論文の概要: 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.11354v4
- Date: Tue, 19 Sep 2023 13:42:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-20 21:03:44.724554
- 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よりも優れていることを示す。
重み付きグラフ上でMax-Cutをシミュレートすることで、QAOA-warmestと呼ぶQAOAのこのバージョンを実証する。
シミュレーションにより,従来のQAOA,古典的なGoemans-Williamsonアルゴリズム,カスタムミキサーを使わずにウォームスタートしたQAOAと比較して,品質の低下が認められた。
- 参考スコア（独自算出の注目度）: 5.451583832235867
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We generalize the Quantum Approximate Optimization Algorithm (QAOA) of Farhi
et al. (2014) to allow for arbitrary separable initial states with
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 $2$ and $3$-dimensional 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 $2$-dimensional and $0.585$ for $3$-dimensional warm-starts for
graphs with non-negative edge weights, improving upon previously known trivial
(i.e., $0.5$ for standard initialization) worst-case bounds at $p=0$. These
factors in fact lower bound the approximation achieved for Max-Cut at higher
circuit depths, since we also show that QAOA-warmest with any separable initial
state converges to Max-Cut under the adiabatic limit as $p\rightarrow \infty$.
However, the choice of warm-starts significantly impacts the rate of
convergence to Max-Cut, and we show empirically that our warm-starts achieve a
faster convergence compared to existing approaches. Additionally, our numerical
simulations show 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's semi-definiteプログラムに対する解のランダム投射を用いて得られる2ドルと3ドルの近似を用いて、開始状態をウォームスタートとして初期化し、ウォームスタート依存のカスタムミキサーを定義する。
これらのウォームスタートは、カオア回路を一定値の近似値である$0.658$、非負のエッジ重みを持つグラフの$0.585$で初期化し、既知の自明(つまり標準初期化に$0.5$)の最悪のケース境界を$p=0$で改善することを示している。
さらに, 分離可能な初期状態を持つqaoa-warmestは, 断熱限界の下では$p\rightarrow \infty$としてmax-cutに収束することを示した。
しかし、ウォームスタートの選択はマックス・カットへの収束率に大きな影響を与え、我々のウォームスタートが既存のアプローチに比べて早く収束できることを実証的に示す。
さらに,従来のQAOA,古典的なGoemans-Williamsonアルゴリズム,および1148ドルのグラフ(最大111ドルノード)と深さ$p=8$のインスタンスライブラリに対して,カスタムミキサーを含まないウォームスタートした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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。