論文の概要: A Quantum Approximate Optimization Algorithm Based On CNR Operation
- arxiv url: http://arxiv.org/abs/2310.17927v1
- Date: Fri, 27 Oct 2023 06:54:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-30 14:48:31.170248
- Title: A Quantum Approximate Optimization Algorithm Based On CNR Operation
- Title（参考訳）: CNR演算に基づく量子近似最適化アルゴリズム
- Authors: Da You Lv and An Min Wang
- Abstract要約: 本稿では,CNR(Comparison and replacement)の運用について紹介する。
CNRはアルゴリズムの過程で高い対象関数レベルを持つ文字列の確率をレベル別に引き上げる。
乱数インスタンスにおける平均性能の分析を支援するために,機能変数の$X_r$を生成した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces the "comparison and replacement" (CNR) operation and
constructs a pure quantum approximate algorithm for combinatorial optimization
problems which depends on positive integers $p$ and $t$. CNR lifts the
probability of strings with high object function level by level in the process
of algorithm, which ensures the strings approximately maximizing the object
function dominate the probability. We produce a feature variable $X_r$ to
support the analysis about average performance on random instances. When the
number of bits $n$ remains unchanged, the performance of the algorithm improves
with the increase of $p$ directly. And $t$ determines the accuracy and
reliability of CNR. The practical performance of algorithm tends to theoretical
results as $t$ increases. For fixed $p$ and $t$, the algorithm outputs a state
with identical probability distribution of measurement or the corresponding fit
curve for nondegenerate or degenerate instance respectively, which means that,
for universal combinatorial optimization problems, the algorithm always works.
- Abstract（参考訳）: 本稿では, "comparison and replacement" (cnr) 演算を導入し, 正の整数 $p$ と $t$ に依存する組合せ最適化問題に対する純粋量子近似アルゴリズムを構成する。
CNRは、アルゴリズムの過程で高いオブジェクト関数レベルを持つ文字列の確率をレベル別に引き上げ、オブジェクト関数が確率を支配するのをほぼ最大化する。
ランダムインスタンスの平均パフォーマンスの分析をサポートするために、機能変数 $x_r$ を作成します。
ビット数n$が変更されていない場合、アルゴリズムの性能は、直接$p$の増加によって向上する。
そして$t$は、CNRの正確性と信頼性を決定する。
アルゴリズムの実用性能は、$t$が増加するにつれて理論的な結果をもたらす傾向がある。
固定された$p$と$t$の場合、このアルゴリズムは測定の確率分布が同じである状態と、非退化あるいは退化のインスタンスに対して対応する適合曲線をそれぞれ出力する。
関連論文リスト
- 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) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。