Classical Optimizers for Variational Quantum Algorithms

Optimizer choice is a live, experimentally consequential decision in every variational-algorithm demonstration. In quantum chemistry, VQE runs reach for QNG or Adam fed by parameter-shift gradients when the ansatz is shallow enough that $2p$ evaluations per step are affordable, because those methods reach chemical accuracy in the fewest iterations on a benign landscape. On noisy devices with many parameters, SPSA is the default outer loop — it stands behind a large fraction of published NISQ VQE and QAOA results precisely because its two-evaluations-per-step budget survives where finite-difference methods drown. For QAOA the parameter space is small and structured, so gradient-free Nelder–Mead and COBYLA, warm-started from parameter-concentration transfer, remain competitive. And the open frontier is trainability: because equation (8) says no outer loop escapes a barren plateau, the active research is upstream of the optimizer — local cost functions, shallow problem-tailored ansätze, identity-block initializations, and layerwise growth that keeps the landscape resolvable as circuits scale. Frameworks such as PennyLane and Qiskit now ship parameter-shift, SPSA, and QNG as drop-in optimizers, making a once-esoteric choice a single line of configuration — one that still often decides whether an experiment converges.

Picture the optimizer as a hiker descending a fog-bound valley. Every altitude reading is jittery because it is a Monte-Carlo estimate from finite shots, and the compass — the gradient — may point slightly wrong because the hardware is noisy. When the compass is honest on average (a parameter-shift gradient), the hiker can march downhill with confidence. When each compass reading is ruinously expensive, the hiker instead pokes two random directions and steps down the average slope — that is SPSA. And when the terrain is a vast, dead-flat plateau (a barren plateau), no compass helps at all, because the ground is indistinguishable from noise in every direction and the only cure is to start in a different valley. The first figure draws this coupled machine explicitly: a quantum inner loop that samples the landscape and a classical outer loop that decides where to step.

Geometry is the second thing the picture must convey. A given change in the parameters $\boldsymbol{\theta}$ can move the underlying quantum state by a lot or by almost nothing, because parameter space is distorted relative to the space of states. Quantum Natural Gradient measures distances with the Fubini–Study metric — the natural ruler on state space — and so takes well-sized steps where plain gradient descent would either crawl or overshoot. But no amount of clever geometry saves an optimizer from the deepest hazard of the landscape: the barren plateau, where the variance of every gradient component decays exponentially with the number of qubits. The second figure makes that threat quantitative, plotting the gradient variance against qubit number and marking where it sinks beneath the shot-noise floor.

Underneath both figures sits one theorem. Stochastic-approximation theory (Robbins and Monro, 1951) says a noisy oracle is acceptable for a first-order method provided the gradient estimate is unbiased and the step size $\eta_k$ decays so that $\sum_k\eta_k=\infty$ while $\sum_k\eta_k^2<\infty$. The first condition lets the iterate travel any finite distance; the second drowns the accumulated noise. Adaptive methods such as Adam achieve the same stabilization by maintaining running averages of the gradient and its square, giving each coordinate its own effective learning rate.

Everything begins with the object being minimized. A variational algorithm poses an optimization over circuit angles, with the cost defined as the expectation of a problem observable in the prepared state — a number the device can only estimate, never compute exactly.

where: $\boldsymbol{\theta}\in\mathbb{R}^p$ — vector of $p$ circuit parameters (rotation angles); $|\psi(\boldsymbol{\theta})\rangle=U(\boldsymbol{\theta})|0\rangle$ — ansatz state prepared by the parameterized unitary; $\hat{H}$ — problem Hamiltonian or observable defining the cost; $C(\boldsymbol{\theta})$ — scalar cost, estimated on the device with finite shots. Reading: the optimizer never sees $C$ itself, only a shot estimate $\hat{C}$, and its whole job is to walk $\boldsymbol{\theta}$ toward $\boldsymbol{\theta}^\star$ using those estimates. The workhorse update is stochastic gradient descent: step against an unbiased estimate of the gradient, with a learning rate that may shrink over iterations. Its convergence under noise is not obvious and is exactly what stochastic-approximation theory secures.

