論文の概要: Equivalence of Quantum Approximate Optimization Algorithm and Linear-Time Quantum Annealing for the Sherrington-Kirkpatrick Model

• arxiv url: http://arxiv.org/abs/2503.09563v1
• Date: Wed, 12 Mar 2025 17:27:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-13 21:17:52.871724
• Title: Equivalence of Quantum Approximate Optimization Algorithm and Linear-Time Quantum Annealing for the Sherrington-Kirkpatrick Model
• Title（参考訳）: シェリントン・カークパトリックモデルにおける量子近似最適化アルゴリズムと線形時間量子アニーリングの等価性
• Authors: Sami Boulebnane, James Sud, Ruslan Shaydulin, Marco Pistoia,
• Abstract要約: QAOAエネルギーは、2つの条件下での量子アニールを近似し、すなわち、角度が1つの層から次の層に滑らかに変化し、和が定数で束縛されていることを示す。 この結果は,一定の角度と任意の深さの和と,角度の和におけるエネルギーの級数展開によるQAOAエネルギーの新式によって実現された。
• 参考スコア（独自算出の注目度）: 2.0174252910776556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum approximate optimization algorithm (QAOA) and quantum annealing are two of the most popular quantum optimization heuristics. While QAOA is known to be able to approximate quantum annealing, the approximation requires QAOA angles to vanish with the problem size $n$, whereas optimized QAOA angles are observed to be size-independent for small $n$ and constant in the infinite-size limit. This fact led to a folklore belief that QAOA has a mechanism that is fundamentally different from quantum annealing. In this work, we provide evidence against this by analytically showing that QAOA energy approximates that of quantum annealing under two conditions, namely that angles vary smoothly from one layer to the next and that the sum is bounded by a constant. These conditions are known to hold for near-optimal QAOA angles empirically. Our results are enabled by novel formulae for QAOA energy with constant sum of angles and arbitrary depth and the series expansion of energy in sum of angles, which we obtain using the saddle-point method, which may be of independent interest. While our results are limited to the Sherrington-Kirkpatrick (SK) model, we show numerically that the expansion holds for random 2SAT and expect our main results to generalize to other constraint satisfaction problems. A corollary of our results is a quadratic improvement for the bound on depth required to compile Trotterized quantum annealing of the SK model.
• Abstract（参考訳）: 量子近似最適化アルゴリズム (QAOA) と量子アニール (quantum annealing) は、最も一般的な量子最適化ヒューリスティックである。 QAOAは量子アニーリングを近似できることが知られているが、近似はQAOA角が問題サイズ$n$で消えることを要求するが、最適化されたQAOA角は小さな$n$では独立であり、無限大の極限では定数である。 この事実はQAOAが量子アニールと根本的に異なる機構を持っているという民間の信念につながった。 本研究は、QAOAエネルギーが2つの条件下で量子アニールを近似していること、すなわち、角度が1つの層から次の層に滑らかに変化すること、および和が定数で束縛されることを解析的に示すことによって、これに対する証拠を提供する。 これらの条件は、準最適QAOA角を経験的に保つことが知られている。 この結果は,一定の角度と任意の深さの総和を持つQAOAエネルギーの新たな公式と,角度の総和におけるエネルギーの時系列展開によって実現された。 結果はシェリントン・カークパトリック(SK)モデルに限られるが、この拡張がランダムな2SATに対して成り立つことを示し、主要な結果が他の制約満足度問題に一般化されることを期待する。 SKモデルのトロタライズド量子アニールをコンパイルするのに必要となる深さ境界の2次改良である。

関連論文リスト

• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  本稿では,VarQITEが従来の手法に比べて平均最適性ギャップを著しく小さくすることを示す。 ハミルトニアンのスケーリングにより、最適化コストをさらに削減し、収束を加速できることを実証する。
  論文  参考訳（メタデータ） (2025-04-17T03:09:37Z)
• Weighted Approximate Quantum Natural Gradient for Variational Quantum Eigensolver [5.873113584103881]
  変分量子固有解法(VQE)は、近距離量子デバイスを用いた最も顕著なアルゴリズムの1つである。 そこで本研究では,局所ハミルトニアンの$kを前提とした重み付き近似量子自然勾配法(WA-QNG)を提案する。
  論文  参考訳（メタデータ） (2025-04-07T11:18:09Z)
