arXiv:2610.06815
CV-QAOA: Efficient Low-Depth Quantum Optimization of Continuous Variables
Sriram Bharadwaj, Di Luo, Leo Zhou
Abstract
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.
AI Summary
This paper studies when continuous-variable QAOA can provably minimize high-dimensional continuous objectives, and whether its performance yields quantum query advantages. The ansatz alternates cost-phase evolution and kinetic mixing, with the initial Gaussian width included among the variational parameters. For strictly convex quadratics in $d$ dimensions, it constructs depth-$d$ circuits achieving arbitrarily small optimality gap using $2d$ value-oracle queries. The parameters require Hessian eigenvalues and increasingly separated scales. For rotated separable analytic objectives, including rotated double wells (RDW), one layer suffices when the gradient at the origin points toward a global minimizer. This uses two quantum queries, versus a classical lower bound of $\Omega(d/\log d)$ at $O(\log d)$-bit precision. The localized-state mechanism admits Gaussian dequantization; an explicit classical RDW algorithm uses $O(d)$ queries. To avoid that mechanism, the paper introduces shifted rotated square wells (RSW). Hidden-coordinate separability, spectral localization, and an endpoint-flat adiabatic schedule yield runtime $O(\log^8 d)$. Higher-order product formulas with a harmonic mixer give $d^{o(1)}$ phase queries to a smoothed potential. A classical rotation-reconstruction algorithm uses $\Theta(d^2\log d)$ queries, compared with a reconstruction lower bound of $\Omega(d^2/\log d)$. The RSW lower bound does not cover arbitrary classical optimizers. Its quantum preparation guarantee initially concerns an enlarged target region, with sample averaging proposed to reach the wells. Total runtime must additionally account for preparation, parameter optimization, and oracle implementation. Low-dimensional numerical comparisons favor CV-QAOA over selected QHD schedules but do not establish general advantage; the random-walk scaling analysis is assumption-dependent.
GPT-6 Astra assisted with drafting and revising manuscript text and checking intermediate algebraic calculations.
Central claim may not hold: The advertised 2d-query quadratic guarantee counts only circuit execution with Hessian-dependent parameters, not obtaining the Hessian eigenvalues required to choose those parameters from the stated value oracle. The quadratic arbitrary-accuracy construction does not establish phase-parameter bounds compatible with the paper’s O(log d)-bit oracle implementation. The RSW subpolynomial-query corollary assumes access to a smoothed potential and a harmonic mixer rather than establishing that bound for the original sharp-potential oracle and stated free-mixer ansatz. The discussion’s claimed superpolynomial-in-d query separations are not implied by its linear-versus-constant and polynomial-versus-subpolynomial bounds. The dequantization explanation incorrectly writes the rotated separable Hessian as w′(0)I instead of w″(0)I, although the corrected Hessian remains known and rotation-independent.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 40+41 pages, 9 figures