where: $\eta_k>0$ — learning rate at iteration $k$; $\widehat{\nabla C}$ — unbiased stochastic estimate of the gradient. Reading: because $\mathbb{E}[\widehat{\nabla C}]=\nabla C$, the expected step points downhill even though any single step is corrupted by shot noise. The gradient itself comes not from finite differences but from the parameter-shift rule, an exact analytic formula that holds whenever a gate is generated by an operator with two distinct eigenvalues (any Pauli rotation qualifies).

where: $\mathbf{e}_j$ — unit vector along parameter $j$; $\partial_j C$ — exact partial derivative of the cost. Reading: two evaluations at angles shifted by the macroscopic amount $\pi/2$ return the true derivative with no truncation bias — the exact opposite of a finite difference, whose small denominator would amplify shot noise. Feeding an ordinary gradient into the Euclidean update ignores that state space is curved. Quantum Natural Gradient corrects this by preconditioning the step with the inverse Fubini–Study metric, so the effective step size respects how much each parameter actually moves the state.

where: $F(\boldsymbol{\theta})$ — Fubini–Study metric tensor (quantum Fisher information divided by four); $[F]^{-1}$ — its (pseudo)inverse, preconditioning the step to state-space geometry. Reading: where $F$ has small eigenvalues — directions in which the state barely changes — $F^{-1}$ enlarges the step, curing the crawl that plagues plain descent in ill-conditioned regions. The metric that does the preconditioning is a geometric quantity built from the state's derivatives, real and positive-semidefinite, measuring how distinguishable neighbouring states are.

where: $|\partial_i\psi\rangle$ — derivative of the ansatz state with respect to $\theta_i$; $F_{ij}$ — real, symmetric, positive-semidefinite metric tensor. Reading: the subtracted term strips off the pure-global-phase part of the state's change, which is physically invisible, leaving only motion that genuinely reshapes the state. When even $2p$ shift evaluations are unaffordable, SPSA collapses the gradient estimate to two evaluations by perturbing all parameters at once along a random sign vector.

where: $\boldsymbol{\Delta}_k$ — random perturbation vector, each component $\pm1$ (Bernoulli); $c_k=c/k^{\gamma}$ — perturbation magnitude, decaying with iteration; $\boldsymbol{\Delta}_k^{-1}$ — component-wise reciprocal of the perturbation vector. Reading: the estimate is noisy per step, but unbiased on average and independent of $p$, which is why it dominates on large, expensive circuits. Any of these gradients can be smoothed by Adam, which keeps bias-corrected running moments and gives every coordinate an adaptive learning rate — the standard choice when the gradient itself is noisy.

where: $g_k$ — current stochastic gradient (parameter-shift or SPSA); $m_k,v_k$ — first- and second-moment running estimates; $\hat m_k=m_k/(1-\beta_1^k)$, $\hat v_k=v_k/(1-\beta_2^k)$ — bias-corrected moments; $\beta_1,\beta_2,\epsilon$ — decay rates (typically $0.9$, $0.999$) and a small constant ($10^{-8}$). Reading: dividing by $\sqrt{\hat v_k}$ shrinks steps along high-variance directions, damping the very shot noise that would otherwise destabilize the trajectory. Finally, the hazard that caps everything: on many ansätze the gradient variance itself decays exponentially in the qubit number, so no local method can find a downhill direction above the noise.

where: $n$ — number of qubits; $\alpha>0$ — decay constant set by ansatz and circuit depth; $G(n)$ — exponentially small gradient-variance bound. Reading: equation (8) is a property of the landscape, not the optimizer, so it cannot be defeated by a better outer loop — the remedy lives in the ansatz, the initialization, and the locality of the cost.

How the optimizer's behaviour changes across the regimes that actually arise in variational algorithms:

1 · The exact parameter-shift gradient of a single rotation (fully worked)

A one-qubit circuit prepares $|\psi(\theta)\rangle=R_Y(\theta)|0\rangle$ and measures the cost $C(\theta)=\langle Z\rangle=\cos\theta$. Evaluate the parameter-shift gradient at $\theta=\pi/3$ and compare it with a central finite difference of step $h=0.1$.

