論文の概要: Warm-Started QAOA with Custom Mixers Provably Converges and
Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
- arxiv url: http://arxiv.org/abs/2112.11354v2
- Date: Tue, 27 Sep 2022 17:11:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-03 22:27:44.757525
- Title: Warm-Started QAOA with Custom Mixers Provably Converges and
Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
- Title（参考訳）: 低回路深さでゴーマンス・ウィリアムソンのマックスカットに収束し、計算的に打ち負かされるカスタムミキサー付きウォームスタートQAOA
- Authors: Reuben Tate and Jai Moondra and Bryan Gard and Greg Mohler and Swati
Gupta
- Abstract要約: 本稿では,QAOA-warmestがFarhiらの標準QAOAよりも優れていることを示す。
分離可能な初期状態を持つQAOA-ウォーメストは、アディアベート極限の下でMax-Cutに$prightarrow infty$として収束することを示す。
- 参考スコア（独自算出の注目度）: 4.024850952459758
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We generalize the Quantum Approximate Optimization Algorithm (QAOA) of Farhi
et al. (2014) to allow for arbitrary separable initial states and corresponding
mixers such that the starting state is the most excited state of the mixing
Hamiltonian. We demonstrate this version of QAOA,which we call QAOA-warmest, by
simulating Max-Cut on weighted graphs. We initialize the starting state as a
warm-start using rank-2 and rank-3 approximations obtained using randomized
projections of solutions to Max-Cut's semi-definite program, and define a
warm-start dependent custom mixer. We show that these warm-starts initialize
the QAOA circuit with constant-factor approximations of $0.658$ for rank-2 and
$0.585$ for rank-3 warm-starts for graphs with non-negative edge weights,
improving upon previously known trivial (i.e., $0.5$ for standard
initialization) worst-case bounds. We further show that QAOA-warmest with any
separable initial state converges to Max-Cut under the adiabatic limit as
$p\rightarrow \infty$. Our numerical simulations with this generalization yield
higher quality cuts (compared to standard QAOA, the classical
Goemans-Williamson algorithm, and a warm-started QAOA without custom mixers)
for an instance library of 1148 graphs (upto 11 nodes) and depth $p=8$. We
further show that QAOA-warmest outperforms the standard QAOA of Farhi et al. in
experiments on current IBM-Q and Quantinuum hardware.
- Abstract（参考訳）: 我々は、farhi et al. (2014) の量子近似最適化アルゴリズム (qaoa) を一般化し、任意の分離可能な初期状態と対応するミキサーに対して、出発状態が混合ハミルトニアンの最も励起状態となるように一般化する。
重み付きグラフ上でMax-Cutをシミュレートすることで、QAOA-warmestと呼ぶこのバージョンのQAOAを実演する。
我々は, max-cut の半定義プログラムに対する解のランダム射影を用いて得られる rank-2 と rank-3 近似を用いて開始状態をウォームスタートとして初期化し,ウォームスタート依存のカスタムミキサーを定義する。
これらのウォームスタートは、ランク2に対して0.658$、非負のエッジ重みを持つグラフに対して0.585$の定数係数近似でQAOA回路を初期化し、既知自明な(標準初期化のために0.5$)最悪のケース境界を改善する。
さらに,任意の分離可能な初期状態を持つqaoa-warmestは,p\rightarrow \infty$という断熱限界の下でmax-cutに収束することを示した。
この一般化による数値シミュレーションにより、1148グラフ(最大11ノード)と深さ$p=8$のインスタンスライブラリに対して、より高品質なカット(標準QAOA、古典Goemans-Williamsonアルゴリズム、カスタムミキサーなしQAOA)が得られる。
さらに、現在のIBM-QおよびQuantinuumハードウェアの実験において、QAOA-warmestがFarhiらの標準QAOAよりも優れていることを示す。
関連論文リスト
- Warm-Started QAOA with Aligned Mixers Converges Slowly Near the Poles of the Bloch Sphere [0.0]
研究者は古典的なアルゴリズムから返された解を利用して、QAOAのためのウォームスタートした量子初期状態を作り出した。
小さい$theta$の場合、回路深さの低い境界は、$Delta lambda/theta$とほぼ比例する。
論文 参考訳（メタデータ） (2024-09-16T14:43:42Z) - Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$ [0.0]
我々はFarhiの0.6924近似結果技術をウォームスタートQAOAに一般化する。
初期状態が積状態であり、各キュービット位置がブロッホ球の北極または南極から約$theta$離れた角度にある場合の温暖開始を考える。
論文 参考訳（メタデータ） (2024-02-20T01:22:07Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Alignment between Initial State and Mixer Improves QAOA Performance for
Constrained Optimization [11.445200448951072]
量子交互演算子 ansatz (QAOA) は断熱アルゴリズムと強い関係を持つ。
本稿では, 断熱アルゴリズムの直感がQAOA初期状態を選択するタスクに適用できることを実証する。
論文 参考訳（メタデータ） (2023-05-05T21:54:28Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - 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) - Exploiting Symmetry Reduces the Cost of Training QAOA [6.295931120803673]
そこで本研究では,QAOAエネルギーの対称性を利用して,QAOAエネルギーの評価を高速化するための新しい手法を提案する。
目的関数の古典的対称性と、QAOAエネルギーに関するコストハミルトニアン項の対称性の関連性を示す。
我々のアプローチは一般であり、既知の対称性の任意の部分群に適用され、グラフ問題に限らない。
論文 参考訳（メタデータ） (2021-01-25T18:25:44Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - Bridging Classical and Quantum with SDP initialized warm-starts for QAOA [4.76507354067301]
本稿では,QAOAをグラフ内のすべての可能なカットの偏重重ね合わせで初期化する,古典的な前処理ステップを紹介する。
我々は、QAOA-Warmと呼ばれるこのQAOAの変種が、トレーニング時間が少なく、低い回路深度で標準QAOAより優れていることを示す。
論文 参考訳（メタデータ） (2020-10-27T02:57:22Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。