論文の概要: Multilevel leapfrogging initialization for quantum approximate
optimization algorithm
- arxiv url: http://arxiv.org/abs/2306.06986v3
- Date: Sun, 30 Jul 2023 06:16:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-01 20:44:25.177570
- Title: Multilevel leapfrogging initialization for quantum approximate
optimization algorithm
- Title（参考訳）: 量子近似最適化アルゴリズムのための多重レベル跳躍初期化
- Authors: Xiao-Hui Ni, Bin-Bin Cai, Hai-Ling Liu, Su-Juan Qin, Fei Gao and
Qiao-Yan Wen
- Abstract要約: 量子強化学習に拡張可能なマルチレベル跳躍学習(M-Leap)を提案する。
また,最適化を初期化するためのマルチレベル跳躍補間戦略(MLI)を提案する。
準オプティマを少数のコストで見つける効率で、我々の方法は他の量子アルゴリズムに光を放つかもしれない。
- 参考スコア（独自算出の注目度）: 4.501305807267216
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a prospective hybrid
quantum-classical algorithm widely used to solve combinatorial optimization
problems. However, the external parameter optimization required in QAOA tends
to consume extensive resources to find the optimal parameters of the
parameterized quantum circuit, which may be the bottleneck of QAOA. To meet
this challenge, we first propose multilevel leapfrogging learning (M-Leap) that
can be extended to quantum reinforcement learning, quantum circuit design, and
other domains. M-Leap incrementally increases the circuit depth during
optimization and predicts the initial parameters at level $p+r$ ($r>1$) based
on the optimized parameters at level $p$, cutting down the optimization rounds.
Then, we propose a multilevel leapfrogging-interpolation strategy (MLI) for
initializing optimizations by combining M-Leap with the interpolation
technique. We benchmark its performance on the Maxcut problem. Compared with
the Interpolation-based strategy (INTERP), MLI cuts down at least half the
number of rounds of optimization for the classical outer learning loop.
Remarkably, the simulation results demonstrate that the running time of MLI is
1/3 of INTERP when MLI gets quasi-optimal solutions. In addition, we present
the greedy-MLI strategy by introducing multi-start, which is an extension of
MLI. The simulation results show that greedy-MLI can get a higher average
performance than the remaining two methods. With their efficiency to find the
quasi-optima in a fraction of costs, our methods may shed light in other
quantum algorithms.
- Abstract（参考訳）: 量子近似最適化アルゴリズム (QAOA) は、組合せ最適化問題の解法として広く用いられているハイブリッド量子古典アルゴリズムである。
しかし、QAOAで必要とされる外部パラメータ最適化は、QAOAのボトルネックとなるパラメータ化量子回路の最適パラメータを見つけるために、広範囲なリソースを消費する傾向にある。
この課題を克服するために,我々はまず,量子強化学習,量子回路設計,その他の領域に拡張可能なマルチレベル跳躍学習(m-leap)を提案する。
m-leapは最適化中に回路の深さを段階的に増加させ、レベル$p$の最適化パラメータに基づいてレベル$p+r$(r>1$)の初期パラメータを予測する。
そこで本稿では,M-Leapと補間手法を組み合わせることで最適化を初期化するためのマルチレベル跳躍補間戦略(MLI)を提案する。
我々は、maxcut問題でパフォーマンスをベンチマークする。
Interpolation-based Strategy (INTERP)と比較して、MLIは古典的な外的学習ループの最適化ラウンドの少なくとも半分を削減している。
シミュレーションの結果、MLIが準最適解を得る場合、MLIの実行時間はInterPの1/3であることが示された。
さらに,MLIの拡張であるマルチスタートを導入することで,greedy-MLI戦略を提案する。
シミュレーションの結果,greedy-MLIは残りの2つの手法よりも平均性能が高いことがわかった。
準オプティマを少数のコストで見つける効率で、我々の方法は他の量子アルゴリズムに光を放つかもしれない。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models [3.390330377512402]
2次元の$(gamma, beta)$サーチを$gamma$より1次元の検索に還元する方法を示し、$beta*$を解析的に計算する。
このアプローチはRecursive QAOA (RQAOA) を用いて検証され、粗い最適化RQAOAと半定値プログラムを一貫して上回る。
論文 参考訳（メタデータ） (2025-01-27T19:00:00Z) - Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
既存の量子処理ユニット(QPU)がマルチレベル戦略においてサブソルバとしてどのように機能するかを実験的に検証する。
完全連結な 82$-qubit Sherrington-Kirkpatrick グラフに対して 10$ の近似解を求める。
量子最適化の結果は古典学と比較して解の質に関して競争力がある。
論文 参考訳（メタデータ） (2024-08-14T20:06:32Z) - Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
双レベル最適化は階層型機械学習問題に対処するための基本的な数学的枠組みとなっている。
従来の勾配に基づく二段階最適化アルゴリズムは、大規模アプリケーションの要求を満たすには不適である。
両レベル最適化のためのメタ勾配の偏りのない近似を実現するための$(textFG)2textU$を導入する。
論文 参考訳（メタデータ） (2024-06-20T08:21:52Z) - LLM as a Complementary Optimizer to Gradient Descent: A Case Study in Prompt Tuning [69.95292905263393]
グラデーションベースとハイレベルなLLMは、協調最適化フレームワークを効果的に組み合わせることができることを示す。
本稿では,これらを相互に補完し,組み合わせた最適化フレームワークを効果的に連携させることができることを示す。
論文 参考訳（メタデータ） (2024-05-30T06:24:14Z) - Localized Zeroth-Order Prompt Optimization [54.964765668688806]
そこで我々は,ZOPO(Localized zeroth-order prompt optimization)という新しいアルゴリズムを提案する。
ZOPOはニューラル・タンジェント・カーネルをベースとしたガウス法を標準ゼロ階次最適化に取り入れ、高速な局所最適探索を高速化する。
注目すべきは、ZOPOは最適化性能とクエリ効率の両方の観点から、既存のベースラインを上回っていることだ。
論文 参考訳（メタデータ） (2024-03-05T14:18:15Z) - Large Language Models as Optimizers [106.52386531624532]
本稿では,大規模言語モデル (LLM) をプロンプトとして活用するためのシンプルで効果的な手法である Prompting (OPRO) を提案する。
各最適化ステップにおいて、LLMは、前述した値を含むプロンプトから新しい解を生成する。
OPROにより最適化された最良のプロンプトは、GSM8Kで最大8%、Big-Bench Hardタスクで最大50%向上することを示した。
論文 参考訳（メタデータ） (2023-09-07T00:07:15Z) - Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover
Problem [4.697039614904225]
量子交互演算子 ansatz (QAOA+) を用いて最小被覆(MEC)問題を解く。
数値計算の結果,アルゴリズムのレベル$p$が低い場合,高い確率で解が得られることがわかった。
また、1量子ビット回転ゲートを$R_Z$で除去することで量子回路を最適化する。
論文 参考訳（メタデータ） (2022-11-28T12:45:52Z) - Min-Max Bilevel Multi-objective Optimization with Applications in
Machine Learning [30.25074797092709]
本稿では,min-maxバイレベル多目的最適化フレームワークを提案する。
表現学習と超目的学習の応用を強調している。
論文 参考訳（メタデータ） (2022-03-03T18:56:13Z) - An Efficient Batch Constrained Bayesian Optimization Approach for Analog
Circuit Synthesis via Multi-objective Acquisition Ensemble [11.64233949999656]
MACE(Multi-objective Acquisition Function Ensemble)を用いた並列化可能なベイズ最適化アルゴリズムを提案する。
提案アルゴリズムは,バッチサイズが15のときの非制約最適化問題に対する微分進化(DE)と比較して,シミュレーション全体の時間を最大74倍削減することができる。
制約付き最適化問題に対して,提案アルゴリズムは,バッチサイズが15の場合に,重み付き改善に基づくベイズ最適化(WEIBO)アプローチと比較して最大15倍の高速化を実現することができる。
論文 参考訳（メタデータ） (2021-06-28T13:21:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。