Classical-Quantum Algorithm for Solving Stochastic Programs

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 γ^{dT}\mathrm{polylog}(N,(T/\varepsilon)^{d}))$ , where $\varepsilon$ is the accuracy of the solution, $T$ is the time horizon, and $γ$ 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 γ^{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 $γ=1$ .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 γ^{dT}\mathrm{polylog}(N,(T/\varepsilon)^{d}))$, where $\varepsilon$ is the accuracy of the solution, $T$ is the time horizon, and $γ$ 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 γ^{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 $γ=1$.

arXiv:2011.11654Nov 23, 20204 citations

Quantum stochastic optimization

Bruno Apolloni, C. Carvalho, D. de Falco

Stochastic Processes and their ApplicationsDec 1, 1989211 citations

A Quantum Approach for Stochastic Constrained Binary Optimization

Sarthak Gupta, Vassilis Kekatos

Analytical and practical evidence indicates the advantage of quantum computing solutions over classical alternatives. Quantum-based heuristics relying on the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) have been shown numerically to generate high-quality solutions to hard combinatorial problems, yet incorporating constraints to such problems has been elusive. To this end, this work puts forth a quantum heuristic to cope with stochastic binary quadratically constrained quadratic programs (QCQP). Identifying the strength of quantum circuits to efficiently generate samples from probability distributions that are otherwise hard to sample from, the variational quantum circuit is trained to generate binaryvalued vectors to approximately solve the aforesaid stochastic program. The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks. Tests on several synthetic problem instances using a quantum simulator corroborate the near-optimality and feasibility of the method, and its potential to generate feasible solutions for the deterministic QCQP too.Analytical and practical evidence indicates the advantage of quantum computing solutions over classical alternatives. Quantum-based heuristics relying on the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) have been shown numerically to generate high-quality solutions to hard combinatorial problems, yet incorporating constraints to such problems has been elusive. To this end, this work puts forth a quantum heuristic to cope with stochastic binary quadratically constrained quadratic programs (QCQP). Identifying the strength of quantum circuits to efficiently generate samples from probability distributions that are otherwise hard to sample from, the variational quantum circuit is trained to generate binaryvalued vectors to approximately solve the aforesaid stochastic program. The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks. Tests on several synthetic problem instances using a quantum simulator corroborate the near-optimality and feasibility of the method, and its potential to generate feasible solutions for the deterministic QCQP too.

arXiv:2301.01443IEEE International Conference on Acoustics Speech and Signal ProcessingMay 5, 20234 citations

Quantum and Stochastic Programs of Bounded Width

Chris Pollett, Farid Mansurovich Ablayev, Cristopher Moore

Electronic colloquium on computational complexityJan 1, 20020 citations

Finding stable models via quantum computation.

DAVID A. MEYER, James Pommersheim, Jeffrey B. Remmel

Quantum computers have the potential to out-perform classical computers—certain quantum algorithms run much faster than any known alternative classical algorithm. For example, Grover showed that a quantum computer can search an unordered list of N items in time O ( √ N), providing a quadratic speed-up over the classical algorithm. In this paper, we show that we can modify Grover’s search algorithm to give an algorithm that finds stable models of an Answer Set Program with a similar quadratic improvement over the classical algorithm. Marek and Remmel showed that Answer Set Programming (ASP) programs can uniformly solve all NP-search problems, so our quantum algorithm to find stable models of ASP programs also solves all NP-search problems. It follows that Answer Set Programming could provide a programming language for quantum computation.Quantum computers have the potential to out-perform classical computers—certain quantum algorithms run much faster than any known alternative classical algorithm. For example, Grover showed that a quantum computer can search an unordered list of N items in time O ( √ N), providing a quadratic speed-up over the classical algorithm. In this paper, we show that we can modify Grover’s search algorithm to give an algorithm that finds stable models of an Answer Set Program with a similar quadratic improvement over the classical algorithm. Marek and Remmel showed that Answer Set Programming (ASP) programs can uniformly solve all NP-search problems, so our quantum algorithm to find stable models of ASP programs also solves all NP-search problems. It follows that Answer Set Programming could provide a programming language for quantum computation.

Non-Monotonic ReasoningJan 1, 20042 citations

Hybrid Quantum-Classical Dynamic Programming Algorithm

Chih-Chieh Chen, Kodai Shiba, Masaru Sogabe +2 more

Advances in intelligent systems and computingJan 1, 20211 citation

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 γ^{dT}\mathrm{polylog}(N,(T/\varepsilon)^{d}))

, where

\varepsilon

is the accuracy of the solution,

T

is the time horizon, and

γ

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 γ^{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

γ=1