論文の概要: Quantum speedups of some general-purpose numerical optimisation
algorithms
- arxiv url: http://arxiv.org/abs/2004.06521v1
- Date: Tue, 14 Apr 2020 14:04:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 08:48:31.062517
- Title: Quantum speedups of some general-purpose numerical optimisation
algorithms
- Title（参考訳）: 汎用数値最適化アルゴリズムの量子スピードアップ
- Authors: Cezar-Mihail Alexandru, Ella Bridgett-Tomkinson, Noah Linden, Joseph
MacManus, Ashley Montanaro and Hannah Morris
- Abstract要約: リプシッツ制約の下での大域的最適化のための多くの手法は、ほぼ四分法的に加速できることを示す。
第2に、準ニュートン最適化アルゴリズムの成分であるバックトラックライン探索を2次に高速化できることを示す。
第三に、Nelder-Meadアルゴリズムの成分は最大$O(sqrtn)$の乗算係数で加速できることを示す。
- 参考スコア（独自算出の注目度）: 0.03078691410268859
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give quantum speedups of several general-purpose numerical optimisation
methods for minimising a function $f:\mathbb{R}^n \to \mathbb{R}$. First, we
show that many techniques for global optimisation under a Lipschitz constraint
can be accelerated near-quadratically. Second, we show that backtracking line
search, an ingredient in quasi-Newton optimisation algorithms, can be
accelerated up to quadratically. Third, we show that a component of the
Nelder-Mead algorithm can be accelerated by up to a multiplicative factor of
$O(\sqrt{n})$. Fourth, we show that a quantum gradient computation algorithm of
Gily\'en et al. can be used to approximately compute gradients in the framework
of stochastic gradient descent. In each case, our results are based on applying
existing quantum algorithms to accelerate specific components of the classical
algorithms, rather than developing new quantum techniques.
- Abstract（参考訳）: 関数 $f:\mathbb{R}^n \to \mathbb{R}$ を最小化するための汎用数値最適化法の量子スピードアップを与える。
まず、リプシッツ制約の下でのグローバル最適化のための多くの手法が、ほぼ量子的に加速できることを示す。
第2に、準ニュートン最適化アルゴリズムの成分であるバックトラックライン探索を2次に高速化できることを示す。
第3に、nelder-meadアルゴリズムの成分を最大乗算係数$o(\sqrt{n})$で高速化できることを示す。
第4に、Gily\'enらによる量子勾配計算アルゴリズムは、確率勾配勾配の枠組みにおけるおよその計算勾配に利用できることを示す。
いずれの場合も、新しい量子技術を開発するのではなく、既存の量子アルゴリズムを適用して古典的アルゴリズムの特定のコンポーネントを加速する。
関連論文リスト
- Denoising Gradient Descent in Variational Quantum Algorithms [0.0]
本稿では,変分量子アルゴリズムの勾配降下に対する雑音の悪影響を緩和するアルゴリズムを提案する。
ランダム化パラメタライズド量子回路におけるアルゴリズムの利点を実証的に示す。
論文 参考訳（メタデータ） (2024-03-06T16:15:25Z) - Pure Quantum Gradient Descent Algorithm and Full Quantum Variational
Eigensolver [0.7149735232319818]
勾配勾配勾配勾配法は広く採用されている最適化法である。
単一オラクル計算のみを必要とする新しい量子ベース勾配計算法を提案する。
我々は量子勾配降下法をうまく実装し、変分量子固有解法(VQE)に適用した。
論文 参考訳（メタデータ） (2023-05-07T05:52:41Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Quantum speedup of leverage score sampling and its application [0.0]
本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。
応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-15T14:40:18Z) - Gradient-Free optimization algorithm for single-qubit quantum classifier [0.3314882635954752]
量子デバイスによるバレンプラトーの影響を克服するために、勾配のない最適化アルゴリズムを提案する。
提案アルゴリズムは分類タスクに対して実証され,Adamを用いた手法と比較される。
提案アルゴリズムはAdamよりも高速に精度を向上できる。
論文 参考訳（メタデータ） (2022-05-10T08:45:03Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Quantum Gradient Algorithm for General Polynomials [5.008814514502094]
問題を最適化するための一般的な戦略であるグラディエントベースのアルゴリズムは、多くの現代の機械学習技術にとって不可欠である。
着飾った振幅で数値を最適化する量子勾配アルゴリズムを提案する。
高次元最適化におけるポテンシャル値について、この量子アルゴリズムは勾配最適化を容易にする。
論文 参考訳（メタデータ） (2020-04-23T11:28:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。