Quantum speedups for convex dynamic programming
- URL: http://arxiv.org/abs/2011.11654v2
- Date: Wed, 17 Mar 2021 07:20:50 GMT
- Title: Quantum speedups for convex dynamic programming
- Authors: David Sutter, Giacomo Nannicini, Tobias Sutter, Stefan Woerner
- Abstract summary: We present a quantum algorithm to solve dynamic programming problems with convex value functions.
The proposed algorithm outputs a quantum-mechanical representation of the value function in time $O(T gammadTmathrmpolylog(N,(T/varepsilon)d))$.
- Score: 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$.
Related papers
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
Gradient descent is one of the most basic algorithms for solving continuous optimization problems.
We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$.
We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
arXiv Detail & Related papers (2024-07-04T11:03:48Z) - Quantum speedups for linear programming via interior point methods [1.8434042562191815]
We describe a quantum algorithm for solving a linear program with $n$ inequality constraints on $d$ variables.
Our algorithm speeds up the Newton step in the state-of-the-art interior point method of Lee and Sidford.
arXiv Detail & Related papers (2023-11-06T16:00:07Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.
Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
arXiv Detail & Related papers (2023-02-16T13:57:19Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
We show that quantum algorithms can find an $epsilon$-SOSP with poly-logarithmic,, or exponential number of queries in $d.
We also characterize the domains where quantum algorithms can find an $epsilon$-SOSP with poly-logarithmic,, or exponential number of queries in $d.
arXiv Detail & Related papers (2022-12-05T19:10:32Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Quantum simulation of real-space dynamics [7.143485463760098]
We conduct a systematic study of quantum algorithms for real-space dynamics.
We give applications to several computational problems, including faster real-space simulation of quantum chemistry.
arXiv Detail & Related papers (2022-03-31T13:01:51Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems.
MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
arXiv Detail & Related papers (2021-02-15T07:10:33Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$.
The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
arXiv Detail & Related papers (2020-09-09T18:00:09Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.
The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.
It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
arXiv Detail & Related papers (2020-02-20T17:52:18Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.