論文の概要: The QAOA gets stuck starting from a good classical string
- arxiv url: http://arxiv.org/abs/2207.05089v2
- Date: Fri, 7 Jul 2023 14:17:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-10 16:15:53.410143
- Title: The QAOA gets stuck starting from a good classical string
- Title（参考訳）: QAOAは、良い古典的な文字列から始まり、立ち往生する
- Authors: Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard, Eugene Tang
- Abstract要約: 本稿では,QAOAを初期化する手法が劇的に失敗し,コスト関数の改善がほとんど,あるいは全く得られない数値実験を報告する。
我々は、私たちのネガティブな結果は、ウォームスタートQAOAの単純な導入にのみ適用され、文献の他のアプローチには適用されないことを強調する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is designed to maximize
a cost function over bit strings. While the initial state is traditionally a
uniform superposition over all strings, it is natural to try expediting the
QAOA: first use a classical algorithm to produce some good string, and then run
the standard QAOA starting in the computational basis state associated with
that string. Here we report numerical experiments that show this method of
initializing the QAOA fails dramatically, exhibiting little to no improvement
of the cost function. We provide multiple analytical arguments for this lack of
improvement, each of which can be made rigorous under different regimes or
assumptions, including at nearly linear depths. We emphasize that our negative
results only apply to our simple incarnation of the warm-start QAOA and may not
apply to other approaches in the literature. We hope that our theoretical
analysis will inform future algorithm design.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)はビット列上のコスト関数を最大化するように設計されている。
初期状態は伝統的に全ての文字列に対する一様重ね合わせであるが、QAOAを高速化しようとするのが自然である:まず古典的アルゴリズムを使って良い文字列を生成し、次にその文字列に関連する計算基底状態から標準QAOAを実行する。
本稿では,QAOAを初期化する手法が劇的に失敗し,コスト関数の改善がほとんど,あるいは全く見られない数値実験を報告する。
この改善の欠如について複数の分析的議論を行い、それぞれが線形な深さを含む異なるレジームや仮定の下で厳密に扱うことができる。
我々は、私たちのネガティブな結果は、ウォームスタートQAOAの単純な導入にのみ適用され、文献の他のアプローチには適用されないことを強調する。
我々の理論的解析が将来のアルゴリズム設計に役立てることを願っている。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - ADAPT-QAOA with a classically inspired initial state [0.0]
我々は古典近似アルゴリズムにインスパイアされた初期状態でADAPT-QAOAを開始することを提案する。
このアルゴリズムは,従来のQAOAやADAPT-QAOAと同等の精度を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-15T01:12:12Z) - Alignment between Initial State and Mixer Improves QAOA Performance for
Constrained Optimization [11.445200448951072]
量子交互演算子 ansatz (QAOA) は断熱アルゴリズムと強い関係を持つ。
本稿では, 断熱アルゴリズムの直感がQAOA初期状態を選択するタスクに適用できることを実証する。
論文 参考訳（メタデータ） (2023-05-05T21:54:28Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T17:13:45Z) - Iterative-Free Quantum Approximate Optimization Algorithm Using Neural
Networks [20.051757447006043]
そこで本稿では,ニューラルネットワークを用いて与えられた問題に対して,より優れたパラメータを求めるための実践的手法を提案する。
我々の手法は一貫して収束し、最終結果も最高速である。
論文 参考訳（メタデータ） (2022-08-21T14:05:11Z) - Planning and Learning with Adaptive Lookahead [74.39132848733847]
ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。
近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。
本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
論文 参考訳（メタデータ） (2022-01-28T20:26:55Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - Bridging Classical and Quantum with SDP initialized warm-starts for QAOA [4.76507354067301]
本稿では,QAOAをグラフ内のすべての可能なカットの偏重重ね合わせで初期化する,古典的な前処理ステップを紹介する。
我々は、QAOA-Warmと呼ばれるこのQAOAの変種が、トレーニング時間が少なく、低い回路深度で標準QAOAより優れていることを示す。
論文 参考訳（メタデータ） (2020-10-27T02:57:22Z) - Evaluation of QAOA based on the approximation ratio of individual
samples [0.0]
我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、いくつかの古典的代替品と比較する。
QAOA計算複雑性理論のガイダンスが進化しているため、量子的優位性を求めるためのフレームワークを利用する。
論文 参考訳（メタデータ） (2020-06-08T18:00:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。