論文の概要: Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for
3-Regular MAXCUT and Higher-Round Scaling Limits
- arxiv url: http://arxiv.org/abs/2402.12631v1
- Date: Tue, 20 Feb 2024 01:22:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 17:35:33.337318
- Title: Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for
3-Regular MAXCUT and Higher-Round Scaling Limits
- Title（参考訳）: ウォームスタートQAOAの保証:3レギュラーMAXCUTの単線近似比と高速スケーリング限界
- Authors: Reuben Tate and Stephan Eidenbenz
- Abstract要約: 我々はFarhiの0.6924近似結果技術をウォームスタートQAOAに一般化する。
小さい$theta$の場合、その上限は1/theta$に大まかに比例する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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. Finally, for any combinatorial
optimization problem with integer-valued objective values, we provide bounds on
the required circuit depth needed for warm-started QAOA to achieve some change
in approximation ratio; more specifically, we show that for small $\theta$, the
bound is roughly proportional to $1/\theta$.
- Abstract（参考訳）: 我々は3つの正則グラフ上の最大量子近似最適化アルゴリズム(QAOA)のFarhiらによる0.6924近似結果を一般化し、ウォームスタートされたQAOAの近似比の証明可能な下限を求める。
初期化角 $\theta$ が与えられると、初期状態が積状態であり、各キュービットの位置がブロッホ球面の北極または南極のいずれかから離れる角 $\theta$ であるようなウォームスタートを考える。
b$ の性質と初期化角度 $\theta$ がウォームスタートqaoa の近似比にどのように影響するかをプロットで示す。
さまざまな古典的なアルゴリズム(そしてウォームスタートを生成するために使用するカット)を考えています。
以上の結果から,従来のQAOAと古典的アルゴリズムを併用してウォームスタートを生成する近似比を導出する初期化角度の選択は存在しないことが示唆された。
さらに、$\theta=60^\circ$のウォームスタートQAOAは、ウォームスタート生成に使用されるカットを(効果的に)回収できることを示し、この値が実際は、代替解をヒューリスティックな方法で探索するための有望な開始角度である可能性を示唆している。
最後に、整数値を持つ組合せ最適化問題に対して、ウォームスタートした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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。