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.06087v3
Date: Mon, 19 Aug 2024 11:44:22 GMT
ステータス: 処理完了
システム内更新日: 2024-08-21 03:08:08.912536
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の性能は, スピンガラスの平均解法における古典的アルゴリズムと同等であり, シェリントン-カークパトリックモデルに対して, 厳密な解を得るという予想が真であることを示す証拠が得られた。

関連論文リスト

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)
Extending relax-and-round combinatorial optimization solvers with quantum correlations [0.0]
量子近似最適化アルゴリズム (QAOA) を$pgeq 1$ の層に埋め込む。 Sherrington-Kirk メガネを含む多くの問題に対して、$p=1$とすると、その古典的な問題と同じくらい正確であることを示す。古典的アルゴリズムに匹敵するパフォーマンスで、量子リラクゼーションとラウンドを網羅するフレームワークの道を開いた。
論文参考訳（メタデータ） (2023-07-11T22:02:01Z)
Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
論文参考訳（メタデータ） (2022-08-14T20:39:48Z)
Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文参考訳（メタデータ） (2022-06-30T03:15:23Z)
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)
Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
論文参考訳（メタデータ） (2022-03-15T13:17:53Z)
Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文参考訳（メタデータ） (2021-11-09T09:00:02Z)
The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
論文参考訳（メタデータ） (2021-10-27T06:35:59Z)
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)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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