Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This paper introduces CV-QAOA, an efficient low-depth quantum approximate optimization algorithm for continuous variables, by incorporating a variationally optimized initial state and proving convergence guarantees analogous to Quantum Hamiltonian Descent. The authors demonstrate rigorous performance bounds, showing $d$-step CV-QAOA can minimize $d$-dimensional strictly convex quadratic functions with $2d$ queries and solve a challenging non-convex "Rotated Double Well" problem with only two queries. Furthermore, they introduce the "Rotated Square Well" problem, where CV-QAOA achieves near-optimal query complexity for finding the global minimum, outperforming classical algorithms in certain regimes.
A single quantum query can solve a non-convex optimization problem previously requiring superpolynomial classical time, and CV-QAOA offers a path to efficient quantum advantage on problems intractable for classical gradient descent.
We study a Continuous-Variable Quantum Approximate Optimization Algorithm (CV-QAOA) for high-dimensional continuous optimization. Our formulation extends an earlier CV-QAOA proposal with a variationally optimized initial state and recovers the convergence guarantees of Quantum Hamiltonian Descent (QHD) in the high-depth limit. We prove rigorous performance guarantees of CV-QAOA on several families of cost functions. First, we show $d$-step CV-QAOA minimizes any $d$-dimensional strictly convex quadratic function with $2d$ quantum queries to the cost function. We then analyze a family of nonconvex "Rotated Double Well" (RDW) functions with $2^d$ local minima introduced by arXiv:2311.00811. While prior work showed QHD reaches its global minimum with $\tilde O(d^3)$ queries, we prove that 1-step CV-QAOA solves RDW with just two quantum queries. Although general-purpose classical solvers need superpolynomial time for RDW and structure-awareness can reduce the cost to polynomial time, we show that the 1-step CV-QAOA protocol can be efficiently dequantized, and that a gradient-aligned line search succeeds with $O(d)$ queries, nearly matching the information-theoretic $Ω(d/\log d)$ query lower bound. To move beyond the dequantizable regime, we introduce a ``Rotated Square Well'' (RSW) problem, whose globally flat landscape suppresses useful local gradient information. For this family, we show that an adiabatic evolution simulated by CV-QAOA can reach the global minimum using $d^{o(1)}$ queries. On the other hand, any classical algorithm that learn the hidden rotation in RSW provably requires $Ω(d^2/\log d)$ queries, a bound we nearly match with an explicit $Θ(d^2\log d)$-query classical algorithm.Numerical simulations on deflected corrugated spring and Easom functions illustrate the promising performance of CV-QAOA on more general problems.