論文の概要: 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の性能は、サブ最適化された場合でも、平均スピングラス問題の解法における古典的アルゴリズムと同等であり、シェリントン-カークパトリックモデルの極限スワップによる正確な解を得るという予想が真であることを示す証拠となる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。