論文の概要: The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms
- arxiv url: http://arxiv.org/abs/2609.35131v1
- Date: Mon, 28 Sep 2026 13:23:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-02 16:42:07.59078
- Title: The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms
- Title（参考訳）: オーバーラップギャップ特性:量子と量子に着想を得た近似最適化アルゴリズムの分離
- Abstract要約: 平均場近似最適化アルゴリズム(MF-AOA)は、オーバーラップギャップ特性(OGP)を示す問題に対して任意の近似解を与えることができない
我々は,MF-AOA と有限メモリ近似メッセージパッシング (AMP) アルゴリズムを関連付け,OGP の性能に制限があることを示す。
- 参考スコア（独自算出の注目度）: 6.84584651040137
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we prove that the Mean-Field Approximate Optimization Algorithm (MF-AOA), a quantum-inspired classical algorithm of the Quantum Approximate Optimization Algorithm (QAOA), is unable to give arbitrary near optimal solution for problems exhibiting the Overlap Gap Property (OGP). We show this by relating the MF-AOA to finite-memory Approximate Message Passing (AMP) algorithms, which are known to be limited in performance by the OGP. Thus, our paper argues that problems exhibiting the OGP are one such instance where the QAOA can outperform the MF-AOA and AMP algorithms in general. We supplement this by numerically simulating the performance of the QAOA on instances of Max-$4$-XORSAT that exhibit the OGP and find that the QAOA is able to surpass the barrier, while our finite-size scaling analysis favors a super-polynomial over a polynomial depth dependence. In addition, we observe a non-differentiable point in the performance of the QAOA near by the OGP barrier, where the optimal QAOA parameters change from an adiabatic to a non-adiabatic schedule.
- Abstract（参考訳）: 本稿では、量子近似最適化アルゴリズム(QAOA)の量子インスパイアされた古典的アルゴリズムである平均近似最適化アルゴリズム(MF-AOA)が、オーバーラップギャップ特性(OGP)を示す問題に対して任意の近似解を与えることができないことを示す。
我々は,MF-AOA と有限メモリ近似メッセージパッシング (AMP) アルゴリズムを関連付け,OGP の性能に制限があることを示す。
そこで本論文では,OGP を示す問題は,QAOA が MF-AOA と AMP のアルゴリズムを全般的に上回るような事例である,と論じている。
我々は、OGPを示すMax-$4$-XORSATのインスタンス上でのQAOAの性能を数値的にシミュレートし、QAOAが障壁を越えることができることを示す。
さらに, 最適QAOAパラメータがアディベートから非アディベイトスケジュールに変化するOGPバリア近傍のQAOAの性能において, 微分不可能な点を観測した。
関連論文リスト
- Structured Parameterization and Non-Stabilizerness in Hypergraph QAOA [0.0]
我々は$k$-interaction-angle 量子近似最適化アルゴリズム(k$A-QAOA)を紹介する。
我々は、より表現力のある多角量子近似アルゴリズム(MA-QAOA)に匹敵する近似比を$k$A-QAOAで達成していることを示す。
その結果、$k$A-QAOAはMA-QAOAに匹敵する近似比を達成できるが、機能評価は著しく少なく、量子リソース消費を低減できることを示した。
論文 参考訳（メタデータ） (2026-05-02T22:12:18Z) - An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
チュートリアルは変分量子回路とQUBO問題の概要から始まる。
次に、ハミルトンの定式化、ゲート分解、サンプル応用など、QAOAの詳細を探索する。
このチュートリアルはこれらの概念を高階ハミルトニアンに拡張し、関連する対称性と回路構成について議論する。
論文 参考訳（メタデータ） (2025-11-23T09:54:20Z) - The Overlap Gap Property limits limit swapping in the QAOA [5.578103948136372]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化問題(COP)のために設計された量子アルゴリズムである。
また, スピングラス型COPの局所アルゴリズムが, 基礎となるErd"os-R'enyiハイパーグラフの対数深さでの性能に制限されている場合, ランダム正規ハイパーグラフも同様に制限されることを示す。
論文 参考訳（メタデータ） (2024-04-09T07:45:06Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。
この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。
我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文 参考訳（メタデータ） (2023-06-15T15:28:12Z) - Mean-Field Approximate Optimization Algorithm [0.17812428873698405]
平均場近似最適化アルゴリズム(平均場AOA)は、QAOAの量子進化を古典的なスピン力学に置き換えることで開発された。
我々は,シェリントン・カークパトリック(SK)モデルにおけるQAOAとパーティション問題を比較検討した。
そこで本アルゴリズムは,古典的に解けない問題から解ける最適化問題を記述するためのツールとして機能する。
論文 参考訳（メタデータ） (2023-03-01T08:47:06Z) - Quantum Approximate Optimization Algorithm Based Maximum Likelihood
Detection [80.28858481461418]
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
論文 参考訳（メタデータ） (2021-07-11T10:56:24Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳（メタデータ） (2021-02-12T23:12:09Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - A Dynamical Systems Approach for Convergence of the Bayesian EM
Algorithm [59.99439951055238]
我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。
本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。
高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
論文 参考訳（メタデータ） (2020-06-23T01:34:18Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。