Can Low-Depth Continuous-Variable QAOA Solve High-Dimensional Continuous Optimization?

A variational initial state changes one-step CV-QAOA

The paper studies a Continuous-Variable Quantum Approximate Optimization Algorithm (CV-QAOA) for minimizing a cost function C(x) over d real-valued variables. The circuit alternates two drivers, a kinetic Hamiltonian B = p²/2 and the cost Hamiltonian C, applied for p layers with parameters β and γ. As the layer count p grows, the authors note, this construction can approximate Quantum Hamiltonian Descent (QHD) to arbitrary precision through standard Trotter-decomposition arguments.

The formulation extends an earlier CV-QAOA proposal in one specific way: the initial state |σ⟩, a Gaussian of width σ, is itself variationally optimized. The authors report that this matters concretely. On the quartic Styblinski-Tang cost function studied in that earlier work, optimizing the initial state let one-step CV-QAOA approximate the global minimum arbitrarily well, whereas the earlier proposal did not reach the same performance even after optimizing its ansatz up to p = 3 steps.

That single change also sets up the paper's two regimes. A point-like initial state (σ → 0) exploits local gradient information near the origin; a delocalized state (σ → ∞) senses global landscape structure instead. Which regime helps depends on the cost function, and the paper's query-complexity results split along exactly that line.

Strictly convex quadratics need d steps, not one

For a d-dimensional strictly convex quadratic C(x) = ½xᵀQx + bᵀx with Q ≻ 0, the paper proves that d-step CV-QAOA minimizes the function using 2d quantum queries to the cost function. The optimality gap bound depends on the eigenvalues q₁, …, q_d of Q, the minimizer x₀ = −Q⁻¹b, the initial width σ, and the circuit parameters.

The depth requirement is not incidental. The appendix analysis shows that a single ordinary CV-QAOA step is sufficient only in the degenerate case Q ∝ I; for a generic nondegenerate Hessian, one step does not guarantee convergence to the minimum. The explicit sequential parameter choice λ_k = 1/q_k, with β₁ → 0, …, β_{d−1} → 0 taken in that order at fixed λ_k and then β̂/σ → 0, drives the optimality gap to zero.

This result is a warm-up rather than a claimed speedup. The authors place it against known quantum gradient methods for convex optimization, which achieve polylogarithmic dimension dependence using approximate function-value oracles, including a Õ(κ) query bound for smooth strongly convex objectives with condition number κ. Their contribution here is an analytic d-step construction whose depth and phase-query bounds are independent of κ.

One-step CV-QAOA solves the rotated double well in two queries

The first nonconvex family is the Rotated Double Well (RDW), a set of d-dimensional quartic functions with 2^d local minima, introduced in earlier work. Prior work showed that QHD reaches the global minimum of RDW with O(d³) queries. This paper proves that one-step CV-QAOA solves RDW with just two quantum queries.

The mechanism is a point-like initial state. For general one-dimensional real-analytic functions, the paper's Theorem 3.1 identifies what one-step CV-QAOA does in the σ → 0 regime: to leading order the circuit acts as an effective displacement controlled by C′(0), reducing the optimization to a one-parameter search. On RDW, that displacement is enough to land on the global minimum.

The authors are explicit that this is not the end of the story. They show the one-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 for classical algorithms with O(log d)-bit precision black-box access to the cost function. Earlier empirical studies had suggested state-of-the-art classical solvers need superpolynomial runtime in d; this paper instead exhibits polynomial-time classical algorithms, complementing independent work that reached a similar conclusion.

The rotated square well escapes dequantization

To move beyond the dequantizable regime, the authors introduce the Rotated Square Well (RSW), a family whose globally flat landscape suppresses useful local gradient information. Because the landscape is flat, the point-like regime that solved RDW is ineffective here.

For RSW, the paper shows that an adiabatic evolution simulated by CV-QAOA can reach the global minimum using d^o(1) queries. The supporting analysis bounds the change in the two lowest energies caused by Gaussian smoothing, shows a suitable smoothing width preserves the spectral gap, and combines an exponentially accurate adiabatic theorem with uniform spectral estimates and an endpoint-flat analytic schedule to obtain a runtime bound T = O(log⁸ d). The query bound follows from factorizing the evolution into one-dimensional pieces and using higher-order product formulas.

On the classical side, the paper proves that any classical algorithm which learns the hidden rotation in RSW requires Ω(d²/log d) queries, and provides an explicit Θ(d² log d)-query classical algorithm that nearly matches this bound. The authors also report Θ(d³/log d) hitting-time bounds for a natural family of random-walk algorithms on RSW. The separation here is therefore between d^o(1) quantum queries and a provably superpolynomial classical requirement for rotation-learning algorithms, not between quantum and all classical approaches.

