論文の概要: Counterdiabaticity and the quantum approximate optimization algorithm
- arxiv url: http://arxiv.org/abs/2106.15645v3
- Date: Sat, 22 Jan 2022 18:44:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 19:13:49.126615
- Title: Counterdiabaticity and the quantum approximate optimization algorithm
- Title(参考訳): 逆ダイアバティシティと量子近似最適化アルゴリズム
- Authors: Jonathan Wurtz and Peter J. Love
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)は、MaxCutなどの最適化問題を解くことを目的とした、短期的なハイブリッドアルゴリズムである。
この研究において、QAOAと断定性の間の接続は、$p$大だが有限の規則を検査することによって明確にされる。
グラフ間のパラメータの移動と$p+1$の補間角がともにCD-QAOAマッチングの自然な副産物であることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a near-term hybrid
algorithm intended to solve combinatorial optimization problems, such as
MaxCut. QAOA can be made to mimic an adiabatic schedule, and in the
$p\to\infty$ limit the final state is an exact maximal eigenstate in accordance
with the adiabatic theorem. In this work, the connection between QAOA and
adiabaticity is made explicit by inspecting the regime of $p$ large but finite.
By connecting QAOA to counterdiabatic (CD) evolution, we construct CD-QAOA
angles which mimic a counterdiabatic schedule by matching Trotter "error" terms
to approximate adiabatic gauge potentials which suppress diabatic excitations
arising from finite ramp speed. In our construction, these "error" terms are
helpful, not detrimental, to QAOA. Using this matching to link QAOA with
quantum adiabatic algorithms (QAA), we show that the approximation ratio
converges to one at least as $1-C(p)\sim 1/p^{\mu}$. We show that transfer of
parameters between graphs, and interpolating angles for $p+1$ given $p$ are
both natural byproducts of CD-QAOA matching. Optimization of CD-QAOA angles is
equivalent to optimizing a continuous adiabatic schedule. Finally, we show
that, using a property of variational adiabatic gauge potentials, QAOA is at
least counterdiabatic, not just adiabatic, and has better performance than
finite time adiabatic evolution. We demonstrate the method on three examples: a
2 level system, an Ising chain, and the MaxCut problem.
- Abstract(参考訳): 量子近似最適化アルゴリズム(quantum approximation optimization algorithm,qaoa)は、maxcutのような組合せ最適化問題を解くための近距離ハイブリッドアルゴリズムである。
QAOA は断熱的なスケジュールを模倣するために作成することができ、$p\to\infty$ limit では、最終状態は断熱定理に従って正確に極大固有状態となる。
本研究では, qaoa と adiabaticity の関連は, 大きくても有限な $p$ のレジームを検査することによって明らかにされる。
QAOAを反断熱(CD)の進化に接続することにより、有限ランプ速度から発生するダイアバティック励起を抑制するアディバティックゲージ電位を近似するために、トロッターの「エラー」項をマッチングすることにより、逆断熱スケジュールを模倣するCD-QAOA角を構築する。
私たちの構築では、これらの「エラー」用語は有害ではなく、QAOAに役立ちます。
このマッチングを用いてQAOAと量子断熱アルゴリズム(QAA)を結びつけることにより、近似比が少なくとも1-C(p)\sim 1/p^{\mu}$に収束することを示す。
グラフ間のパラメータの移動と$p+1$の補間角がともにCD-QAOAマッチングの自然な副産物であることを示す。
CD-QAOA角の最適化は連続断熱スケジュールの最適化と等価である。
最後に, 変分的断熱ゲージポテンシャルの特性を用いて, qaoaは少なくとも反断熱性であり, 断熱性だけでなく, 有限時間断熱進化よりも優れた性能を示す。
2レベルシステム、Isingチェーン、MaxCut問題という3つの例でこの手法を実証する。
関連論文リスト
- Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
ランダム正則グラフ上での最大カットと最大独立集合問題を考える。
高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。
両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
論文 参考訳(メタデータ) (2024-06-20T18:00:02Z) - Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free
parameters [0.0]
より高階のCD補正により、手前の問題の正確な解により早く収束できることが示される。
しかし、この結果を達成するのに必要な自由パラメータの総数は、分析された特定のQAOA変種とは独立である。
論文 参考訳(メタデータ) (2023-07-26T10:02:47Z) - Alignment between Initial State and Mixer Improves QAOA Performance for
Constrained Optimization [11.445200448951072]
量子交互演算子 ansatz (QAOA) は断熱アルゴリズムと強い関係を持つ。
本稿では, 断熱アルゴリズムの直感がQAOA初期状態を選択するタスクに適用できることを実証する。
論文 参考訳(メタデータ) (2023-05-05T21:54:28Z) - Simulating scalar field theories on quantum computers with limited
resources [62.997667081978825]
量子ビットコンピュータ上での格子スカラー場理論を実装するための量子アルゴリズムを提案する。
このアルゴリズムは、通常の対称性相と壊れた対称性相の両方において、幅広い入力パラメータの効率的な$phi4$状態の準備を可能にする。
論文 参考訳(メタデータ) (2022-10-14T17:28:15Z) - 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) - Warm-Started QAOA with Custom Mixers Provably Converges and
Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths [5.451583832235867]
本稿では,QAOA-warmestがFarhiらの標準QAOAよりも優れていることを示す。
重み付きグラフ上でMax-Cutをシミュレートすることで、QAOA-warmestと呼ぶQAOAのこのバージョンを実証する。
シミュレーションにより,従来のQAOA,古典的なGoemans-Williamsonアルゴリズム,カスタムミキサーを使わずにウォームスタートしたQAOAと比較して,品質の低下が認められた。
論文 参考訳(メタデータ) (2021-12-21T16:53:16Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳(メタデータ) (2021-06-22T11:07:38Z) - Exploiting Symmetry Reduces the Cost of Training QAOA [6.295931120803673]
そこで本研究では,QAOAエネルギーの対称性を利用して,QAOAエネルギーの評価を高速化するための新しい手法を提案する。
目的関数の古典的対称性と、QAOAエネルギーに関するコストハミルトニアン項の対称性の関連性を示す。
我々のアプローチは一般であり、既知の対称性の任意の部分群に適用され、グラフ問題に限らない。
論文 参考訳(メタデータ) (2021-01-25T18:25:44Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳(メタデータ) (2020-09-29T18:48:21Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳(メタデータ) (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。