論文の概要: A Recursive Lower Bound on the Energy Improvement of the Quantum Approximate Optimization Algorithm

• arxiv url: http://arxiv.org/abs/2405.10125v2
• Date: Mon, 18 Nov 2024 14:13:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-19 14:28:50.373931
• Title: A Recursive Lower Bound on the Energy Improvement of the Quantum Approximate Optimization Algorithm
• Title（参考訳）: 量子近似最適化アルゴリズムのエネルギー改善に関する再帰的下界
• Authors: Raimel A. Medina, Maksym Serbyn,
• Abstract要約: 我々は、遷移状態に関するコスト関数の解析的拡張を用いて、深いQAOAに関する洞察を得る。 計算の結果, 得られたQAOAコスト関数の有界値と真値が, 層数$p$に比例して指数関数的に減少していることが判明した。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) uses a quantum computer to implement a variational method with $2p$ layers of alternating unitary operators, optimized by a classical computer to minimize a cost function. While rigorous performance guarantees exist for the QAOA at small depths $p$, the behavior at large depths remains less clear, though simulations suggest exponentially fast convergence for certain problems. In this work, we gain insights into the deep QAOA using an analytic expansion of the cost function around transition states. Transition states are constructed recursively: from a local minima of the QAOA with $p$ layers we obtain transition states of the QAOA with $p+1$ layers, which are stationary points characterized by a unique direction of negative curvature. We construct an analytic estimate of the negative curvature and the corresponding direction in parameter space at each transition state. Expansion of the QAOA cost function along the negative direction to the quartic order gives a lower bound of the QAOA cost function improvement. We provide physical intuition behind the analytic expressions for the local curvature and quartic expansion coefficient. Our numerical study confirms the accuracy of our approximations, and reveals that the obtained bound and the true value of the QAOA cost function gain have a characteristic exponential decrease with the number of layers $p$, with the bound decreasing more rapidly. Our study establishes an analytical method for recursively studying the QAOA applicable in the regime of high circuit depth.
• Abstract（参考訳）: 量子近似最適化アルゴリズム (QAOA) は、量子コンピュータを用いて、コスト関数を最小限に抑えるために古典的コンピュータによって最適化された2p$の交互ユニタリ演算子からなる変分法を実装している。 小さな深さでQAOAに厳密な性能保証は存在するが、大きな深さでの挙動は明らかになっていないが、シミュレーションは特定の問題に対して指数関数的に高速な収束を示唆している。 本研究では, 遷移状態に関するコスト関数の解析的拡張を用いて, 深部QAOAの洞察を得る。 遷移状態は再帰的に構成される: QAOA の局所ミニマから$p+1$ の層を持つ QAOA の遷移状態を得る。 本研究では,各遷移状態におけるパラメータ空間における負曲率と対応する方向の解析的推定値を構築する。 QAOAコスト関数は、クォート次数に対する負の方向に沿って拡張され、QAOAコスト関数の改善の低い境界となる。 局所曲率とクォート膨張係数の解析式の背後にある物理的直観を提供する。 計算の結果,得られたQAOAコスト関数の有界値と真値が,層数$p$に比例して指数関数的に減少し,バウンドが急速に減少することが明らかとなった。 本研究は, 高回路深度状態に適用可能なQAOAを再帰的に研究するための解析手法を確立する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Efficient Quantum Gradient and Higher-order Derivative Estimation via Generalized Hadamard Test [2.5545813981422882]
  パラメータ化量子回路(PQC)の動作を理解するためには、勾配に基づく手法が不可欠である 有限差分、シフト規則、アダマール試験、直接アダマール試験などの既存の勾配推定法は、特定のPQCに対して最適な勾配回路を得ることが多い。 本稿では,一階勾配推定法に適用したフレキシブル・アダマールテスト(Flexible Hadamard Test)を提案する。 また、PQ内の個々のパラメータに対する最適勾配推定手法を適応的に選択する統一勾配法である量子自動微分(QAD)を導入する。
  論文  参考訳（メタデータ） (2024-08-10T02:08:54Z)
• Linearly simplified QAOA parameters and transferability [0.6834295298053009]
  量子近似アルゴリズム最適化(QAOA)は、量子コンピュータを用いて最適化問題を解く方法を提供する。 ランダムイジングモデルのインスタンスと最大カット問題のインスタンスに対して得られた数値結果について述べる。
  論文  参考訳（メタデータ） (2024-05-01T17:34:32Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。 i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。 その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
  論文  参考訳（メタデータ） (2024-04-18T16:46:08Z)
• Trainability Barriers in Low-Depth QAOA Landscapes [0.0]
  QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための変分量子アルゴリズムである。 以前の結果から、小さなパラメータの固定数の解析性能が保証された。 本研究は,近年の数値研究の焦点である中間体制における訓練の難しさについて考察する。
  論文  参考訳（メタデータ） (2024-02-15T18:45:30Z)
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement [1.720510639137902]
  量子近似最適化アルゴリズム (QAOA) は変分量子アルゴリズムであり、量子コンピュータは変分ユニタリ演算子の$p$層からなる変分アンサッツを実装している。 本稿では,QAOAを$p+1$で局所最小のQAOAを$p$で使用するQAOAの遷移状態の解析的構成について述べる。
  論文  参考訳（メタデータ） (2022-09-02T16:40:21Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Quantum annealing initialization of the quantum approximate optimization algorithm [0.0]
  量子近似最適化アルゴリズム(QAOA)は、近い将来の量子アルゴリズムである。 QAOAで必要とされる外部パラメータの最適化は、パフォーマンスのボトルネックになる可能性がある。 本研究では、ランダムグラフ上のMaxCut問題に適用されたQAOAの最適化景観を可視化する。
  論文  参考訳（メタデータ） (2021-01-14T17:45:13Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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