Initial width σ decides which regime CV-QAOA exploits

The paper's two headline separations come from opposite ends of the same control knob. The initial Gaussian width σ sets whether the algorithm behaves like a localized probe or a delocalized one, and the authors frame the results as showing CV-QAOA can exploit both localized (σ → 0) and highly delocalized (σ → ∞) quantum states to obtain provable query-complexity separations.

RDW is the localized case: the gradient at the origin reveals substantial information about the global minimum, which is why both one-step CV-QAOA and the classical line search do well. RSW is the delocalized case: the flat staircase-like landscape carries no useful local gradient, so the classical advantage disappears while the adiabatic evolution simulated by CV-QAOA still finds the optimum.

This distinction is the paper's most transferable idea for a reader comparing optimization problems. It is not the dimension alone that determines whether CV-QAOA helps; it is whether the landscape's useful information sits in local gradients near the starting region or in global structure that only a spread-out state can sense.

Simulations show low-depth CV-QAOA beating QHD on Easom

The rigorous results cover specific families. To probe more general problems, the authors run numerical simulations on deflected corrugated spring and Easom functions. The Easom case is the informative one because its gradients are exponentially small everywhere except near the global minimum at x = 0, so the point-like regime cannot work.

In the comparison, space [−L, L]^d is discretized into a lattice with 2⁸ grid points per dimension, success is defined as ‖x − x*‖₂ < ε with ε = 10% of 2L, and success rate is computed by integrating the final probability density over that region. To match effort fairly, the QHD schedule is converted into an equivalent integrated runtime T_p defined as the ℓ₁-norm Σ(|β_k| + |γ_k|) over layers, and CV-QAOA parameters are tuned with random initial guesses followed by a gradient-free Powell optimizer.

At matched integrated runtime, low-depth CV-QAOA with a uniform initial state reaches higher accuracy than QHD in both d = 1 and d = 2, and the margin persists as T_p grows. Absolute success probabilities peak near 0.3 for d = 2 versus nearly 1 for d = 1, so the two-dimensional instance is clearly harder, yet CV-QAOA keeps its lead. A few layers suffice, whereas QHD saturates at lower accuracy over the same budget. These are simulation results on two named functions, not extensions of the query-complexity theorems.

Query separations are not yet total-runtime advantages

The paper's guarantees are stated in query complexity, and the authors are careful about what that leaves out. They note that establishing a substantial advantage in total runtime also requires accounting for state preparation, parameter optimization, and query implementation. The depth-p = 1 analysis is also the main theoretical frontier: extending it to broader classes of nonconvex functions, including landscapes with multiple interacting minima or strong anisotropy, remains open.

Hardware is a second boundary. Realizing CV-QAOA on continuous-variable hardware requires high-fidelity Gaussian and non-Gaussian operations; the authors point to proposals for multimode photonic gates and programmable trapped-ion bosonic simulation, and to experimental demonstrations of nonlinear quadrature measurements using optical feedforward. They state that scaling to the gate counts needed for high-dimensional problems will require further advances in hardware performance and scalability, and that small-scale experimental demonstrations may become feasible as those platforms improve.

The classical lower bounds also carry their own scope. The Ω(d/log d) bound applies to classical algorithms with O(log d)-bit precision black-box access to the cost function, and the Ω(d²/log d) bound applies to algorithms that reconstruct the hidden rotation in RSW. The paper's own classical algorithms show that RDW is solvable in polynomial time, so the RDW separation is against general-purpose solvers, not against all classical methods.

The advantage lives in flat landscapes, not in dimension alone

Read together, the results give a specific decision rule rather than a blanket claim about low-depth CV-QAOA. If a high-dimensional continuous problem has informative local gradients near the starting region, expect the point-like regime to work and expect classical methods to keep pace: RDW is solved by one-step CV-QAOA in two queries, but a gradient-aligned line search gets there in O(d) queries, close to the Ω(d/log d) lower bound.

If instead the landscape is globally flat and hides its structure from local gradients, the picture changes. RSW is the paper's constructed example: CV-QAOA reaches the global minimum in d^o(1) queries, while any classical algorithm that learns the hidden rotation provably needs Ω(d²/log d) queries, with an explicit Θ(d² log d) classical algorithm nearly matching that bound. The Easom simulation points the same way, where a delocalized initial state outperforms QHD at matched integrated runtime.

The priority this paper sets is therefore to look for flat, gradient-poor, high-dimensional landscapes when asking whether CV-QAOA is worth the hardware cost, and to check whether a structure-aware classical method can already exploit the same hidden structure before assuming a quantum advantage.

Sources used in this answer