Fugu-MT 論文翻訳(概要): The Overlap Gap Property limits limit swapping in QAOA

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

arxiv url: http://arxiv.org/abs/2404.06087v2
Date: Mon, 6 May 2024 18:03:03 GMT
ステータス: 処理完了
システム内更新日: 2024-05-08 19:03:36.695651
Title: The Overlap Gap Property limits limit swapping in QAOA
Title（参考訳）: QAOAにおけるオーバーラップギャップ特性制限リミットスワップ
Authors: Mark Xin Hong Goh,
Abstract要約: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化問題(COP)のために設計された量子アルゴリズムである。スピンガラス上でのQAOAの性能は, スピンガラスの平均解法における古典的アルゴリズムと同等であることを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a COP with an underlying Erd\"os--R\'enyi hypergraph exhibits the Overlap Gap Property (OGP), then a random regular hypergraph exhibits it as well. Given that Max-$q$-XORSAT on an Erd\"os--R\'enyi hypergraph is known to exhibit the OGP, and since the performance of QAOA for the pure $q$-spin model matches asymptotically for Max-$q$-XORSAT on large-girth regular hypergraph, we show that the average-case value obtained by QAOA for the pure $q$-spin model for even $q\ge 4$ is bounded away from optimality even when the algorithm runs indefinitely. This suggests that a necessary condition for the validity of limit swapping in QAOA is the absence of OGP in a given combinatorial optimization problem. Furthermore, 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)のために設計された量子アルゴリズムである。基礎となる Erd\"os--R'enyi ハイパーグラフを持つ COP がオーバーラップギャップ特性 (OGP) を示す場合、ランダムな正規ハイパーグラフもそれを示す。例えば、Erd\"os-R'enyiハイパーグラフ上のMax-$q$-XORSATがOGPを示すことが知られており、純$q$-spinモデルに対するQAOAのパフォーマンスは、大容量正規ハイパーグラフ上のMax-$q$-XORSATと漸近的に一致していることから、QAOAが純$q$-spinモデルに対して得られる平均ケース値は、q\ge 4$であっても、アルゴリズムが無期限に実行しても最適性から逸脱していることを示す。このことは、QAOAにおける極限スワップの有効性に対する必要条件は、与えられた組合せ最適化問題における OGP の欠如であることを示している。さらに, スピンガラス上での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)

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

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