論文の概要: Recursive greedy initialization of the quantum approximate optimization
algorithm with guaranteed improvement
- arxiv url: http://arxiv.org/abs/2209.01159v2
- Date: Tue, 6 Jun 2023 12:59:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 22:05:51.137278
- Title: Recursive greedy initialization of the quantum approximate optimization
algorithm with guaranteed improvement
- Title(参考訳): 改良を保証した量子近似最適化アルゴリズムの再帰的グリーディ初期化
- Authors: Stefan H. Sack, Raimel A. Medina, Richard Kueng and Maksym Serbyn
- Abstract要約: 量子近似最適化アルゴリズム (QAOA) は変分量子アルゴリズムであり、量子コンピュータは変分ユニタリ演算子の$p$層からなる変分アンサッツを実装している。
本稿では,QAOAを$p+1$で局所最小のQAOAを$p$で使用するQAOAの遷移状態の解析的構成について述べる。
- 参考スコア(独自算出の注目度): 1.720510639137902
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a variational
quantum algorithm, where a quantum computer implements a variational ansatz
consisting of $p$ layers of alternating unitary operators and a classical
computer is used to optimize the variational parameters. For a random
initialization, the optimization typically leads to local minima with poor
performance, motivating the search for initialization strategies of QAOA
variational parameters. Although numerous heuristic initializations exist, an
analytical understanding and performance guarantees for large $p$ remain
evasive. We introduce a greedy initialization of QAOA which guarantees
improving performance with an increasing number of layers. Our main result is
an analytic construction of $2p+1$ transition states - saddle points with a
unique negative curvature direction - for QAOA with $p+1$ layers that use the
local minimum of QAOA with $p$ layers. Transition states connect to new local
minima, which are guaranteed to lower the energy compared to the minimum found
for $p$ layers. We use the GREEDY procedure to navigate the exponentially
increasing with $p$ number of local minima resulting from the recursive
application of our analytic construction. The performance of the GREEDY
procedure matches available initialization strategies while providing a
guarantee for the minimal energy to decrease with an increasing number of
layers $p$.
- Abstract(参考訳): 量子近似最適化アルゴリズム (quantum approximation optimization algorithm,qaoa) は、量子コンピュータが交代ユニタリ作用素の$p$層からなる変分アンサッツを実装し、古典的コンピュータを用いて変分パラメータを最適化する変分量子アルゴリズムである。
ランダム初期化の場合、最適化は通常、性能の悪い局所最小化につながり、QAOA変動パラメータの初期化戦略の探索を動機付ける。
多くのヒューリスティックな初期化が存在するが、大きな$p$に対する解析的理解と性能保証は避けられないままである。
層数の増加による性能向上を保証するQAOAの初期化について述べる。
我々の主な成果は、QAOAが$p+1$層を持つ局所最小のQAOAと$p$層を持つQAOAに対して、2p+1$遷移状態(ユニークな負曲率方向を持つサドル点)の解析的構成である。
遷移状態は新しい局所的ミニマと接続し、これは$p$層で見つかる最小のエネルギーよりも低いエネルギーを保証される。
我々はGREEDY法を用いて,解析構造の再帰的適用による局所最小値$p$の指数関数的増加をナビゲートする。
グリーディプロシージャのパフォーマンスは利用可能な初期化戦略に合致すると同時に、最小エネルギーが$p$の増加とともに減少する保証を提供する。
関連論文リスト
- A Recursive Lower Bound on the Energy Improvement of the Quantum Approximate Optimization Algorithm [0.0]
量子近似最適化アルゴリズム(QAOA)は、量子コンピュータを用いて、交互ユニタリ演算子の2p$層を持つ変分法を実装している。
遷移状態に関するコスト関数の解析的拡張を用いて, 深部QAOAの洞察を得る。
計算の結果, 得られたQAOAコスト関数の有界値と真値が, 層数$p$に比例して指数関数的に減少することが明らかとなった。
論文 参考訳(メタデータ) (2024-05-16T14:24:37Z) - Trainability Barriers in Low-Depth QAOA Landscapes [0.0]
QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための変分量子アルゴリズムである。
以前の結果から、小さなパラメータの固定数の解析性能が保証された。
本研究は,近年の数値研究の焦点である中間体制における訓練の難しさについて考察する。
論文 参考訳(メタデータ) (2024-02-15T18:45:30Z) - Iterative Layerwise Training for Quantum Approximate Optimization
Algorithm [0.39945675027960637]
最適化問題の解法における量子近似最適化アルゴリズム(QAOA)の能力は近年,盛んに研究されている。
本稿では,QAOAによる問題解決における最適化コスト削減の可能性を検討する。
論文 参考訳(メタデータ) (2023-09-24T05:12:48Z) - Using Differential Evolution to avoid local minima in Variational
Quantum Algorithms [0.0]
変分量子アルゴリズム(VQA)は、量子コンピューティングを利用する最も有望なNISQ時代のアルゴリズムの一つである。
本研究の目的は,局所的ミニマ問題や大理石高原問題の影響を回避・低減できる代替最適化手法を検討することである。
論文 参考訳(メタデータ) (2023-03-21T20:31:06Z) - LAWS: Look Around and Warm-Start Natural Gradient Descent for Quantum
Neural Networks [11.844238544360149]
Vari Quantum Algorithm (VQA) は、ノイズ中間スケール量子コンピュータ (NISQ) における有望な性能のために最近注目されている。
パラメータ化量子回路(PQC)上でランダムなパラメータを持つVQAは、勾配が量子ビット数で指数関数的に消えるバレンプラトー(BP)によって特徴づけられる。
本稿では、古典的な1次最適化点から、VQAでよく使われるアルゴリズムの1つである量子自然勾配(QNG)について述べる。
そして、私たちはアンダーラインAroundアンダーラインを提案しました。
論文 参考訳(メタデータ) (2022-05-05T14:16:40Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳(メタデータ) (2022-02-08T07:10:06Z) - Adaptive Multi-Goal Exploration [118.40427257364729]
我々は、AdaGoalが$epsilon$-optimal goal-conditioned policyを学習する目的を達成するためにどのように使えるかを示す。
AdaGoalは、ゴール条件の深い強化学習のための既存の手法の高レベルなアルゴリズム構造に固定されている。
論文 参考訳(メタデータ) (2021-11-23T17:59:50Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳(メタデータ) (2020-10-01T18:14:11Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。