論文の概要: The Overlap Gap Property limits limit swapping in QAOA
- arxiv url: http://arxiv.org/abs/2404.06087v1
- Date: Tue, 9 Apr 2024 07:45:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-10 15:39:15.359992
- Title: The Overlap Gap Property limits limit swapping in QAOA
- Title(参考訳): QAOAにおけるオーバーラップギャップ特性制限リミットスワップ
- Authors: Mark Xin Hong Goh,
- Abstract要約: We show that the Overlap Gap Property (OGP) in the solution space for the Max-$q$-XORSAT is a monotonic increasing function。
QAOAが純$qge 4$に対する$q$-spinモデルに対して得た平均ケース値は、アルゴリズムが無期限に実行されたとしても最適性から逸脱していることを示す。
- 参考スコア(独自算出の注目度): 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. We show that under the assumption that the Overlap Gap Property (OGP) in the solution space for the Max-$q$-XORSAT is a monotonic increasing function, the swapping of limits in QAOA leads to suboptimal results limited by the OGP. Furthermore, 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. A corollary of this is that the spectral gap of a Hamiltonian exhibiting the OGP will close in the thermodynamic limit resulting in a limitation of the quantum adiabatic theorem and efficient optimization of QAOA parameters. Furthermore, the results suggests that even when sub-optimised, the performance of QAOA on spin glass is equal in performance to Montanari's classical algorithm in solving the mean field spin glass problem, the best known classical algorithm.
- Abstract(参考訳): 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化問題のために設計された量子アルゴリズムである。
我々は、Max-$q$-XORSAT の解空間におけるオーバーラップギャップ特性 (OGP) が単調増加関数であるという仮定の下で、QAOA における極限の交換は、OGP によって制限される準最適結果をもたらすことを示す。
さらに,純$q$-spinモデルに対するQAOAの性能は,大容量正規ハイパーグラフ上でのMax-q$-XORSATと漸近的に一致するため,QAOAが純$q$-spinモデルに対して得られる平均ケース値は,アルゴリズムが無期限に実行しても最適性から外れていることを示す。
このことは、QAOAにおける極限スワップの有効性に対する必要条件は、与えられた組合せ最適化問題における OGP の欠如であることを示している。
これは、OGPを示すハミルトニアンのスペクトルギャップが熱力学の極限で閉じ、量子断熱定理の極限とQAOAパラメータの効率的な最適化をもたらすというものである。
さらに, スピンガラス上でのQAOAの性能は, スピンガラスの平均解法におけるモンタ成の古典的アルゴリズムと同等であることが示唆された。
関連論文リスト
- An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
論文 参考訳(メタデータ) (2023-02-09T07:47:06Z) - 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) - 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) - 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) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。