Step 1. The exact analytic derivative is $\partial_\theta C=-\sin\theta$, so at $\theta=\pi/3$ we expect $\partial_\theta C=-\sin(\pi/3)=\mathbf{-0.86603}$. The cost itself there is $C=\cos(\pi/3)=0.5$.

Step 2. Apply the shift rule with $\pi/2$: $C(\theta+\tfrac{\pi}{2})=\cos(5\pi/6)=-0.86603$ and $C(\theta-\tfrac{\pi}{2})=\cos(-\pi/6)=+0.86603$, so $\tfrac12[C(\theta+\tfrac{\pi}{2})-C(\theta-\tfrac{\pi}{2})]=\tfrac12(-0.86603-0.86603)=\mathbf{-0.86603}$ — exactly the analytic value, to every digit.

Step 3. Now the finite difference: $[C(\theta+h)-C(\theta-h)]/(2h)$ with $h=0.1$ gives $(0.41103-0.58397)/0.2=\mathbf{-0.86458}$, which is off by $\mathbf{0.00144}$. That error is the leading $O(h^2)$ truncation, $\tfrac{h^2}{6}|C'''|=\tfrac{0.01}{6}\sin(\pi/3)=0.00144$ — and shrinking $h$ to reduce it would divide two ever-closer noisy numbers by an ever-smaller denominator, which is precisely why finite differences fail under shot noise while the shift rule does not. The shift rule returns −0.86603 exactly; the finite difference is biased by 1.4×10⁻³ and gets noisier as h shrinks.

2 · Shot noise, gradient variance, and detectability

The same circuit is run on hardware with $N_{\text{shots}}=1000$ per evaluation. How noisy is the parameter-shift gradient at $\theta=\pi/3$, and is the gradient resolvable?

Step 1. A single $Z$ measurement on a state with $\langle Z\rangle=\mu$ has variance $1-\mu^2$. At the shifted angles $\langle Z\rangle=\mp0.86603$, so $\mu^2=0.75$ and each has $\sigma_\pm^2=1-0.75=0.25$.

Step 2. The gradient variance is $\mathrm{Var}[\widehat{\partial_\theta C}]=\dfrac{\sigma_+^2+\sigma_-^2}{4N_{\text{shots}}}=\dfrac{0.5}{4000}=\mathbf{1.25\times10^{-4}}$, a standard error of $\mathbf{0.0112}$.

Step 3. Compare to the signal $|\partial_\theta C|=0.866$: the signal-to-noise ratio is $0.866/0.0112\approx\mathbf{78}$, so the gradient is comfortably resolved and the sign is never in doubt. Had this been a barren-plateau direction with $|\partial_\theta C|\sim 2^{-n/2}$, resolving it would demand $N_{\text{shots}}\gtrsim 2^{n}$ shots — at $n=13$ that is already $\sim8000$ shots just to clear the noise floor once, as Figure 2 marks. At 1000 shots the gradient has SNR ≈ 78; on a plateau the required shots grow as 2ⁿ.

3 · SPSA cost saving and the QNG factor of four

A hardware VQE uses $p=100$ parameters at $1000$ shots per evaluation. Compare the per-step cost of full parameter-shift with SPSA, and separately compute the Fubini–Study metric for a single $R_Y(\theta)$ rotation.

Step 1. Full parameter-shift needs two evaluations per parameter, $2p=\mathbf{200}$ circuit evaluations per gradient, i.e. $200\times1000=\mathbf{2.0\times10^5}$ shots per optimizer step.

Step 2. SPSA needs exactly $\mathbf{2}$ evaluations per step regardless of $p$, i.e. $2\times1000=\mathbf{2000}$ shots per step — a $\mathbf{100\times}$ reduction. The price is a noisier per-step direction, but with a decaying step schedule the trajectory still converges; this is why SPSA is the default on slow NISQ hardware.

Step 3. For QNG on a single $R_Y(\theta)$, the state derivative is $|\partial_\theta\psi\rangle=\tfrac12(-\sin\tfrac{\theta}{2}|0\rangle+\cos\tfrac{\theta}{2}|1\rangle)$, giving $\langle\partial_\theta\psi|\partial_\theta\psi\rangle=\tfrac14$ and $\langle\partial_\theta\psi|\psi\rangle=0$, so $F=\tfrac14-0=\tfrac14$. The QNG step is therefore $-\eta F^{-1}\partial_\theta C=-4\eta\,\partial_\theta C$: the metric rescales the bare gradient by exactly four. Parameter-shift costs 2.0×10⁵ shots per step versus 2×10³ for SPSA; the single-rotation Fubini–Study metric is 1/4, so QNG multiplies the gradient by 4.

The intellectual backbone of this whole subject is not quantum mechanics but stochastic approximation — the mid-twentieth-century theory of how to optimize a function you can only sample noisily. Its most practical descendant, and the optimizer most used on real quantum hardware, is James Spall's simultaneous perturbation method.

Texts and papers. Cerezo et al., "Variational Quantum Algorithms", Nature Reviews Physics 3, 625 (2021) · Spall, "Multivariate stochastic approximation using a simultaneous perturbation gradient approximation", IEEE Trans. Automatic Control 37, 332 (1992), and the implementation paper, IEEE Trans. Aerospace and Electronic Systems 34, 817 (1998) · Stokes, Izaac, Killoran, Carleo, "Quantum Natural Gradient", Quantum 4, 269 (2020) · Schuld, Bergholm, Gogolin, Izaac, Killoran, "Evaluating analytic gradients on quantum hardware", Phys. Rev. A 99, 032331 (2019) · Kingma & Ba, "Adam: A Method for Stochastic Optimization", ICLR (2015) · McClean, Boixo, Smelyanskiy, Babbush, Neven, "Barren plateaus in quantum neural network training landscapes", Nature Communications 9, 4812 (2018) · Robbins & Monro, "A Stochastic Approximation Method", Ann. Math. Statist. 22, 400 (1951) · Amari, "Natural Gradient Works Efficiently in Learning", Neural Computation 10, 251 (1998) · Preskill, Ph219 lecture notes (Caltech); Nielsen & Chuang, Quantum Computation and Quantum Information.

Provenance. A verifier should reconfirm: the parameter-shift formula $\partial_\theta C=\tfrac12[C(\theta+\tfrac\pi2)-C(\theta-\tfrac\pi2)]$ for Pauli generators via the sinusoid $a+b\cos\theta+c\sin\theta$ (Schuld et al. 2019); the QNG update $\Delta\boldsymbol\theta=-\eta F^{-1}\nabla C$ and the Fubini–Study metric $F_{ij}=\mathrm{Re}\langle\partial_i\psi|\partial_j\psi\rangle-\langle\partial_i\psi|\psi\rangle\langle\psi|\partial_j\psi\rangle$ (Stokes et al. 2020); the SPSA estimator and its two-evaluation cost (Spall 1992); the Adam recursion with $\beta_1=0.9,\beta_2=0.999,\epsilon=10^{-8}$ (Kingma & Ba 2015); Monte-Carlo variance scaling $1/\sqrt{N_{\text{shots}}}$ and the gradient variance $0.125/N$ for the single-qubit $\theta=\pi/3$ case; the Robbins–Monro conditions; and the single-rotation metric $F=1/4$. The barren-plateau scaling $\mathrm{Var}[\partial_j C]\sim2^{-\alpha n}$ is stated qualitatively, consistent with McClean et al. (2018); the $n\approx13.3$ crossover at $10^4$ shots follows from $2^{-n}=10^{-4}$. No fabricated constants beyond standard optimizer defaults.

Prerequisites. Cost-Function and Measurement Estimation in Variational Algorithms · Parameter-Shift Rules and Quantum Gradients · Parameterized Quantum Circuits and Ansatz Design · Variational Quantum Eigensolver. Leads to. Barren Plateaus in Variational Landscapes · Strategies to Mitigate Barren Plateaus · Quantum Approximate Optimization Algorithm · Quantum Machine Learning Models.

Ask the tutor: Ask me to walk through the parameter-shift gradient of your own ansatz, or to work out whether SPSA, QNG, or Adam is the right optimizer for your shot budget and qubit count.