論文の概要: The Quantum Approximate Optimization Algorithm at High Depth for MaxCut
on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
- arxiv url: http://arxiv.org/abs/2110.14206v3
- Date: Thu, 7 Jul 2022 13:35:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-10 03:35:52.839619
- Title: The Quantum Approximate Optimization Algorithm at High Depth for MaxCut
on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
- Title（参考訳）: 大規模Girth正規グラフとシェリントン・カークパトリックモデルを用いたMaxCutの高深さ量子近似最適化アルゴリズム
- Authors: Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, Leo Zhou
- Abstract要約: 量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。
任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。
我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Quantum Approximate Optimization Algorithm (QAOA) finds approximate
solutions to combinatorial optimization problems. Its performance monotonically
improves with its depth $p$. We apply the QAOA to MaxCut on large-girth
$D$-regular graphs. We give an iterative formula to evaluate performance for
any $D$ at any depth $p$. Looking at random $D$-regular graphs, at optimal
parameters and as $D$ goes to infinity, we find that the $p=11$ QAOA beats all
classical algorithms (known to the authors) that are free of unproven
conjectures. While the iterative formula for these $D$-regular graphs is
derived by looking at a single tree subgraph, we prove that it also gives the
ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK)
model defined on the complete graph. We also generalize our formula to
Max-$q$-XORSAT on large-girth regular hypergraphs. Our iteration is a compact
procedure, but its computational complexity grows as $O(p^2 4^p)$. This
iteration is more efficient than the previous procedure for analyzing QAOA
performance on the SK model, and we are able to numerically go to $p=20$.
Encouraged by our findings, we make the optimistic conjecture that the QAOA, as
$p$ goes to infinity, will achieve the Parisi value. We analyze the performance
of the quantum algorithm, but one needs to run it on a quantum computer to
produce a string with the guaranteed performance.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は組合せ最適化問題の近似解を求める。
その性能は深さ$p$で単調に改善する。
大きめの$D$正規グラフ上で、QAOAをMaxCutに適用する。
私たちは、どんな深さでも$d$でパフォーマンスを評価するために反復式を与えます。
ランダムな$D$正規グラフ、最適パラメータ、そして$D$が無限大となると、$p=11$ QAOAは証明されていない予想のないすべての古典的アルゴリズム(著者によって知られている)を破る。
これらの$d$-正則グラフの反復公式は単一の木の部分グラフを見て導かれるが、完全グラフ上で定義されるシェリントン=キルクパトリック(sk)モデル上でのqaoaのアンサンブル平均性能を与えることも証明する。
我々はまた、我々の公式を大幅正規ハイパーグラフ上でMax-$q$-XORSATに一般化する。
我々の反復はコンパクトな手続きであるが、計算複雑性は$O(p^2 4^p)$として増大する。
この繰り返しは、SKモデル上でのQAOA性能の分析方法よりも効率的であり、数値的に$p=20$にすることができる。
我々の発見に勇気づけられて、QAOAは無限大に$p$でパリの価値を達成できるという楽観的な予想を立てる。
量子アルゴリズムの性能を分析するが、それを量子コンピュータ上で実行して、性能が保証された文字列を生成する必要がある。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
論文 参考訳（メタデータ） (2023-06-23T01:28:24Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Performance and limitations of the QAOA at constant levels on large
sparse hypergraphs and spin glass models [15.857373057387669]
無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。
我々の分析は、サドル点近似の和対パス積分によって理解することができる。
一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
論文 参考訳（メタデータ） (2022-04-21T17:40:39Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth
regular graphs [0.0]
すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。
任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
論文 参考訳（メタデータ） (2021-01-14T09:17:20Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。
本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。
Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
論文 参考訳（メタデータ） (2020-11-16T18:43:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。