論文の概要: Evidence that the Quantum Approximate Optimization Algorithm Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case

• arxiv url: http://arxiv.org/abs/2505.07929v1
• Date: Mon, 12 May 2025 18:00:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-14 20:57:54.289136
• Title: Evidence that the Quantum Approximate Optimization Algorithm Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case
• Title（参考訳）: 量子近似最適化アルゴリズムがシェリントン・カークパトリックモデルに有効に最適化する証拠
• Authors: Sami Boulebnane, Abid Khan, Minzhao Liu, Jeffrey Larson, Dylan Herman, Ruslan Shaydulin, Marco Pistoia,
• Abstract要約: Sherrington-Kirkpatrick(SK)モデルは、混乱したシステムを理解するための基盤となるフレームワークである。 量子近似最適化アルゴリズム (Quantum Approximate Optimization Algorithm, QAOA) は、量子最適化アルゴリズムであり、その性能は深さ$p$で単調に向上する。 無限大の極限においてSKモデルに適用されたQAOAを解析し、回路深さ$mathcalO(n/epsilon1.13)$の最適エネルギーに対して1-epsilon$の近似が得られるという数値的な証拠を与える。
• 参考スコア（独自算出の注目度）: 3.4872784636892047
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Sherrington-Kirkpatrick (SK) model serves as a foundational framework for understanding disordered systems. The Quantum Approximate Optimization Algorithm (QAOA) is a quantum optimization algorithm whose performance monotonically improves with its depth $p$. We analyze QAOA applied to the SK model in the infinite-size limit and provide numerical evidence that it obtains a $(1-\epsilon)$ approximation to the optimal energy with circuit depth $\mathcal{O}(n/\epsilon^{1.13})$ in the average case. Our results are enabled by mapping the task of evaluating QAOA energy onto the task of simulating a spin-boson system, which we perform with modest cost using matrix product states. We optimize QAOA parameters and observe that QAOA achieves $\varepsilon\lesssim2.2\%$ at $p=160$ in the infinite-size limit. We then use these optimized QAOA parameters to evaluate the QAOA energy for finite-sized instances with up to $30$ qubits and find convergence to the ground state consistent with the infinite-size limit prediction. Our results provide strong numerical evidence that QAOA can efficiently approximate the ground state of the SK model in the average case.
• Abstract（参考訳）: Sherrington-Kirkpatrick(SK)モデルは、混乱したシステムを理解するための基盤となるフレームワークである。 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、量子最適化アルゴリズムである。 我々は、無限大の極限においてSKモデルに適用されたQAOAを分析し、平均の場合、回路深さ$\mathcal{O}(n/\epsilon^{1.13})$の最適エネルギーに対して$(1-\epsilon)$の近似が得られるという数値的な証拠を与える。 本研究の結果は,QAOAエネルギー評価タスクをスピンボソンシステムのシミュレーションタスクにマッピングすることで実現した。 我々はQAOAパラメータを最適化し、QAOAが無限大の極限において$\varepsilon\lesssim2.2\%$を$p=160$とする。 次に、最適化されたQAOAパラメータを用いて、最大30$ qubitsの有限サイズのインスタンスに対するQAOAエネルギーを評価し、無限大の極限予測と整合した基底状態への収束を求める。 以上の結果から,QAOAが平均ケースにおけるSKモデルの基底状態を効率的に近似できることを示す。

関連論文リスト

• 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)
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization [11.445200448951072]
  量子交互演算子 ansatz (QAOA) は断熱アルゴリズムと強い関係を持つ。 本稿では, 断熱アルゴリズムの直感がQAOA初期状態を選択するタスクに適用できることを実証する。
  論文  参考訳（メタデータ） (2023-05-05T21:54:28Z)
• Quantum Approximate Optimization Algorithm Parameter Prediction Using a Convolutional Neural Network [0.0]
  我々は、深度$p+1$QAOAのパラメータから深度$p+1$QAOAのパラメータを予測する畳み込みニューラルネットワークを構築している。 Max-Cut に対する平均近似比 92735$ 800$ ErdHos-R'enyi を得る。
  論文  参考訳（メタデータ） (2022-11-17T13:20:58Z)
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
  量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。 我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。 約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
  論文  参考訳（メタデータ） (2022-08-14T20:39:48Z)
• Automatic Depth Optimization for Quantum Approximate Optimization Algorithm [26.4589898848196]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、制御パラメータを古典的に最適化したハイブリッドアルゴリズムである。 本稿では,勾配降下に基づく自動アルゴリズムによる制御深度選択について検討する。 提案アルゴリズムは,ランダム検索や経験則の代替として,適切な制御深度を選択するための効率的なツールとして利用できる。
  論文  参考訳（メタデータ） (2022-06-29T05:48:16Z)
• 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)
• 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)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。 そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
  論文  参考訳（メタデータ） (2020-03-11T23:23:29Z)

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

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