論文の概要: The Overlap Gap Property limits limit swapping in the QAOA
- arxiv url: http://arxiv.org/abs/2404.06087v6
- Date: Sat, 02 Aug 2025 11:45:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-05 14:07:55.27222
- Title: The Overlap Gap Property limits limit swapping in the QAOA
- Title(参考訳): QAOAにおけるオーバーラップギャップ特性制限スワップ
- Authors: Mark Goh,
- Abstract要約: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化問題(COP)のために設計された量子アルゴリズムである。
また, スピングラス型COPの局所アルゴリズムが, 基礎となるErd"os-R'enyiハイパーグラフの対数深さでの性能に制限されている場合, ランダム正規ハイパーグラフも同様に制限されることを示す。
- 参考スコア(独自算出の注目度): 5.578103948136372
- 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 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 is similarly limited in performance as well. As such, we re-derived the fact that the average-case value obtained by the QAOA for even $q\ge 4$, Max-$q$-XORSAT is bounded away from optimality when optimised using asymptotic analysis due to 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 constant depth. Furthermore, the extension to logarithmic depth leads to a tightening of the upper bound that the QAOA outputs at logarithmic depth for MaxCUT and Max-$q$-XORSAT problems. We also provide some numerical evidence the limitation should be extended to odd $q$ by showing that the OGP exists for the Max-$3$-XORSAT on random regular graphs.
- Abstract(参考訳): 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、組合せ最適化問題(COP)のために設計された量子アルゴリズムである。
本稿では, スピングラス型COPの局所アルゴリズムが, 基礎となるErd\"os-R'enyiハイパーグラフの対数深さでの性能に制限されている場合, 同様にランダムな正規ハイパーグラフも性能に制限されていることを示す。
そこで我々は, オーバーラップギャップ特性 (OGP) による漸近解析を用いて最適化した場合, QAOA が得られる平均ケース値を$q\ge 4$, Max-$q$-XORSAT が最適性から逸脱するという事実を再定義した。
この結果は以前にも証明されたが、この証明は我々のものに比べてかなり技術的である。
さらに、初期結果は対数深度$p \le \epsilon \log n$ の制限を暗黙的に意味していることも示している。
さらに、対数深さへの拡張は、QAOAがMaxCUTおよびMax-$q$-XORSAT問題に対して対数深さで出力する上限の締め付けにつながる。
また、OGP がランダム正規グラフ上の Max-$3$-XORSAT に対して存在することを示すことによって、制限を奇数$q$まで拡張すべきという数値的な証拠も提示する。
関連論文リスト
- On Speedups for Convex Optimization via Quantum Dynamics [2.5094874597551913]
量子ハミルトニアンDescentフレームワークの離散シミュレーションを用いて凸最適化における量子速度の可能性を探る。
連続時間において、適切なパラメータを持つQHDは、任意に高速な収束率が得られることを示す。
QHDは、この評価ノイズのレベルを許容する既知の全ての古典的アルゴリズムに対して、超クアドラルなクエリの利点を提供することを示す。
論文 参考訳(メタデータ) (2025-03-31T17:21:12Z) - Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA [0.027042267806481293]
我々は MaxCut を、様々な$g$s に対して最小の girth $g$ の 3 つの正則グラフ上で研究する。
深さ$g geq 16$、深さ$p geq 7$の場合、QAOAは以前に知られていた下限を改善する。
論文 参考訳(メタデータ) (2025-03-17T03:58:43Z) - Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems [0.0]
量子近似最適化アルゴリズムの最適化問題に対する量子優位性を実現する能力はまだ不明である。
ランダムなMax-$k$XOR上でのQAOAの性能を$k$の関数と節対変数比として解析する。
満足度の高いレベルに達するには、非常に大きな$p$が必要であり、変動コンテキストと短期デバイスの両方において、かなり難しいとみなす必要がある。
論文 参考訳(メタデータ) (2024-11-28T21:39:58Z) - Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。
まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。
第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1の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) - 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) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳(メタデータ) (2021-10-15T00:54:04Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。