論文の概要: A Recursive Lower Bound on the Energy Improvement of the Quantum Approximate Optimization Algorithm
- arxiv url: http://arxiv.org/abs/2405.10125v1
- Date: Thu, 16 May 2024 14:24:37 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-17 14:02:34.222344
- Title: A Recursive Lower Bound on the Energy Improvement of the Quantum Approximate Optimization Algorithm
- Title（参考訳）: 量子近似最適化アルゴリズムのエネルギー改善に関する再帰的下界
- Authors: Raimel A. Medina, Maksym Serbyn,
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)は、量子コンピュータを用いて、交互ユニタリ演算子の2p$層を持つ変分法を実装している。
遷移状態に関するコスト関数の解析的拡張を用いて, 深部QAOAの洞察を得る。
計算の結果, 得られたQAOAコスト関数の有界値と真値が, 層数$p$に比例して指数関数的に減少することが明らかとなった。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- 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 in a recursive manner: from the 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. The 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 that is applicable in the regime of high circuit depth.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、量子コンピュータを用いて、コスト関数を最小限に抑えるために古典的コンピュータによって最適化された2p$の交互ユニタリ演算子からなる変分法を実装している。
小さな深さでQAOAに厳密な性能保証は存在するが、大きな深さでの挙動は明らかになっていないが、シミュレーションは特定の問題に対して指数関数的に高速な収束を示唆している。
本研究では, 遷移状態に関するコスト関数の解析的拡張を用いて, 深部QAOAの洞察を得る。
遷移状態は再帰的に構成される: QAOA の局所最小値から$p+1$ の層を持つ QAOA の遷移状態を得る。
本研究では,各遷移状態におけるパラメータ空間における負曲率と対応する方向の解析的推定値を構築する。
QAOAコスト関数をクォート次数に負の方向に沿って拡張することで、QAOAコスト関数の低いバウンドが得られる。
局所曲率とクォート膨張係数の解析式の背後にある物理的直観を提供する。
数値計算により,得られたQAOAコスト関数の有界値と真値が,各層数$p$に比例して指数関数的に減少し,バウンドが急速に減少することが明らかとなった。
本研究は, 高回路深度状態に適用可能なQAOAを再帰的に研究するための解析手法を確立する。
関連論文リスト
- 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 Minimiax 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) - Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled
Gradient Descent, Even with Overparameterization [48.65416821017865]
この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。
低ランク物体の条件数に依存しない定数速度で直線的に収束する。
様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
論文 参考訳（メタデータ） (2023-10-09T21:16:57Z) - 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) - Avoiding Barren Plateaus with Classical Deep Neural Networks [0.0]
VQA(Vari quantum algorithm)は、ノイズ中間スケール量子デバイス時代において最も有望なアルゴリズムの一つである。
VQAは、化学シミュレーション、最適化問題、量子ニューラルネットワークなど、様々なタスクに適用される。
本稿では,VQA入力パラメータにおける古典的ニューラルネットワークの利用がバレンプラトー現象を緩和する方法について報告する。
論文 参考訳（メタデータ） (2022-05-26T15:14:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。