論文の概要: Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$
- arxiv url: http://arxiv.org/abs/2402.12631v2
- Date: Thu, 03 Oct 2024 15:23:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-04 23:26:48.915238
- Title: Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$
- Title（参考訳）: 深さ$p=1$の3つの正則マックスカットインスタンス上のウォームスタートQAOAの理論的近似比
- Authors: Reuben Tate, Stephan Eidenbenz,
- Abstract要約: 我々はFarhiの0.6924近似結果技術をウォームスタートQAOAに一般化する。
初期状態が積状態であり、各キュービット位置がブロッホ球の北極または南極から約$theta$離れた角度にある場合の温暖開始を考える。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle $\theta$, we consider warm-starts where the initial state is a product state where each qubit position is angle $\theta$ away from either the north or south pole of the Bloch sphere; of the two possible qubit positions the position of each qubit is decided by some classically obtained cut encoded as a bitstring $b$. We illustrate through plots how the properties of $b$ and the initialization angle $\theta$ influence the bound on the approximation ratios of warm-started QAOA. We consider various classical algorithms (and the cuts they produce which we use to generate the warm-start). Our results strongly suggest that there does not exist any choice of initialization angle that yields a (worst-case) approximation ratio that simultaneously beats standard QAOA and the classical algorithm used to create the warm-start. Additionally, we show that at $\theta=60^\circ$, warm-started QAOA is able to (effectively) recover the cut used to generate the warm-start, thus suggesting that in practice, this value could be a promising starting angle to explore alternate solutions in a heuristic fashion.
- Abstract（参考訳）: 我々は3つの正則グラフ上の最大量子近似最適化アルゴリズム(QAOA)のFarhiらによる0.6924近似結果を一般化し、ウォームスタートされたQAOAの近似比の証明可能な下限を求める。
初期化角 $\theta$ が与えられると、初期状態が積状態であるとき、各キュービット位置がブロッホ球の北または南極から離れた角度 $\theta$ となる。
プロットを通して、$b$の特性と初期化角$\theta$が、ウォームスタートされたQAOAの近似比にどのように影響するかを説明する。
様々な古典的アルゴリズム(そして、ウォームスタートを生成するために使用するカット)について検討する。
以上の結果から,従来のQAOAと古典的アルゴリズムを併用してウォームスタートを生成する近似比を導出する初期化角度の選択は存在しないことが示唆された。
さらに、$\theta=60^\circ$のウォームスタート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) - An angle rounding parameter initialization technique for ma-QAOA [2.048226951354646]
マルチ角量子近似最適化アルゴリズム(ma-QAOA)は、量子近似最適化アルゴリズム(QAOA)と少なくとも同じ近似比を与えるアルゴリズムである。
ma-QAOAの欠点の1つは、QAOAよりもかなり古典的なパラメータを使用するため、古典的な最適化成分はより複雑である。
論文 参考訳（メタデータ） (2024-04-16T17:19:49Z) - Alignment between Initial State and Mixer Improves QAOA Performance for
Constrained Optimization [11.445200448951072]
量子交互演算子 ansatz (QAOA) は断熱アルゴリズムと強い関係を持つ。
本稿では, 断熱アルゴリズムの直感がQAOA初期状態を選択するタスクに適用できることを実証する。
論文 参考訳（メタデータ） (2023-05-05T21:54:28Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - Neural Inverse Kinematics [72.85330210991508]
逆キネマティック(英語版)(IK)法は、キネマティックチェインにおける選択された要素の所望の位置から関節のパラメータを復元する。
本稿では,問題階層構造を用いて,所望の位置に条件付き有効関節角度を逐次サンプリングするニューラルIK法を提案する。
論文 参考訳（メタデータ） (2022-05-22T14:44:07Z) - 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) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Counterdiabaticity and the quantum approximate optimization algorithm [0.0]
量子近似最適化アルゴリズム(QAOA)は、MaxCutなどの最適化問題を解くことを目的とした、短期的なハイブリッドアルゴリズムである。
この研究において、QAOAと断定性の間の接続は、$p$大だが有限の規則を検査することによって明確にされる。
グラフ間のパラメータの移動と$p+1$の補間角がともにCD-QAOAマッチングの自然な副産物であることを示す。
論文 参考訳（メタデータ） (2021-06-29T18:00:47Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。