We provide several quantum algorithms for continuous optimization that do not require gradient estimation. Instead, we encode the optimization problem into the dynamics of a physical system and coherently simulate the time evolution. We focus on the setting where the objective function can be accessed via a phase oracle. Our first two algorithms can find local optima of a differentiable function f : R N → R by simulating either classical or quantum dynamics with friction via a time-dependent Hamiltonian. We show that for the benchmark problem of optimizing a locally quadratic objective function, these methods require a total of O ( N 2 κ 2 / h x 2 ϵ ) queries to a phase oracle to find an ϵ -approximate local optimum, where κ is the condition number of the Hessian matrix and h x is the discretization spacing. In contrast, we show that methods based on gradient descent require O ( N 3 / 2 ( 1 / ϵ ) κ log ( 3 ) / 4 ) queries. This corresponds to an exponential separation between the query upper bounds for the benchmark problem. Our third algorithm can find the global optimum of f by preparing a classical low-temperature thermal state via simulation of the classical Liouvillian operator associated with the Nosé Hamiltonian. We use results from the quantum thermodynamics literature to bound the thermalization time for the discrete system. Additionally, we analyze barren plateau effects that commonly plague quantum optimization algorithms and observe that our approach is vastly less sensitive to this problem than standard gradient-based optimization. Our results suggest that these dynamical optimization approaches may be far more scalable for future quantum machine learning, optimization and variational experiments than was widely believed.
We provide several quantum algorithms for continuous optimization that do not require gradient estimation. Instead, we encode the optimization problem into the dynamics of a physical system and coherently simulate the time evolution. We focus on the setting where the objective function can be accessed via a phase oracle. Our first two algorithms can find local optima of a differentiable function f : R N → R by simulating either classical or quantum dynamics with friction via a time-dependent Hamiltonian. We show that for the benchmark problem of optimizing a locally quadratic objective function, these methods require a total of O ( N 2 κ 2 / h x 2 ϵ ) queries to a phase oracle to find an ϵ -approximate local optimum, where κ is the condition number of the Hessian matrix and h x is the discretization spacing. In contrast, we show that methods based on gradient descent require O ( N 3 / 2 ( 1 / ϵ ) κ log ( 3 ) / 4 ) queries. This corresponds to an exponential separation between the query upper bounds for the benchmark problem. Our third algorithm can find the global optimum of f by preparing a classical low-temperature thermal state via simulation of the classical Liouvillian operator associated with the Nosé Hamiltonian. We use results from the quantum thermodynamics literature to bound the thermalization time for the discrete system. Additionally, we analyze barren plateau effects that commonly plague quantum optimization algorithms and observe that our approach is vastly less sensitive to this problem than standard gradient-based optimization. Our results suggest that these dynamical optimization approaches may be far more scalable for future quantum machine learning, optimization and variational experiments than was widely believed.
We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued function f : Rd → R by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d.One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).
We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate realvalued function f : ℝd → ℝ by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d. One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).
This work investigates the possibility of quantum speedups for continuous optimization through quantum Hamiltonian simulation. We establish the first rigorous query complexity bounds for unconstrained convex optimization via digital quantum annealing, based on the non-adiabatic Quantum Hamiltonian Descent (QHD) framework. In the process, we derive rigorous resource estimates for digital quantum simulation of Schrödinger operators depending only on input simulation parameters, given black-box evaluation access to separable, Lipschitz continuous potential b(t) f(x). We apply these simulation bounds to assess the complexity of high-dimensional convex optimization. Our annealing schedule achieves arbitrarily fast convergence rates in the evolution time, with computational time determined solely by the cost of discretization. We show that a G-Lipschitz convex function can be optimized to an error of ε with 𝒪̃(d^{1.5} G² R²/ε²) queries, given a starting point that is Euclidean distance R from optimal. Under reasonable assumptions such as the complexity of simulating Schrödinger operators, we show that Ω̃(d/ε²) queries are necessary. This suggests QHD does not offer improvements over classical methods in the noiseless zeroth order setting. However, we show that the QHD algorithm can tolerate 𝒪̃(ε³ /d^{1.5} G² R²) noise in function evaluation, and as a result, provides a super-quadratic query advantage over the best existing noise-tolerant classical algorithms in the high-dimensional setting. We leverage this to design a quantum algorithm for stochastic convex optimization that offers a super-quadratic speedup over all known classical and quantum algorithms in this regime. To our knowledge, these results represent the first rigorous quantum speedups for convex optimization obtained through a dynamical algorithm.
We introduce a quantum approximate optimization algorithm (QAOA) for continuous optimization. The algorithm is based on the dynamics of a quantum system moving in an energy potential which encodes the objective function. By approximating the dynamics at finite time steps, the algorithm can be expressed as alternating evolution under two non-commuting Hamiltonians. We show that each step of the algorithm updates the wavefunction in the direction of its local gradient, with an additional momentum-dependent displacement. For initial states in a superposition over many points, this method can therefore be interpreted as a coherent version of gradient descent, i.e., 'gradient descent in superposition.' This approach can be used for both constrained and unconstrained optimization. In terms of computational complexity, we show how variants of the algorithm can recover continuous-variable Grover search, and how a single iteration can replicate continuous-variable instantaneous quantum polynomial circuits. We also discuss how the algorithm can be adapted to solve discrete optimization problems. Finally, we test the algorithm through numerical simulation in optimizing the Styblinski-Tang function.
Quantum computers are expected to significantly outperform classical computers for certain computational tasks. One of the most promising applications is the simulation of many-body systems such as complex molecules or materials. In this thesis, we present several quantum algorithms for simulating many-body systems that can provide considerably better scaling than prior approaches. First, we describe a fully coherent quantum algorithm for simulating molecular dynamics within the Born-Oppenheimer approximation that leads to super-polynomially better scaling with respect to the error tolerance than previous work. Our algorithm utilizes the Koopman-von Neumann formulation of classical mechanics. This allows us to express the classical equations of motion as unitary dynamics which can be efficiently simulated on a quantum computer. We demonstrate that these simulations can be performed either at constant energy or at constant temperature. The latter allows us to estimate thermodynamic properties such as the Helmholtz free energy of the system. Next, we present two closely related quantum algorithms for solving continuous optimization problems such as finding the equilibrium configurations of molecules. These algorithms do not require any explicit gradient estimations. Instead, we encode the optimization problem into the dynamics of a quantum or classical system with friction. The dynamics are governed by a carefully chosen time-dependent Hamiltonian and thus can be simulated using efficient Hamiltonian simulation algorithms. We provide evidence that our fully coherent quantum algorithms can, in certain cases, provide exponentially better asymptotic scaling than approaches based on gradient descent. Lastly, we present a quantum algorithm for preparing the ground state of a set of interacting systems that can circumvent the exponential scaling suggested by the Van Vleck catastrophe. Our algorithm utilizes a divide-and-conquer strategy that repeatedly uses phase estimation to merge ground states of increasingly larger subsystems. We provide rigorous bounds for this approach and show that, under certain assumptions, our algorithm scales only quasi-polynomially with the number of systems.
Estimating the ground-state energy of Hamiltonians is a fundamental task for which it is believed that quantum computers can be helpful. Several approaches have been proposed toward this goal, including algorithms based on quantum phase estimation and hybrid quantum-classical optimizers involving parameterized quantum circuits, the latter falling under the umbrella of the variational quantum eigensolver. Here, we analyze the performance of quantum Boltzmann machines for this task, which is a less explored ansatz based on parameterized thermal states and which is not known to suffer from the barren-plateau problem. We delineate a hybrid quantum-classical algorithm for this task and rigorously prove that it converges to an ε-approximate stationary point of the energy function optimized over parameter space, while using a number of parameterized-thermal-state samples that is polynomial in ε−1, the number of parameters, and the norm of the Hamiltonian being optimized. Our algorithm estimates the gradient of the energy function efficiently by means of a quantum circuit construction that combines classical random sampling, Hamiltonian simulation, and the Hadamard test. Additionally, supporting our main claims are calculations of the gradient and Hessian of the energy function, as well as an upper bound on the matrix elements of the latter that is used in the convergence analysis.