論文の概要: The Overlap Gap Property limits limit swapping in QAOA

• arxiv url: http://arxiv.org/abs/2404.06087v4
• Date: Mon, 11 Nov 2024 13:35:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-12 14:03:23.501856
• Title: The Overlap Gap Property limits limit swapping in QAOA
• Title（参考訳）: QAOAにおけるオーバーラップギャップ特性制限リミットスワップ
• Authors: Mark Xin Hong Goh,
• Abstract要約: ここでは,qge 4$ の Max-$q$-XORSAT に対する QAOA の平均ケース値が最適性から外れていることを示す。 その結果,スピングラス上でのQAOAの性能は古典的アルゴリズムと同等であることが示唆された。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erd\"os--R\'enyi hypergraph, then a random regular hypergraph exhibits it as well. As such, we re-derived the fact that the average-case value obtained by QAOA for the Max-$q$-XORSAT for even $q\ge 4$ is bounded away from optimality even when the algorithm runs indefinitely if optimised using the so-called tree parameters due to the presence of the Overlap Gap Property (OGP). While this result was proven before, the proof is rather technical compared to ours. In addition, we show that the earlier result implicitly also implies limitation at logarithmic depth $p \le \epsilon \log n$ providing an improvement over limitation at superconstant depth. Lastly, the results suggests that even when sub-optimised, the performance of QAOA on spin glass is equal in performance to classical algorithms in solving the mean field spin glass problem providing further evidence that the conjecture of getting the exact solution under limit swapping for the Sherrington--Kirkpatrick model to be true.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、組合せ最適化問題(COP)のために設計された量子アルゴリズムである。 スピングラス型COPの局所アルゴリズムが,基礎となる Erd\"os-R'enyi ハイパーグラフの対数深さでの性能に制限されている場合,ランダムな正規ハイパーグラフもそれを示す。 したがって, オーバーラップギャップ特性 (OGP) の存在により, いわゆるツリーパラメータを用いて最適化した場合, アルゴリズムが無期限に実行された場合でも, 最大$q$-XORSAT に対して$q\ge 4$ に対して QAOA が得られる平均値が最適性から逸脱するという事実を再導出する。 この結果は以前にも証明されたが、この証明は我々のものに比べてかなり技術的である。 さらに、初期結果は対数深度$p \le \epsilon \log n$ の制限を暗黙的に意味していることも示している。 最後に、スピングラス上でのQAOAの性能は、サブ最適化された場合でも、平均スピングラス問題の解法における古典的アルゴリズムと同等であり、シェリントン-カークパトリックモデルの極限スワップによる正確な解を得るという予想が真であることを示す証拠となる。

関連論文リスト

• Improved Recursive QAOA for Solving MAX-CUT on Bipartite Graphs [4.364124102844566]
  両部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。 レベル1再帰QAOA(RQAOA)を用いて同じ問題を解く数値結果を通して示す。 本稿では,QAOAに最適化されたパラメータ構造を削減したRQAOAを提案する。
  論文  参考訳（メタデータ） (2024-08-23T16:35:47Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
  ランダム正則グラフ上での最大カットと最大独立集合問題を考える。 高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。 両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
  論文  参考訳（メタデータ） (2024-06-20T18:00:02Z)
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
  量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。 我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。 約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
  論文  参考訳（メタデータ） (2022-08-14T20:39:48Z)
• 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)
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models [15.857373057387669]
  無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。 我々の分析は、サドル点近似の和対パス積分によって理解することができる。 一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
  論文  参考訳（メタデータ） (2022-04-21T17:40:39Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit [0.05076419064097732]
  推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。 この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
  論文  参考訳（メタデータ） (2021-10-20T17:58:53Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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