論文の概要: Parameter Setting in Quantum Approximate Optimization of Weighted
Problems
- arxiv url: http://arxiv.org/abs/2305.15201v3
- Date: Thu, 11 Jan 2024 14:02:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-12 11:23:19.776329
- Title: Parameter Setting in Quantum Approximate Optimization of Weighted
Problems
- Title（参考訳）: 重み付き問題の量子近似最適化におけるパラメータ設定
- Authors: Shree Hari Sureshbabu, Dylan Herman, Ruslan Shaydulin, Joao Basso,
Shouvanik Chakrabarti, Yue Sun, and Marco Pistoia
- Abstract要約: 本研究では,重み付き問題の一般的なクラスに適用したQAOAのパラメータ設定を開発する。
まず、重み付けされたMaxCut問題に適用した深さ$p=1$のQAOAに対する最適パラメータを、重み付けの異なる仮定の下で導出する。
第二に、$pgeq 1$ の場合、重み付き MaxCut の QAOA エネルギーランドスケープが、パラメータの単純な再スケーリングの下での未重み付きケースにアプローチすることを証明します。
第三に、重み付きMaxCutの解析結果から着想を得た一般的な再スケーリング手法を提案し、その効果を実証する。
- 参考スコア（独自算出の注目度）: 10.396104620517171
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate
algorithm for solving combinatorial optimization problems on quantum computers.
However, in many cases QAOA requires computationally intensive parameter
optimization. The challenge of parameter optimization is particularly acute in
the case of weighted problems, for which the eigenvalues of the phase operator
are non-integer and the QAOA energy landscape is not periodic. In this work, we
develop parameter setting heuristics for QAOA applied to a general class of
weighted problems. First, we derive optimal parameters for QAOA with depth
$p=1$ applied to the weighted MaxCut problem under different assumptions on the
weights. In particular, we rigorously prove the conventional wisdom that in the
average case the first local optimum near zero gives globally-optimal QAOA
parameters. Second, for $p\geq 1$ we prove that the QAOA energy landscape for
weighted MaxCut approaches that for the unweighted case under a simple
rescaling of parameters. Therefore, we can use parameters previously obtained
for unweighted MaxCut for weighted problems. Finally, we prove that for $p=1$
the QAOA objective sharply concentrates around its expectation, which means
that our parameter setting rules hold with high probability for a random
weighted instance. We numerically validate this approach on general weighted
graphs and show that on average the QAOA energy with the proposed fixed
parameters is only $1.1$ percentage points away from that with optimized
parameters. Third, we propose a general heuristic rescaling scheme inspired by
the analytical results for weighted MaxCut and demonstrate its effectiveness
using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio
optimization problem. Our heuristic improves the convergence of local
optimizers, reducing the number of iterations by 7.4x on average.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、量子コンピュータにおける組合せ最適化問題を解くための主要な候補アルゴリズムである。
しかし、多くの場合、QAOAは計算集約的なパラメータ最適化を必要とする。
パラメータ最適化の課題は、位相演算子の固有値が非整数であり、QAOAエネルギーランドスケープが周期的でない重み付き問題の場合において特に顕著である。
本研究では,重み付き問題の一般クラスに適用したQAOAのパラメータ設定ヒューリスティックスを開発する。
まず、重み付けされたMaxCut問題に適用した深さ$p=1$のQAOAに対する最適パラメータを、重み付けの異なる仮定の下で導出する。
特に、平均的な場合、ゼロに近い最初の局所最適値が世界最適QAOAパラメータを与えるという従来の知恵を厳密に証明する。
第二に、$p\geq 1$ の場合、重み付き MaxCut の QAOA エネルギーランドスケープが、パラメータの単純な再スケーリングの下での未重み付きケースにアプローチすることを証明する。
したがって、未重み付きMaxCutで得られたパラメータを重み付き問題に使用することができる。
最後に、$p=1$のQAOAの目的が期待値に集中していることが証明され、これはパラメータ設定規則がランダムな重み付きインスタンスに対して高い確率で保持されることを意味する。
一般重み付きグラフ上でこのアプローチを数値的に検証し、提案した固定パラメータのQAOAエネルギーが最適化パラメータのQAOAからわずか1.1$%離れていることを示す。
第3に,重み付きmaxcutの解析結果に着想を得た一般ヒューリスティックリスケーリングスキームを提案し,ポートフォリオ最適化問題に適用したxyハミング重み保存ミキサーを用いたqaoaの有効性を示す。
我々のヒューリスティックは局所最適化器の収束を改善し、平均7.4倍のイテレーション数を減らす。
関連論文リスト
- Graph Representation Learning for Parameter Transferability in Quantum Approximate Optimization Algorithm [1.0971022294548696]
量子近似最適化アルゴリズム(QAOA)は、量子拡張最適化による量子優位性を達成するための最も有望な候補の1つである。
本研究では,5種類のグラフ埋め込み手法を適用し,パラメータ転送可能性に対する適切なドナー候補を決定する。
この手法を用いて,パラメータ最適化に要するイテレーション数を効果的に削減し,目標問題に対する近似解を桁違いに高速化する。
論文 参考訳（メタデータ） (2024-01-12T16:01:53Z) - A Parameter Setting Heuristic for the Quantum Alternating Operator
Ansatz [0.0]
本稿では,問題の大きさに応じて異なるコスト値の数が増加する場合に適したパラメータ設定戦略を提案する。
我々は、完全均一性が正確に保持され、状態と期待値の両方を記述する情報が得られるQAOAの古典的同次プロキシを定義する。
最大3ドルのQAOAレベルでは、これまでのグローバルに最適化されたアプローチによって返される近似比にマッチするパラメータを容易に見つけることができます。
論文 参考訳（メタデータ） (2022-11-17T00:18:06Z) - Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
Annealed Importance Smpling (AIS) は、深層生成モデルの難易度を推定するために使われる一般的なアルゴリズムである。
本稿では、フレキシブルな中間分布を持つパラメータAISプロセスを提案し、サンプリングに少ないステップを使用するようにブリッジング分布を最適化する。
我々は, 最適化AISの性能評価を行い, 深部生成モデルの限界推定を行い, 他の推定値と比較した。
論文 参考訳（メタデータ） (2022-09-27T07:58:25Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Parameter Transfer for Quantum Approximate Optimization of Weighted
MaxCut [2.8087801395910525]
与えられたQAOA深度に対して、QAOAパラメータの1つの「典型的」ベクトルを、重み付きMaxCutインスタンスに転送することに成功した。
この移動は、近似比がわずか2.0ポイントの中央値の減少につながる。
論文 参考訳（メタデータ） (2022-01-27T19:54:00Z) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳（メタデータ） (2021-11-01T15:43:36Z) - Parameters Fixing Strategy for Quantum Approximate Optimization
Algorithm [0.0]
そこで本稿では,QAOAをパラメータとして初期化することで,回路深度が大きければ平均で高い近似比を与える手法を提案する。
我々は3つの正則グラフやエルド・オス=ルネニグラフのようなグラフのある種のクラスにおけるマックスカット問題に対する我々の戦略をテストする。
論文 参考訳（メタデータ） (2021-08-11T15:44:16Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳（メタデータ） (2021-02-12T23:12:09Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - 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) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。