論文の概要: Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
- arxiv url: http://arxiv.org/abs/2406.14618v1
- Date: Thu, 20 Jun 2024 18:00:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-24 18:23:10.681083
- Title: Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
- Title（参考訳）: 量子近似最適化アルゴリズムの性能ランドスケープにおけるノズルピースの欠落
- Authors: Elisabeth Wybo, Martin Leib,
- Abstract要約: ランダム正則グラフ上での最大カットと最大独立集合問題を考える。
高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。
両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the maximum cut and maximum independent set problems on random regular graphs, and calculate the energy densities achieved by QAOA for high regularities up to $d=100$. Such an analysis is possible because the reverse causal cones of the operators in the Hamiltonian are associated with tree subgraphs, for which efficient classical contraction schemes can be developed. We combine the QAOA analysis with state-of-the-art upper bounds on optimality for both problems. This yields novel and better bounds on the approximation ratios achieved by QAOA for large problem sizes. We show that the approximation ratios achieved by QAOA improve as the graph regularity increases for the maximum cut problem. However, QAOA exhibits the opposite behavior for the maximum independent set problem, i.e. the approximation ratios decrease with increasing regularity. This phenomenon is explainable by the overlap gap property for large $d$, which restricts local algorithms (like QAOA) from reaching near-optimal solutions with high probability. In addition, we use the QAOA parameters determined on the tree subgraphs for small graph instances, and in that way outperform classical algorithms like Goemans-Williamson for the maximum cut problem and minimal greedy for the maximum independent set problem. In this way we circumvent the parameter optimization problem and are able to derive bounds on the expected approximation ratios.
- Abstract（参考訳）: ランダムな正則グラフ上での最大カットと最大独立集合問題を考慮し、高い正則性に対してQAOAによって達成されるエネルギー密度を最大$d=100$まで計算する。
このような解析は、ハミルトニアン作用素の逆因果錐が木部分グラフに関連付けられており、効率的な古典的収縮スキームを開発できるため可能である。
両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
これは、QAOAが大きな問題サイズに対して達成した近似比に、新しくより良い境界をもたらす。
最大カット問題に対するグラフ正則性の増加に伴い,QAOAにより達成される近似比が向上することを示す。
しかし、QAOAは最大独立集合問題に対して逆の挙動を示す。
この現象は、(QAOAのような)局所アルゴリズムが高い確率で最適に近い解に到達することを制限する、大きな$d$の重なり合うギャップ特性によって説明できる。
さらに,木部分グラフ上で決定されたQAOAパラメータを小さなグラフのインスタンスに適用し,その場合,最大カット問題に対してゴーマンス・ウィリアムソンのような古典的アルゴリズムを上回り,最大独立集合問題に対して最小の欲求性を与える。
このようにして、パラメータ最適化問題を回避し、期待される近似比のバウンダリを導出することができる。
関連論文リスト
- Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。
まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。
第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。
最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
論文 参考訳（メタデータ） (2024-08-23T16:35:47Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
論文 参考訳（メタデータ） (2023-02-09T07:47:06Z) - 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) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit [0.05076419064097732]
推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。
この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
論文 参考訳（メタデータ） (2021-10-20T17:58:53Z) - 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) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - 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) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: Worst Case Examples [6.810856082577402]
量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。
我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
論文 参考訳（メタデータ） (2020-05-18T14:23:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。