論文の概要: Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios

• arxiv url: http://arxiv.org/abs/2308.15442v4
• Date: Wed, 11 Jun 2025 16:18:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 06:35:01.311234
• Title: Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Title（参考訳）: 保証近似比に必要な量子近似最適化アルゴリズムのラウンド数に関する下界
• Authors: Naphan Benchasattabuse, Andreas Bärtschi, Luis Pedro García-Pintos, John Golden, Nathan Lemons, Stephan Eidenbenz,
• Abstract要約: 本稿では、QAOAに必要なラウンド数(QAOAランタイムの主成分)について、最初の低い係数をいくつか提示する。 従来の横フィールドミキサーの場合、(iv)我々のフレームワークは、すべての有界共起局所コスト問題に自明な下限を与える。 厳密には$k$-local cost Hamiltonian matching known results that constant approximation ratio is obtained with a constant-round QAOA。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum approximate optimization algorithm, also known in its generalization as the quantum alternating operator ansatz, (QAOA) is a heuristic hybrid quantum-classical algorithm for finding high-quality approximate solutions to combinatorial optimization problems, such as maximum satisfiability. While the QAOA is well studied, theoretical results as to its runtime or approximation ratio guarantees are still relatively sparse. We provide some of the first lower bounds for the number of rounds (the dominant component of QAOA runtimes) required for the QAOA. For our main result, we (i) leverage a connection between quantum annealing times and the angles of the QAOA to derive a lower bound on the number of rounds of the QAOA with respect to the guaranteed approximation ratio. We apply and calculate this bound with Grover-style mixing unitaries and (ii) show that this type of QAOA requires at least a polynomial number of rounds to guarantee any constant approximation ratios for most problems. We also (iii) show that the bound depends only on the statistical values of the objective functions, and when the problem can be modeled as a $k$-local Hamiltonian, can be easily estimated from the coefficients of the Hamiltonians. For the conventional transverse-field mixer, (iv) our framework gives a trivial lower bound to all bounded-occurrence local cost problems and for all strictly $k$-local cost Hamiltonians matching known results that constant approximation ratio is obtainable with a constant-round QAOA for a few optimization problems from these classes. Using our proof framework, (v) we recover the Grover lower bound for unstructured search and, with small modification, show that our bound applies to any QAOA-style search protocol that starts in the ground state of the mixing unitaries.
• Abstract（参考訳）: 量子近似最適化アルゴリズムは量子交互演算子アンサッツ (QAOA) としても知られ、最大満足度などの組合せ最適化問題に対する高品質な近似解を求めるためのヒューリスティックなハイブリッド量子古典的アルゴリズムである。 QAOAはよく研究されているが、その実行時間や近似比の保証に関する理論的結果はいまだに比較的少ない。 我々は、QAOAに必要なラウンド数(QAOAランタイムの主要なコンポーネント)について、最初の下位境界をいくつか提供します。 主な成果のために、私たちは i) 量子アニール時間とQAOAの角度の接続を利用して、保証近似比に対するQAOAのラウンド数に対する下界を導出する。 我々は、Groverスタイルの混合ユニタリでこれを適用し、計算する。 (ii) このタイプのQAOAは、ほとんどの問題に対して定数近似比を保証するために少なくとも1つの多項式数を必要とすることを示す。 私たちも (iii) 有界関数は対象関数の統計値にのみ依存し、問題が$k$局所ハミルトニアンとしてモデル化できる場合、ハミルトニアンの係数から容易に推定できることを示す。 従来の横フィールドミキサーについて (iv)我々のフレームワークは、すべての有界局所コスト問題に自明な下限を与え、厳密な$k$-ローカルコストハミルトニアンは、定数近似比がこれらのクラスからいくつかの最適化問題に対して一定周QAOAで得られることを既知の結果と一致する。 証明フレームワークの使用。 (v)未構造化探索のためのグロバーの下限を復元し、小さな修正を加えれば、混合ユニタリの基底状態から始まる任意のQAOAスタイルの検索プロトコルに適用できることを示す。

関連論文リスト

• Equivalence of Quantum Approximate Optimization Algorithm and Linear-Time Quantum Annealing for the Sherrington-Kirkpatrick Model [2.0174252910776556]
  QAOAエネルギーは、2つの条件下での量子アニールを近似し、すなわち、角度が1つの層から次の層に滑らかに変化し、和が定数で束縛されていることを示す。 この結果は,一定の角度と任意の深さの和と,角度の和におけるエネルギーの級数展開によるQAOAエネルギーの新式によって実現された。
  論文  参考訳（メタデータ） (2025-03-12T17:27:40Z)
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
  ランダム正則グラフ上での最大カットと最大独立集合問題を考える。 高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。 両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
  論文  参考訳（メタデータ） (2024-06-20T18:00:02Z)
• 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)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  最適化問題を解くために考案された量子近似最適化アルゴリズム(QAOA)は、既存のノイズのある中間スケール量子(NISQ)デバイス上で実行することができる。 我々は、QAOAを適切に適応させることにより、一般星座の最大可能性(ML)検出問題を解く。 特に、M-ary Gray-mapped Quarature amplitude modulation (MQAM) 星座では、同相成分をコードする特定の量子ビットと二次成分をコードする量子ビットが、興味のある量子系において独立であることを示す。
  論文  参考訳（メタデータ） (2022-04-11T14:11:24Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization [0.0]
  本稿では,Grover-style unstructured searchによるQAOAの指数的高速化の証拠を示す。 以上の結果から,QAOA性能の最大化にはミキサーと位相分離器の選択が必要であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-01T18:39:52Z)
• Shortcuts to Quantum Approximate Optimization Algorithm [2.150418646956503]
  我々は「QAOAへのショートカット」(S-QAOA)と呼ばれる新しいアンサッツを提案する。 S-QAOAは、2体相互作用を多く含み、パラメータ自由を解放することで、ターゲットハミルトン状態へのショートカットを提供する。 MaxCut問題とSherrington-Kirkpatrick(SK)モデルを考えると、YY相互作用が最高の性能を示す。
  論文  参考訳（メタデータ） (2021-12-21T02:24:19Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
  パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。 QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。 得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
  論文  参考訳（メタデータ） (2021-02-12T23:12:09Z)
• Evaluation of QAOA based on the approximation ratio of individual samples [0.0]
  我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、いくつかの古典的代替品と比較する。 QAOA計算複雑性理論のガイダンスが進化しているため、量子的優位性を求めるためのフレームワークを利用する。
  論文  参考訳（メタデータ） (2020-06-08T18:00:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。