論文の概要: A Quantum Approximate Optimization Algorithm Based on CNR Operation
- arxiv url: http://arxiv.org/abs/2310.17927v4
- Date: Thu, 7 Dec 2023 11:22:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-08 18:13:02.361109
- Title: A Quantum Approximate Optimization Algorithm Based on CNR Operation
- Title（参考訳）: CNR演算に基づく量子近似最適化アルゴリズム
- Authors: Da You Lv and An Min Wang
- Abstract要約: 本稿では、比較と置換(CNR)演算を導入し、最適化問題に対する純粋量子近似アルゴリズムを提案する。
最上位の$frac12p$オブジェクト関数値を持つ文字列が、$p$レベルのアルゴリズムの最終的な測定において、支配的確率($1-frac1mathrmeapprox0.6321$)を占めることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces the ``comparison and replacement" (CNR) operation and
propose a general-purposed pure quantum approximate algorithm for combinatorial
optimization problems. The CNR operation can increase the probability of
obtaining a string with high object function value. And our algorithm is
constructed to a $p$-level divide-and-conquer structure with CNR operations to
improve the quality of optimization. For a fixed size problem, the algorithm
performance is improved with the increase of $p$ directly. And the algorithm
performance in application converges to the theoretical case as the number of
ancillary qubits $t$ increases. Furthermore, we demonstrate in theory and
application that for sufficiently general combinatorial optimization problems,
the algorithm can work and output a state with considerable approximation
ratio. Moreover, the string with higher object function can be measured in the
final state with higher probability. To put it further, we prove that the
strings with the top $\frac{1}{2^p}$ object function value occupy the dominant
probability(with lower bound around $1-\frac{1}{\mathrm{e}}\approx0.6321$) in
final measurement after $p$-level algorithm. As an illustration, we show the
results of our algorithm when applied to MAX-2-XOR instances and Gaussian
weighted 2-edge graphs.
- Abstract（参考訳）: 本稿では,<comparison and replacement>(CNR)演算を導入し,組合せ最適化問題に対する汎用純粋量子近似アルゴリズムを提案する。
CNR演算は、高いオブジェクト関数値の文字列を得る確率を高めることができる。
また,提案アルゴリズムはCNR演算による$p$レベルの分割対数構造に構築され,最適化の質が向上する。
固定サイズの問題では、直接$p$の増加によってアルゴリズムの性能が向上する。
そして、アプリケーションにおけるアルゴリズムの性能は、補助量子ビットの数が増加するにつれて理論ケースに収束する。
さらに, 十分一般的な組合せ最適化問題に対して, アルゴリズムが十分に近似した状態の処理と出力が可能であることを理論と応用で示す。
さらに、高いオブジェクト関数を持つ文字列は、高い確率で最終状態で測定することができる。
さらには、$p$ アルゴリズムの最終的な測定において、最高値の$\frac{1}{2^p}$ の文字列が支配的確率(約$-\frac{1}{\mathrm{e}}\approx0.6321$)を占めることを証明する。
図示として、MAX-2-XORインスタンスとガウス重み付き2辺グラフに適用したアルゴリズムの結果を示す。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Recursive Quantum Approximate Optimization Algorithm for the MAX-CUT
problem on Complete graphs [1.90365714903665]
量子近似最適化アルゴリズムは、MAX-CUT問題のような最適化問題を近似的に解くために設計されたハイブリッド量子古典的変分アルゴリズムである。
近い将来の量子応用の可能性にもかかわらず、量子近似最適化アルゴリズムはMAX-CUT問題を解くための制限があることが知られている。
論文 参考訳（メタデータ） (2022-11-28T23:51:02Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Optimizing Optimizers: Regret-optimal gradient descent algorithms [9.89901717499058]
我々は,後悔最適アルゴリズムの存在,一意性,一貫性について検討する。
制御問題に対する一階最適条件を提供することにより、後悔最適アルゴリズムはそれらの力学において特定の構造を満たす必要があることを示す。
それらを近似する高速な数値法を提案し,長期的後悔を直接最適化する最適化アルゴリズムを生成する。
論文 参考訳（メタデータ） (2020-12-31T19:13:53Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z) - Optimal and Practical Algorithms for Smooth and Strongly Convex
Decentralized Optimization [21.555331273873175]
ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。
本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
論文 参考訳（メタデータ） (2020-06-21T11:23:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。