論文の概要: Quantum speedups for stochastic optimization
- arxiv url: http://arxiv.org/abs/2308.01582v2
- Date: Thu, 25 Jul 2024 03:21:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-26 20:06:09.612614
- Title: Quantum speedups for stochastic optimization
- Title(参考訳): 確率最適化のための量子スピードアップ
- Authors: Aaron Sidford, Chenyi Zhang,
- Abstract要約: オラクルに対する量子振動の連続関数を最小化する問題を考察する。
リプシュ・アヴィッツ関数を最小化するための2つの新しい方法を提案する。
- 参考スコア(独自算出の注目度): 18.32349609443295
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of minimizing a continuous function given quantum access to a stochastic gradient oracle. We provide two new methods for the special case of minimizing a Lipschitz convex function. Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in low-dimensional settings. Additionally, we provide quantum algorithms for computing a critical point of a smooth non-convex function at rates not known to be achievable classically. To obtain these results we build upon the quantum multivariate mean estimation result of Cornelissen et al. 2022 and provide a general quantum-variance reduction technique of independent interest.
- Abstract(参考訳): 確率勾配オラクルへの量子アクセスを与えられた連続関数を最小化する問題を考える。
リプシッツ凸関数を最小化するための2つの新しい方法を提案する。
各手法は、古典的に証明不可能な次元対精度トレードオフを求め、低次元設定において1つの手法が漸近的に最適であることを証明した。
さらに、古典的に達成不可能な速度で滑らかな非凸関数の臨界点を計算するための量子アルゴリズムを提供する。
これらの結果を得るために、Cornelissen et al 2022の量子多変量平均推定結果の上に構築し、独立利息の一般的な量子分散低減技術を提供する。
関連論文リスト
- Qubit-efficient quantum combinatorial optimization solver [0.0]
そこで我々は,候補ビット解をより少ない量子ビットの絡み合った波動関数にマッピングすることで,制限を克服する量子ビット効率のアルゴリズムを開発した。
このアプローチは、短期的な中間スケールと将来のフォールトトレラントな小規模量子デバイスに有効である。
論文 参考訳(メタデータ) (2024-07-22T11:02:13Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳(メタデータ) (2024-06-28T02:56:22Z) - Optimal Low-Depth Quantum Signal-Processing Phase Estimation [0.029541734875307393]
本稿では,課題に対して頑健な量子信号生成位相推定アルゴリズムを導入し,最適性能を実現する。
超伝導2量子ビット実験において不要なスワップ角度を推定するために, 従来の標準偏差精度は10~4ドルであった。
我々の結果は量子フィッシャー情報に対して厳密に検証され、2量子ゲート学習の未整合精度を達成するためのプロトコルの能力を確認する。
論文 参考訳(メタデータ) (2024-06-17T10:33:52Z) - A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
本稿では,ギブス分割関数を線形時間で推定する新しい量子アルゴリズムを提案する。
これは、vStefankovivc, Vempala, Vigodaの半周期的なほぼ直線時間で得られる最初のスピードアップである。
論文 参考訳(メタデータ) (2022-07-18T14:41:48Z) - Bayesian Learning of Parameterised Quantum Circuits [0.0]
我々はベイズ後部の近似として古典的最適化の確率論的視点を取り、再定式化する。
ラプラスを用いた最大後点推定に基づく次元縮小戦略について述べる。
量子H1-2コンピュータの実験では、結果として得られる回路は勾配なしで訓練された回路よりも高速でノイズが少ないことが示されている。
論文 参考訳(メタデータ) (2022-06-15T14:20:14Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳(メタデータ) (2021-06-24T20:16:02Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z) - 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) - Measuring Analytic Gradients of General Quantum Evolution with the
Stochastic Parameter Shift Rule [0.0]
本研究では,量子計測から直接最適化される関数の勾配を推定する問題について検討する。
マルチキュービットパラメトリック量子進化の勾配を推定するアルゴリズムを提供する数学的に正確な公式を導出する。
私たちのアルゴリズムは、利用可能な全ての量子ゲートがノイズである場合でも、いくつかの近似で機能し続けています。
論文 参考訳(メタデータ) (2020-05-20T18:24:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。