Quantum gradient estimation promises something classical black-box optimization cannot do. Using Jordan's phase-kickback algorithm, it evaluates a cost function once on a superposition of small perturbations and reads out the whole gradient at once, so the number of function calls barely grows with the number of inputs $d$. Classical finite differences need $d+1$ calls. The catch is that this trick assumes the function is nearly linear over the perturbation grid, and it needs very precise function values. Nonlinear control objectives are the opposite case: the cost of a simulated trajectory, as a function of the control inputs, bends more sharply the longer the horizon. So the theory says quantum gradients should matter most for high-dimensional control, and the physics says that is where they are hardest to run.
We propose to measure which effect wins and to report the answer in a form an engineer can read. Our central observation is that, in many coupled physical systems, the gradient of a rollout cost lives mostly on a small, sparse set of control coordinates, such as a few actuators over a few time windows. Sparse principal component analysis (PCA, here restricted so each direction uses only $k$ of the $d$ inputs) applied to sampled gradients finds that set and names it. That support size $k$ then does two jobs. It is an interpretable summary of which inputs drive the cost. It is also the quantity that decides whether a quantum estimator beats a classical one restricted to the same $k$ coordinates. The deliverable is a measured crossover: the range of $k$ and curvature at which quantum gradient estimation still has an advantage once the cheap classical alternative of "finite differences on the sparse support" is allowed.
Core Claim
On nonlinear control rollouts, two measurable properties of the cost determine the practical advantage of quantum zeroth-order gradient estimation, not the nominal dimension $d$. The first is the sparse effective dimension $k$ of the gradient: the smallest support for which a sparse subspace captures a fixed fraction of the gradient covariance. The second is the curvature of the cost restricted to that support, which sets how fine the perturbation grid must be and how precise the function oracle must be. Restricting a quantum estimator to the sparse support relaxes its precision demands sharply. The robustness analysis of Gong, Zhang and Li shows Jordan-based perturbed accelerated gradient descent tolerates oracle noise only up to $O(\epsilon^{10}/d^5)$. Running on a $k$-dimensional support turns that into $O(\epsilon^{10}/k^5)$, a gain of $(d/k)^5$. The same restriction also makes classical finite differences cost only $k+1$ calls. The quantum estimator therefore wins only when $k$ is large enough for $k+1$ classical calls to hurt, yet the restricted curvature is small enough for the relaxed precision to be reachable. We expect this window to be narrow and benchmark-dependent, and we want to map it rather than assume it.
The mechanism is simple to state. Jordan's algorithm encodes $f(x_0+\delta z)$ as a phase over grid points $z$, with grid spacing $\delta$. The readout is correct when the phase is dominated by the linear term:
$$ f(x_0+\delta z) \approx f(x_0) + \delta\, \nabla f(x_0)^\top z + \tfrac{\delta^2}{2}\, z^\top H z , $$
Here $H$ is the Hessian of the rollout cost. Over a grid in $k$ coordinates, the quadratic term grows roughly with $k\,\delta^2 \|H_k\|$, where $H_k$ is the Hessian restricted to the support. Fewer active coordinates therefore permit a coarser grid at the same error. That coarser grid in turn tolerates a noisier function oracle.
Position Relative to Prior Work
The quantum side supplies the method and the constraints. Kim et al. give quantum zeroth-order methods, among them projected subgradient and mirror descent, with polylogarithmic dependence on $d$ that match classical first-order rates. They also flag that oracle precision scales badly. Gong et al. give the noise regimes, including an $\Omega(\epsilon^{1.5})$ noise level beyond which no algorithm succeeds. Both treat static black-box functions. Neither asks what structure in a time-indexed rollout makes the precision requirement reachable, and that is the question we test. He and Lui combine Jordan estimation with sparsity through an $\ell_1$-ball Frank-Wolfe method. Their sparsity constrains the solution, not the gradient estimator, and the setting is convex and static. Lim et al. show how sparsity-preserving quantum updates can cost more in iterations, $\tilde O(T^{5/2}\sqrt d)$, than they save in dimension. That warning shapes our design: we count total cost, not only dimension scaling.
On the control side, Clayton et al. is the closest quantum-for-control work. They obtain quantum policy gradients for linear-quadratic control through a quantum Lyapunov solver. The nonlinear case is left open there, and their gain matrix is dense. We do not extend their solver. Their linear-algebra trick has no counterpart for black-box nonlinear simulators, which is why we go through zeroth-order estimation instead. Frey et al. show that classical exact-Hessian sensitivities through nonlinear model predictive control (MPC, which re-solves a finite-horizon optimal control problem at every step) are accurate and fast in acados. Approximate Hessians, by contrast, give severe gradient errors. This is a warning for us: crude curvature handling breaks gradients through nonlinear controllers, so our error accounting must measure curvature, not assume it away. QuACK cuts the number of quantum gradient steps by extrapolating parameter trajectories with Koopman operators. It is complementary to our work, because it reduces how many gradients are needed while we study what each gradient costs.
The dimensionality-reduction side supplies the diagnostic. Del Pia et al. solve sparse PCA by thresholding a covariance into blocks and solving within blocks. That fits gradient covariances of chain-like physical systems, which we expect to be nearly block-structured. Moghaddam et al. give greedy spectral alternatives, and Mattei gives shared-support sparsity across several components, which is the right notion when we need a rank-$r$ subspace with one common set of active inputs. Pfau et al. motivate the decomposition: low-rank plus sparse structure yields interpretable dynamical models. They apply it to observations, not to the gradients of a control objective.
Research Program
We build three components.
The first is a gradient-structure pipeline. For each benchmark, we sample many base points across the operating region and compute reference gradients of the rollout cost with respect to the control sequence. These come from exact adjoints where a model exists and from large-sample classical estimates otherwise. We then fit shared-support sparse PCA to the gradient covariance. From the fit we report $k$ at fixed explained-variance levels, the identity of the selected actuators and time windows, and the stability of that support across base points and disturbance draws.
The second is a cost model for quantum gradient estimation that charges for precision. Exact simulation of Jordan's algorithm is feasible only for small $k$ times bits per coordinate, so we use two levels. For $k \le 4$ with a few bits per coordinate, we simulate the circuit's output distribution exactly from the true rollout cost, including its curvature, and inject oracle noise. That gives empirical error-versus-$\delta$ curves. For larger $k$, we evaluate the Taylor-remainder phase error on sampled grid points and convert it, using the published bounds of Kim et al. and Gong et al., into required oracle precision and query counts. We check that this conversion against the exact small-$k$ simulations before trusting it. Results are reported in oracle calls and in the number of bits of function-value precision required, never as wall-clock quantum time, which we cannot measure honestly.
The third is the crossover analysis. Each estimator gets the same target accuracy, measured as cosine similarity to the reference gradient and as the downstream closed-loop cost after a fixed number of descent steps. For each estimator we compute the cost to reach that target as a function of $k$, horizon length, and nonlinearity strength.
Baselines
The naive reference is full-dimensional central finite differences on all $d$ control inputs, at $2d$ calls per gradient. Every method must beat it, and it fixes the scale of the problem.
The strongest classical competitor is finite differences, or the classical simultaneous-perturbation estimator SPSA, restricted to the sparse PCA support. This uses the same sampled gradients and the same sparse solver as our quantum variant, so it isolates the quantum ingredient exactly. If it matches the quantum estimator's total cost at every $k$ we observe, the quantum advantage on these benchmarks is nil, and we will say so.
The strongest method when a model is available is exact adjoint sensitivity in acados following Frey et al.. They report that it is 3.6x to 19x faster for adjoint sensitivities than mpc.pytorch and cvxpygen on a bounded linear-quadratic benchmark. It sets the accuracy ceiling. It is unavailable in the black-box regime that motivates zeroth-order methods, and we treat the RRLS adversarially perturbed simulators as that regime.
For the linear chain, the relevant prior quantum-assisted number is from Clayton et al.: convergence in "approximately 750 iterations" against "20,000 iterations" for the classical model-free baseline on the mass-spring-damper chain. No reported result was found on Lacuna for zeroth-order gradient accuracy or query cost on nonlinear versions of these benchmarks. Those numbers are something this project must produce.
We run two ablations, each matched in subspace size and query budget, to isolate the role of sparsity. The first replaces sparse PCA with dense PCA, giving the same dimension but non-interpretable directions in which every input is mixed. The second uses a random $k$-dimensional coordinate subset. Beating them means reaching the target gradient accuracy with fewer calls, or at coarser required precision, while the support remains stable across operating points. For the sparse diagnostic itself, the block method of Del Pia et al. is the reference. They report a 100.5x average speedup over branch-and-bound with 0.61% average error on static covariances, and we check whether that accuracy carries over to gradient covariances.
Why not just…?
Why not just run classical finite differences on the sparse support and skip the quantum part? This is the most serious threat, and the proposal is built around it. Once sparse PCA reduces the problem to $k$ coordinates, classical estimation costs $k+1$ calls. A quantum estimator has to win against that, not against $d+1$. The crossover analysis answers the question directly. If the measured $k$ on every benchmark is in the tens, classical restricted finite differences win, and the honest conclusion is that the sparse structure, not quantum hardware, is what makes these problems tractable.
Why not just use exact adjoints in acados? When a differentiable model exists, they should win. Frey et al. show they are both accurate and fast. Our claim concerns black-box simulators and adversarial parameter sets as in RRLS, where only cost evaluations are available. We include the adjoint baseline wherever a model is available, so readers can see the size of the gap.
Why not just reduce the number of gradient steps with Koopman extrapolation, as QuACK does? QuACK reports over 200x speedup in overparameterized circuits but only 3x to 4.6x on non-smooth chemistry landscapes. It needs periodic re-anchoring because predictions drift. It reduces the number of gradients, not the cost of each one, so it composes with any estimator studied here. We run one combined condition to check that the crossover location does not move when step count is reduced.
Why not just use classical model reduction such as balanced truncation? The bounded-error reduced-order MPC of Köhler et al. is linear. Its projections mix all physical states, so they neither handle nonlinearity nor name the active actuators. The dense-PCA ablation stands in for this family.
Proposed Experiments
The benchmarks follow the file. The first is the mass-spring-damper chain at the scales used by Clayton et al. (4 to 64 masses) and Köhler et al. (50 masses, 100 states). We make it nonlinear with a cubic (Duffing) spring term whose strength we sweep from zero, which recovers the linear case and a sanity check against published behavior, upward. We also use the pendulum-on-cart from Frey et al., the CSTR from Degner et al. as a strongly nonlinear economic case, and the RRLS MuJoCo environments (RRLS) as black-box tests, with the horizon swept on each. The metrics are sparse effective dimension $k$ at 90% and 99% explained gradient variance, support stability measured as Jaccard overlap across operating points, gradient cosine accuracy, oracle calls and required precision bits to reach a target, and closed-loop cost after a fixed descent budget. All estimators share seeds, base points, and accuracy targets.
Three checks are decisive. First, if $k$ does not stay well below $d$ as horizon and nonlinearity grow, the sparse account fails, and the quantum estimator faces the full-dimensional precision bound. Second, the exact small-$k$ circuit simulations must agree with the bound-based cost model. If they diverge, the large-$k$ crossover numbers are not trustworthy, and we report only the small-$k$ regime. Third, the crossover itself: we plot quantum versus restricted-classical cost against $k$ and the restricted curvature, and state whether any benchmark lands in the region where quantum wins. An empty region on every benchmark would be a useful negative result. It would say that, for nonlinear control, the cited dimension-independent query bounds are cancelled by precision costs once sparse structure is exploited classically.
References
- Robustness of Quantum Algorithms for Nonconvex Optimization
- Fast Zeroth-Order Convex Optimization with Quantum Gradient Methods
- Quantum Algorithms for Projection-Free Sparse Convex Optimization
- Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent
- Differentiable Quantum Computing for Large-scale Linear Control
- Differentiable Nonlinear Model Predictive Control
- QuACK: Accelerating Gradient-Based Quantum Optimization with Koopman Operator Learning
- Efficient Sparse PCA via Block-Diagonalization
- Spectral Bounds for Sparse PCA: Exact and Greedy Algorithms
- Globally Sparse Probabilistic PCA
- Robust learning of low-dimensional dynamics from large neural ensembles
- Rrls: Robust reinforcement learning suite
- Robust reduced-order model predictive control using peak-to-peak analysis of filtered signals
- Adaptive Economic Model Predictive Control: Performance Guarantees for Nonlinear Systems