論文の概要: Amplitude Amplification for Optimization via Subdivided Phase Oracle
- arxiv url: http://arxiv.org/abs/2205.00602v1
- Date: Mon, 2 May 2022 01:14:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 20:55:24.268126
- Title: Amplitude Amplification for Optimization via Subdivided Phase Oracle
- Title(参考訳): 分割位相Oracleによる振幅増幅の最適化
- Authors: Naphan Benchasattabuse, Takahiko Satoh, Michal Hajdu\v{s}ek, Rodney
Van Meter
- Abstract要約: 振幅増幅の修正版を用いて最適化問題を解くアルゴリズムを提案する。
数値シミュレーションにより, 対象値の正規分布, 歪正規分布, 指数分布分布に対して, 最適解の確率を増幅するアルゴリズムが有効であることを示す。
- 参考スコア(独自算出の注目度): 0.9176056742068814
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an algorithm using a modified variant of amplitude amplification
to solve combinatorial optimization problems via the use of a subdivided phase
oracle. Instead of dividing input states into two groups and shifting the phase
equally for all states within the same group, the subdivided phase oracle
changes the phase of each input state uniquely in proportion to their objective
value. We provide visualization of how amplitudes change after each iteration
of applying the subdivided phase oracle followed by conventional Grover
diffusion in the complex plane. We then show via numerical simulation that for
normal, skew normal, and exponential distribution of objective values, the
algorithm can be used to amplify the probability of measuring the optimal
solution to a significant degree independent of the search space size. In the
case of skew normal and exponential distributions, this probability can be
amplified to be close to unity, making our algorithm near deterministic. We
then modify our algorithm in order to demonstrate how it can be extended to a
broader set of objective value distributions. Finally, we discuss the speedup
compared to classical schemes using the query complexity model, and show that
our algorithm offers a significant advantage over these classical approaches.
- Abstract(参考訳): 本稿では, 振幅増幅の修正版を用いて, 分割位相オラクルを用いて組合せ最適化問題を解くアルゴリズムを提案する。
入力状態を2つのグループに分割し、同じグループ内の全ての状態に対して等しく位相をシフトする代わりに、サブ分割されたフェーズオラクルは、それぞれの入力状態の位相を目的値に比例して一意に変更する。
複素平面における従来のグローバー拡散に続いて, 分割位相オラクルを適用した各繰り返しの振幅の変化を可視化する。
次に, 対象値の正規分布, 歪正規分布, 指数分布の数値シミュレーションにより, 最適解の測定確率を探索空間サイズに依存しないかなりの程度に増幅できることを示す。
スキュー正規分布と指数分布の場合、この確率は一意に近いように増幅することができ、アルゴリズムは決定論的に近い。
次に、より広範な目的値分布にどのように拡張できるかを示すために、アルゴリズムを変更します。
最後に,クエリ複雑性モデルを用いた古典的スキームと比較して,高速化について論じるとともに,従来の手法に対してアルゴリズムが大きなアドバンテージを与えることを示す。
関連論文リスト
- Enhancing Grover's Search Algorithm: A Modified Approach to Increase the
Probability of Good States [0.0]
本稿では,Grover検索アルゴリズムを改良し,アルゴリズムの初期イテレーションにおける良好な状態を見つける可能性を高める。
これは (y+z) 軸のまわりに回転ゲートを組み込むことを提案し、その位相は初期反復時の微分器出力の微分から数学的に決定される。
以上の結果から,目標状態の特定に要する反復回数が約28%減少し,全体のプロセスが高速化されたことが示唆された。
論文 参考訳(メタデータ) (2024-01-31T04:55:06Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳(メタデータ) (2024-01-29T02:08:40Z) - Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。
本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
論文 参考訳(メタデータ) (2023-06-27T08:15:28Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳(メタデータ) (2023-06-21T17:03:22Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳(メタデータ) (2023-02-13T19:57:17Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality [8.771678221101368]
我々は、アルゴリズムが使用するデータ分布が反復列に沿って進化する決定依存問題に対する近似を解析する。
軽微な仮定の下では、アルゴリズムの反復と解の偏差は正規であることを示す。
また,平均化アルゴリズムの性能は局所的に最小限であることを示す。
論文 参考訳(メタデータ) (2022-07-09T01:44:17Z) - Grover's Algorithm with Diffusion and Amplitude Steering [0.0]
多次元ヒルベルト空間の任意の部分空間を探索するグロバーアルゴリズムの一般化を提案する。
また、データベース要素間の高次相関を考慮に入れた一般化Groverのアルゴリズムを概説する。
論文 参考訳(メタデータ) (2021-10-21T14:15:32Z) - Sharp global convergence guarantees for iterative nonconvex
optimization: A Gaussian process perspective [30.524043513721168]
回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。
決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。
我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
論文 参考訳(メタデータ) (2021-09-20T21:48:19Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳(メタデータ) (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。