論文の概要: Expectation Values from the Single-Layer Quantum Approximate
Optimization Algorithm on Ising Problems
- arxiv url: http://arxiv.org/abs/2012.03421v3
- Date: Fri, 23 Sep 2022 16:54:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-21 21:12:09.089351
- Title: Expectation Values from the Single-Layer Quantum Approximate
Optimization Algorithm on Ising Problems
- Title（参考訳）: 単層量子近似最適化アルゴリズムのイジング問題に対する期待値
- Authors: Asier Ozaeta, Wim van Dam, Peter L. McMahon
- Abstract要約: 単一層(p=1$)量子近似最適化アルゴリズム(QAOA)によって生成されるエネルギー-観測値のランドスケープについて報告する。
景観は我々が導いた解析式を用いて得られる。
数千量子ビットの量子コンピュータ上で実行される場合、単層QAOAがどの程度うまく機能するかを推定する。
- 参考スコア（独自算出の注目度）: 1.8732539895890135
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We report on the energy-expectation-value landscapes produced by the
single-layer ($p=1$) Quantum Approximate Optimization Algorithm (QAOA) when
being used to solve Ising problems. The landscapes are obtained using an
analytical formula that we derive. The formula allows us to predict the
landscape for any given Ising problem instance and consequently predict the
optimal QAOA parameters for heuristically solving that instance using the
single-layer QAOA. We have validated our analytical formula by showing that it
accurately reproduces the landscapes published in recent experimental reports.
We then applied our methods to address the question: how well is the
single-layer QAOA able to solve large benchmark problem instances? We used our
analytical formula to calculate the optimal energy-expectation values for
benchmark MAX-CUT problems containing up to $7\,000$ vertices and $41\,459$
edges. We also calculated the optimal energy expectations for general Ising
problems with up to $100\,000$ vertices and $150\,000$ edges. Our results
provide an estimate for how well the single-layer QAOA may work when run on a
quantum computer with thousands of qubits. In addition to providing performance
estimates when optimal angles are used, we are able to use our analytical
results to investigate the difficulties one may encounter when running the QAOA
in practice for different classes of Ising instances. We find that depending on
the parameters of the Ising Hamiltonian, the expectation-value landscapes can
be rather complex, with sharp features that necessitate highly accurate
rotation gates in order for the QAOA to be run optimally on quantum hardware.
We also present analytical results that explain some of the qualitative
landscape features that are observed numerically.
- Abstract（参考訳）: 本稿では,単一層(p=1$)量子近似最適化アルゴリズム(qaoa)が生成するエネルギー期待値のランドスケープについて報告する。
景観は我々が導いた解析式を用いて得られる。
この公式により、任意のIsing問題インスタンスのランドスケープを予測でき、その結果、単一層QAOAを用いてそのインスタンスをヒューリスティックに解くための最適なQAOAパラメータを予測できる。
我々は,最近の実験報告で公表された景観を正確に再現できることを示し,解析式を検証する。
シングルレイヤのQAOAが大規模なベンチマーク問題インスタンスをどの程度うまく解決できるのか?
解析式を用いて最大7,000ドルの頂点と41,459ドルの辺を含むベンチマークマックスカット問題の最適エネルギー期待値を計算した。
また,一般的なイジング問題に対する最適エネルギー期待値を,最大100,000ドルの頂点と150,000ドルのエッジで計算した。
私たちの結果は、数千キュービットの量子コンピュータ上で動作した場合、シングルレイヤqaoaがどの程度うまく機能するかを推定するものです。
最適角度を用いた場合のパフォーマンス推定に加えて、分析結果を用いて、Isingインスタンスの異なるクラスで実際にQAOAを実行する場合の難易度を調べることができる。
アイジング・ハミルトンのパラメータによっては、QAOAが量子ハードウェア上で最適に動作するためには、高精度な回転ゲートを必要とするシャープな特徴を持つ期待値のランドスケープがかなり複雑になることが分かる。
また,数値的に観察される定性的な景観特徴のいくつかを説明する分析結果も提示する。
関連論文リスト
- Parameter Setting in Quantum Approximate Optimization of Weighted
Problems [10.396104620517171]
本研究では,重み付き問題の一般的なクラスに適用したQAOAのパラメータ設定を開発する。
まず、重み付けされたMaxCut問題に適用した深さ$p=1$のQAOAに対する最適パラメータを、重み付けの異なる仮定の下で導出する。
第二に、$pgeq 1$ の場合、重み付き MaxCut の QAOA エネルギーランドスケープが、パラメータの単純な再スケーリングの下での未重み付きケースにアプローチすることを証明します。
第三に、重み付きMaxCutの解析結果から着想を得た一般的な再スケーリング手法を提案し、その効果を実証する。
論文 参考訳（メタデータ） (2023-05-24T14:37:33Z) - Solving boolean satisfiability problems with the quantum approximate
optimization algorithm [0.05076419064097732]
量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。
我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。
約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
論文 参考訳（メタデータ） (2022-08-14T20:39:48Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳（メタデータ） (2021-02-12T23:12:09Z) - Exploiting Symmetry Reduces the Cost of Training QAOA [6.295931120803673]
そこで本研究では,QAOAエネルギーの対称性を利用して,QAOAエネルギーの評価を高速化するための新しい手法を提案する。
目的関数の古典的対称性と、QAOAエネルギーに関するコストハミルトニアン項の対称性の関連性を示す。
我々のアプローチは一般であり、既知の対称性の任意の部分群に適用され、グラフ問題に限らない。
論文 参考訳（メタデータ） (2021-01-25T18:25:44Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Evaluation of QAOA based on the approximation ratio of individual
samples [0.0]
我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、いくつかの古典的代替品と比較する。
QAOA計算複雑性理論のガイダンスが進化しているため、量子的優位性を求めるためのフレームワークを利用する。
論文 参考訳（メタデータ） (2020-06-08T18:00:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。