論文の概要: Quantum speedups for convex dynamic programming
- arxiv url: http://arxiv.org/abs/2011.11654v2
- Date: Wed, 17 Mar 2021 07:20:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-23 08:50:57.829002
- Title: Quantum speedups for convex dynamic programming
- Title（参考訳）: 凸動的プログラミングのための量子スピードアップ
- Authors: David Sutter, Giacomo Nannicini, Tobias Sutter, Stefan Woerner
- Abstract要約: 本稿では,凸値関数を用いた動的プログラミング問題を解く量子アルゴリズムを提案する。
提案アルゴリズムは、値関数の量子力学的表現を時間$O(T gammadTmathrmpolylog(N,(T/varepsilon)d))$で出力する。
- 参考スコア（独自算出の注目度）: 6.643082745560234
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a quantum algorithm to solve dynamic programming problems with
convex value functions. For linear discrete-time systems with a $d$-dimensional
state space of size $N$, the proposed algorithm outputs a quantum-mechanical
representation of the value function in time $O(T
\gamma^{dT}\mathrm{polylog}(N,(T/\varepsilon)^{d}))$, where $\varepsilon$ is
the accuracy of the solution, $T$ is the time horizon, and $\gamma$ is a
problem-specific parameter depending on the condition numbers of the cost
functions. This allows us to evaluate the value function at any fixed state in
time $O(T \gamma^{dT}\sqrt{N}\,\mathrm{polylog}(N,(T/\varepsilon)^{d}))$, and
the corresponding optimal action can be recovered by solving a convex program.
The class of optimization problems to which our algorithm can be applied
includes provably hard stochastic dynamic programs. Finally, we show that the
algorithm obtains a quadratic speedup (up to polylogarithmic factors) compared
to the classical Bellman approach on some dynamic programs with continuous
state space that have $\gamma=1$.
- Abstract（参考訳）: 凸値関数を用いて動的プログラミング問題を解く量子アルゴリズムを提案する。
$d$-dimensional state space of size $N$の線形離散時間系に対して、提案アルゴリズムは、時間$O(T \gamma^{dT}\mathrm{polylog}(N,(T/\varepsilon)^{d}))$で値関数の量子力学的表現を出力し、$\varepsilon$は解の精度、$T$は時間地平線、$\gamma$はコスト関数の条件数に依存する問題固有のパラメータである。
これにより、任意の固定状態における値関数を$O(T \gamma^{dT}\sqrt{N}\,\mathrm{polylog}(N,(T/\varepsilon)^{d}))$で評価することができ、対応する最適動作は凸プログラムを解くことで回復することができる。
アルゴリズムを適用可能な最適化問題のクラスには,強固な確率動的プログラムが含まれる。
最後に,連続状態空間が$\gamma=1$のいくつかの動的プログラムに対する古典的ベルマンのアプローチと比較して,アルゴリズムが二次的なスピードアップ(多相因子まで)を得ることを示す。
関連論文リスト
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳（メタデータ） (2023-11-06T16:00:07Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
論文 参考訳（メタデータ） (2022-12-05T19:10:32Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum simulation of real-space dynamics [7.143485463760098]
実空間力学のための量子アルゴリズムの体系的研究を行う。
我々は、量子化学のより高速な実空間シミュレーションを含む、いくつかの計算問題に応用する。
論文 参考訳（メタデータ） (2022-03-31T13:01:51Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。