論文の概要: Lower Bounds on Number of QAOA Rounds Required for Guaranteed Approximation Ratios

• arxiv url: http://arxiv.org/abs/2308.15442v3
• Date: Mon, 4 Sep 2023 03:27:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-07 02:37:10.102729
• Title: Lower Bounds on Number of QAOA Rounds Required for Guaranteed Approximation Ratios
• Title（参考訳）: 近似比保証に必要なQAOAラウンド数に関する下限
• Authors: Naphan Benchasattabuse, Andreas B\"artschi, Luis Pedro Garc\'ia-Pintos, John Golden, Nathan Lemons and Stephan Eidenbenz
• Abstract要約: 量子交互作用素アンサッツ(QAOA)に必要なラウンド数に対する最初の下界のいくつかを提供する。 このタイプのQAOAは、ほとんどの問題に対して一定の近似比を保証するために少なくとも複数のラウンドを必要とすることを示す。 我々のフレームワークは、すべての局所的なコスト問題に自明な制約を与えます。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 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 QAOA. For our main result, (i) we leverage a connection between quantum annealing times and the angles of QAOA to derive a lower bound on the number of rounds of 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 all strictly $k$-local cost Hamiltonians matching known results that constant approximation ratio is obtainable with constant round QAOA for a few optimization problems from these classes. Using our novel 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（参考訳）: 量子交互作用素 ansatz (qaoa) は、最大充足可能性のような組合せ最適化問題に対する高品質な近似解を見つけるためのヒューリスティックなハイブリッド量子古典アルゴリズムである。 QAOAはよく研究されているが、実行時や近似比の保証に関する理論的結果はまだ比較的少ない。 我々はQAOAに必要なラウンド数(QAOAランタイムの主要なコンポーネント)について、最初の下位境界をいくつか提示する。 私たちの主な成果は (i) 量子アニーリング時間とqaoaの角度との関係を利用して、保証された近似比に対してqaoaのラウンド数に対する下界を導出する。 我々は、Groverスタイルの混合ユニタリでこれを適用し、計算する。 (ii) このタイプのQAOAは、ほとんどの問題に対して定数近似比を保証するために少なくとも1つの多項式数を必要とすることを示す。 私たちも (iii) 有界関数は対象関数の統計値にのみ依存し、問題が$k$局所ハミルトニアンとしてモデル化できる場合、ハミルトニアンの係数から容易に推定できることを示す。 従来の横フィールドミキサーについて (iv)本フレームワークは,局所的な局所的コスト問題と厳密な$k$-ローカルなコストハミルトニアンは,これらのクラスからのいくつかの最適化問題に対して,定数近似比が一定のラウンドQAOAで得られることを既知の結果と一致する。 新たな証明フレームワークを使って (v)非構造化探索のためのGroverの下限を復元し、小さな修正を加えて、混合ユニタリの基底状態から始まるQAOAスタイルのサーチプロトコルに我々のバウンドが適用されることを示す。

関連論文リスト

• 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)

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

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