論文の概要: 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 15:35:37.172251
• 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:
• 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次改良である。

関連論文リスト

• A Quantum Approximate Optimization Algorithm for Local Hamiltonian Problems [0.0]
  局所ハミルトン問題(Local Hamiltonian Problems、LHP)は、多体量子系において計算完全で物理的に関係のある重要な問題である。 我々は、ハミルトニアン量子近似最適化アルゴリズム(HamQAOA)と呼ばれる量子近似を提案し、解析する。 以上の結果から, 線形深度HamQAOAは, 1次元反強磁性ハイゼンベルクスピン鎖の正確な基底状態を決定論的に生成できることが示唆された。
  論文  参考訳（メタデータ） (2024-12-12T12:22:08Z)
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters [0.0]
  より高階のCD補正により、手前の問題の正確な解により早く収束できることが示される。 しかし、この結果を達成するのに必要な自由パラメータの総数は、分析された特定のQAOA変種とは独立である。
  論文  参考訳（メタデータ） (2023-07-26T10:02:47Z)
• Scaling Limits of Quantum Repeater Networks [62.75241407271626]
  量子ネットワーク(QN)は、セキュアな通信、強化されたセンシング、効率的な分散量子コンピューティングのための有望なプラットフォームである。 量子状態の脆弱な性質のため、これらのネットワークはスケーラビリティの観点から大きな課題に直面している。 本稿では,量子リピータネットワーク(QRN)のスケーリング限界について解析する。
  論文  参考訳（メタデータ） (2023-05-15T14:57:01Z)
• 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)
• 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)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• 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)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。 ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。 この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
  論文  参考訳（メタデータ） (2020-08-03T18:00:05Z)

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

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