• A quantum algorithm for Khovanov homology [42.6618666851542]
  ホバノフホモロジー(Khovanov homology)は、ジョーンズ位相不変量を分類し、カンノットを認識する結び目であり、4D$超対称ヤン・ミルズ理論において観測可能であると推測されている。 リッチな数学的および物理的重要性にもかかわらず、ホバノフホモロジーの計算複雑性はほとんど不明である。
  論文  参考訳（メタデータ） (2025-01-21T18:54:59Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  我々はこのプロトコルをバイアス場デジタルダイアバティック量子最適化(BF-DCQO)と呼ぶ。 私たちの純粋に量子的なアプローチは、古典的な変分量子アルゴリズムへの依存を排除します。 基底状態の成功確率のスケーリング改善を実現し、最大2桁まで増大する。
  論文  参考訳（メタデータ） (2024-05-22T18:11:42Z)
• Variational-quantum-eigensolver-inspired optimization for spin-chain work extraction [39.58317527488534]
  量子源からのエネルギー抽出は、量子電池のような新しい量子デバイスを開発するための重要なタスクである。 量子源からエネルギーを完全に抽出する主な問題は、任意のユニタリ演算をシステム上で行うことができるという仮定である。 本稿では,変分量子固有解法(VQE)アルゴリズムにインスパイアされた抽出可能エネルギーの最適化手法を提案する。
  論文  参考訳（メタデータ） (2023-10-11T15:59:54Z)
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters [0.0]
  より高階のCD補正により、手前の問題の正確な解により早く収束できることが示される。 しかし、この結果を達成するのに必要な自由パラメータの総数は、分析された特定のQAOA変種とは独立である。
  論文  参考訳（メタデータ） (2023-07-26T10:02:47Z)
• Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate [0.6445605125467572]
  変分量子アルゴリズム (VQA) は、量子ハードウェアへの短期的応用に向けて激しい研究が行われている。 VQA の重要なパラメータは変分アンザッツ' のエンプデプス' である。 与えられたVQAアンザッツの最適深さを近似することは困難であることを示す。
  論文  参考訳（メタデータ） (2022-11-22T19:00:01Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry [10.967081346848687]
  本研究では,量子近似最適化アルゴリズム(QAOA)の性能について検討した。 本稿では,パラメータ化資源であるハミルトンが支援する一般化QAOAを提案する。 我々の研究は、翻訳対称性のないプログラマブル量子プロセッサ上でQAOAを実行する方法である。
  論文  参考訳（メタデータ） (2022-06-06T14:17:58Z)
• Quantum Davidson Algorithm for Excited States [42.666709382892265]
  基底状態と励起状態の両方に対処するために量子クリロフ部分空間(QKS)法を導入する。 固有状態の残余を使ってクリロフ部分空間を拡大し、コンパクトな部分空間を定式化し、正確な解と密接に一致させる。 量子シミュレータを用いて、様々なシステムの励起状態特性を探索するために、新しいQDavidsonアルゴリズムを用いる。
  論文  参考訳（メタデータ） (2022-04-22T15:03:03Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• Shortcuts to Quantum Approximate Optimization Algorithm [2.150418646956503]
  我々は「QAOAへのショートカット」(S-QAOA)と呼ばれる新しいアンサッツを提案する。 S-QAOAは、2体相互作用を多く含み、パラメータ自由を解放することで、ターゲットハミルトン状態へのショートカットを提供する。 MaxCut問題とSherrington-Kirkpatrick(SK)モデルを考えると、YY相互作用が最高の性能を示す。
  論文  参考訳（メタデータ） (2021-12-21T02:24:19Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz [0.4881924950569191]
  我々は、ハミルトン変分アンザッツ(HVA)と呼ばれる量子回路の族を研究する。 HVAは、穏やかまたは完全に欠落したバレン高原や制限された状態空間などの良好な構造特性を示す。 HVAは、環上の修正ハルデン・シャストリー・ハミルトニアンの基底状態に対する正確な近似を見つけることができる。
  論文  参考訳（メタデータ） (2020-08-07T01:28:26Z)

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

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