Variational Quantum Algorithms

A variational quantum algorithm (VQA) optimizes a classical parameter vector $\boldsymbol{\theta}$ using quantities estimated from a parameterized quantum circuit. In a common form,

$$\lvert\psi(\boldsymbol{\theta})\rangle = U(\boldsymbol{\theta})\lvert\psi_0\rangle,$$

and the task is encoded in an objective such as

$$C(\boldsymbol{\theta}) = \sum_{a=1}^{M} w_a \langle O_a \rangle_{\boldsymbol{\theta}}.$$

The quantum processor prepares states and samples measurements; a classical routine constructs cost or gradient estimates and proposes the next parameters. The loop is repeated until a declared stopping rule is met.

Useful applications include VQE, which minimizes an energy, and QAOA, which optimizes a cost using alternating operators. The general questions are shared: can the circuit reach a useful state, can measurements resolve improvements, and can the classical search find them at acceptable total cost? A decreasing cost alone does not answer all three.

Helpful background. Circuit models describes gate sequences, expectation values connects states to measured averages, and variance and covariance explains the uncertainty of weighted estimates.

Variational objectives and repeated measurements

Choose an initial state, parameterized circuit, objective and a criterion for useful output. Then repeatedly prepare the circuit state, measure the required observables, and use the resulting cost or gradient estimates to propose new parameters. Stop when the task criterion or resource budget is reached, and evaluate the selected parameters with fresh measurements. The introductory treatments of McClean and collaborators and Cerezo and collaborators develop this hybrid structure.

The output might be a parameter vector, a quantum state or a measured number. For a state-preparation task, the optimized objective must constrain the properties that actually matter. For a numerical estimate, uncertainty and acquisition cost remain part of the answer. Optimization can also select favorable measurement noise: the lowest estimate among many trials tends to be too low. Fresh measurements assess the chosen state without reusing that selection fluctuation.

Changing parameters may bind new angles in one compiled circuit or trigger a different decomposition. Those choices can change both cost and noise. Likewise, adaptive shot allocations mean that measurements collected at different stages generally are not identically distributed samples of one fixed state.

Objective, Estimand, and Estimator

Three objects are easy to conflate:

1. the ideal objective defined by the mathematical problem;
2. the implemented estimand defined by the compiled circuit and physical experiment;
3. the finite-data estimator computed from observed records.

For an ideal pure-state objective,

$$C_{\mathrm{ideal}}(\boldsymbol{\theta}) = \operatorname{Tr} \left[ \rho_{\mathrm{ideal}}(\boldsymbol{\theta})O \right].$$

Compilation approximation and noise produce a physical state $\rho_{\mathrm{phys}}$, so the hardware estimand is

$$C_{\mathrm{phys}}(\boldsymbol{\theta},t) = \operatorname{Tr} \left[ \rho_{\mathrm{phys}}(\boldsymbol{\theta},t)O_{\mathrm{impl}} \right],$$

where $t$ denotes time-dependent context. A sample mean $\widehat C$ estimates $C_{\mathrm{phys}}$, not automatically $C_{\mathrm{ideal}}$. The useful decomposition is

$$\widehat C-C_{\mathrm{ideal}} = \bigl(\widehat C-C_{\mathrm{phys}}\bigr) + \bigl(C_{\mathrm{phys}}-C_{\mathrm{ideal}}\bigr).$$

The first term is statistical error. The second includes coherent miscalibration, decoherence, readout error, drift, compilation approximation, and any mismatch between the intended and realized observable. More shots reduce the first term but need not reduce the second.

Objectives built from many observables

Suppose

$$O = \sum_{a=1}^{M}w_a O_a, \qquad \mu_a(\boldsymbol{\theta}) = \langle O_a\rangle_{\boldsymbol{\theta}}.$$

With separately estimated terms,

$$\widehat C = \sum_{a=1}^{M}w_a\widehat\mu_a.$$

For independent, stationary settings, let term $a$ receive $N_a$ shots with single-shot variance $\sigma_a^2$. Then

$$\operatorname{Var}(\widehat C) = \sum_{a=1}^{M} \frac{w_a^2\sigma_a^2}{N_a}.$$

For fixed total shots $N=\sum_a N_a$, the continuous optimum is

$$N_a \propto \lvert w_a\rvert\sigma_a.$$

A Lagrange multiplier gives $-w_a^2\sigma_a^2/N_a^2+\lambda=0$, which yields this allocation. The resulting minimum variance is $(\sum_a|w_a|\sigma_a)^2/N$. Terms with nonzero variance need positive allocations; a variance inferred as zero from a small pilot sample is not a proof that the term is deterministic.

Uniform allocation is therefore not generally optimal. In practice, $\sigma_a$ is unknown and can be learned from pilot data. Commuting terms can sometimes share measurement settings, but grouping introduces covariance and changes circuit count, basis-change depth, and statistical analysis. The measurement design must be optimized as a whole rather than term by term.

Nonlinear postprocessing

Ratios, logarithms, normalization by estimated quantities, postselected conditional means, and mitigation inverses can be biased at finite sample size. For a nonlinear map $g$,

$$\mathbb E[g(\widehat{\boldsymbol{\mu}})] \neq g(\mathbb E[\widehat{\boldsymbol{\mu}}])$$

in general. Bootstrap intervals can help with irregular estimators, but only if resampling respects the experimental hierarchy. Analytic propagation, likelihood methods, or simulation-based calibration may be preferable.

Parameterized Circuit Families

An ansatz is the map

$$\boldsymbol{\theta} \longmapsto \lvert\psi(\boldsymbol{\theta})\rangle.$$

Its reachable set is a manifold or stratified subset of state space, often of far lower dimension than the full Hilbert space. The key question is not whether the family can approximate arbitrary states, but whether it can reach useful states for the target instance at acceptable depth and can be searched with available precision.

Problem-inspired circuits

Problem-inspired ansatzes use generators, symmetries, conserved quantities, or known limiting states from the application. A layered form is

$$U(\boldsymbol{\theta}) = \prod_{\ell=1}^{L} \prod_{k=1}^{K} e^{-i\theta_{\ell k}G_k}.$$

If the generators commute with a symmetry $S$ and the initial state lies in one symmetry sector, then the circuit remains there:

$$[G_k,S]=0 \quad\Longrightarrow\quad [U(\boldsymbol{\theta}),S]=0.$$

This can exclude invalid states and reduce the search space. It can also exclude the solution if the sector, encoding, or assumed symmetry is wrong. Constraints should therefore be justified from the problem, not imposed only because they simplify optimization.

Hardware-efficient circuits

Hardware-efficient ansatzes alternate native single-qubit rotations and entangling layers chosen to match connectivity. They can minimize compiled depth for a given number of layers, but the phrase does not mean efficient optimization or favorable asymptotic scaling. Deep, highly random families can be expressive while producing concentrated costs and gradients. Native gates can also drift, crosstalk, and vary strongly across qubits.

Adaptive and growing circuits

An adaptive method adds generators or layers according to measured information. This can keep early circuits shallow and allocate parameters where they appear useful. It also creates a nested selection process: each proposed operator, gradient estimate, and stopping decision consumes measurements. Comparisons must count the rejected candidates and all intermediate circuits, not only the final compact ansatz.

Expressibility is not the objective

One expressibility diagnostic compares the distribution of state overlaps generated by the ansatz with the Haar distribution. Such metrics can rank circuit families, but closeness to Haar-random states is not synonymous with task performance. An ansatz may be:

• too restricted to represent the target;
• expressive enough for the target but easy to train;
• highly expressive yet redundant and statistically untrainable;
• expressive in ideal simulation but ineffective after noise.

The desired family is task sufficient, symmetry appropriate, compilable, and trainable under the actual estimator. Maximum generic expressibility is usually neither necessary nor desirable.

Exact Quantum Gradients

For

$$f(\theta) = \langle\psi_0\rvert U^\dagger(\theta)OU(\theta) \lvert\psi_0\rangle,$$

a derivative can often be written as a linear combination of expectation values evaluated by shifted circuits. This avoids differentiating sampled bit strings as though they were deterministic floating-point outputs.

Two-eigenvalue parameter-shift rule

Consider one gate

$$R_G(\theta) = e^{-i\theta G},$$

where the Hermitian generator $G$ has eigenvalues $\{-r,+r\}$. Holding all other gates fixed,

$$\frac{\partial f}{\partial\theta} = r \left[ f(\theta+s)-f(\theta-s) \right], \qquad s=\frac{\pi}{4r}.$$

For

$$R_P(\theta) = e^{-i\theta P/2}, \qquad P^2=I,$$

one has $r=1/2$ and therefore

$$\frac{\partial f}{\partial\theta} = \frac12 \left[ f\!\left(\theta+\frac{\pi}{2}\right) - f\!\left(\theta-\frac{\pi}{2}\right) \right].$$

This identity is exact for the ideal expectation function. Its finite-shot implementation remains a noisy gradient estimator. If one parameter controls several gates, the chain rule contributes once per occurrence unless a generalized rule exploits the full Fourier spectrum.

Generators with more than two distinct eigenvalues generally require more shifted evaluations or stochastic rules. Fixed, parameter-independent quantum channels before and after the shifted gate preserve the rule for the noisy expectation value, because the channel and expectation are linear. The result need not be the ideal gradient. Parameter-dependent noise, a compilation change or nonlinear conditional normalization can invalidate the two-point identity. For a postselected ratio $f(\theta)=a(\theta)/p(\theta)$, differentiate the numerator and acceptance probability and use the quotient rule; do not simply shift the ratio.

The derivations of Mitarai and collaborators and Schuld and collaborators apply the gate’s frequency structure. Wierichs and collaborators give generalized shift rules; Banchi and Crooks develop a stochastic rule for more general evolution.

Gradient-estimator variance

If the two shifted sample means are independent with variances $v_+$ and $v_-$, the Pauli-rotation rule gives

$$\operatorname{Var}(\widehat{\partial_\theta f}) = \frac14 \left( v_++v_- \right).$$

For $N_\pm$ independent shots, $v_\pm=\sigma_\pm^2/N_\pm$; these are not the single-shot variances. Using common random numbers is not usually literal on hardware, because measurement outcomes from distinct quantum circuits are independent. Correlated calibration blocks or paired execution schedules can nevertheless reduce drift mismatch, and covariance must then be included explicitly.

For $p$ parameters, a naive full parameter-shift gradient can require order $2p$ objective evaluations per iteration, each of which may contain many measurement settings. This multiplicative cost is often more important than the nominal depth of one ansatz circuit.

Finite differences

The centered finite difference

$$\widehat g_j = \frac{ \widehat C(\boldsymbol{\theta}+h\mathbf e_j) - \widehat C(\boldsymbol{\theta}-h\mathbf e_j) }{2h}$$

has truncation bias of order $h^2$ for a smooth objective, while its sampling variance scales as order $1/(N h^2)$. Making $h$ smaller reduces truncation bias but amplifies shot noise, calibration quantization, and drift. A finite-difference step therefore requires an explicit bias-variance choice.

Simultaneous perturbation

Simultaneous perturbation stochastic approximation (SPSA) draws a random direction $\boldsymbol{\Delta}$, often with independent entries in $\{-1,+1\}$, and uses two cost evaluations:

$$\widehat g_j = \frac{ \widehat C(\boldsymbol{\theta}+c\boldsymbol{\Delta}) - \widehat C(\boldsymbol{\theta}-c\boldsymbol{\Delta}) }{2c\Delta_j}.$$

Its circuit-evaluation count does not grow linearly with $p$ per stochastic gradient estimate, but the estimate can have high variance and requires careful gain schedules. “Two evaluations” is not “two shots”: each cost may still require many circuits and measurements.

Classical Optimization

No optimizer is uniformly best for VQAs. The relevant regime combines noisy function evaluations, periodic parameters, constraints, heterogeneous curvature, device drift, expensive batches, and sometimes discrete ansatz choices.

First-order stochastic methods

An elementary update is

$$\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta_t\widehat{\boldsymbol g}_t.$$

Stochastic-gradient methods can converge with unbiased finite-variance estimators under regularity and step-size assumptions. VQA gradients may be estimated by sampling shots, observable terms, data records, or combinations of these. Such convergence statements do not guarantee reaching the global minimum of a nonconvex objective, and they do not rescue exponentially small signals.

Momentum and adaptive coordinate scaling can improve empirical behavior, but their hyperparameters and stopping rules are part of the algorithm. Tuning them on the reported instances without accounting for selection exaggerates performance.

Derivative-free methods

Nelder–Mead, Powell-type searches, coordinate methods, Bayesian optimization, and trust-region model building can be useful when gradients are unavailable or very noisy. Their decisions still depend on resolving cost differences. In a barren plateau those differences can be exponentially suppressed, so choosing a gradient-free optimizer does not by itself remove the information problem.

Curvature and trust regions

Quasi-Newton and trust-region methods use local models to adapt steps to curvature and uncertainty. They can reduce iteration count but may require additional evaluations, stable Hessian approximations, or bounds on model error. A noisy optimizer should reject or shrink a step when the predicted improvement is not statistically resolved, rather than treating every fluctuation as a descent direction.

Quantum Geometry and Natural Gradient

The same physical state can have many parameter descriptions, and equal Euclidean parameter steps need not represent equal changes in state. For a normalized pure-state family, the Fubini–Study metric is

$$g_{jk} = \operatorname{Re} \left[ \langle\partial_j\psi\vert\partial_k\psi\rangle - \langle\partial_j\psi\vert\psi\rangle \langle\psi\vert\partial_k\psi\rangle \right].$$

It defines the local line element

$$ds^2 = \sum_{j,k} g_{jk}\,d\theta_jd\theta_k.$$

For pure states, the quantum Fisher information matrix is $4g$ under a common convention. Because authors differ by this factor, an implementation should state which matrix it uses.

Quantum natural gradient chooses a step by solving

$$\left( g+\lambda I \right) \delta\boldsymbol{\theta} = - \eta\nabla C.$$

The construction of Stokes and collaborators uses the geometry of quantum states. With $\lambda=0$ and nonsingular $g$, the infinitesimal natural-gradient direction transforms correctly under a smooth invertible change of coordinates. At a rank-deficient point, restrict to identifiable tangent directions or handle the null directions explicitly.

Adding $\lambda I$ stabilizes a numerical solve, but $I$ selects a Euclidean metric in the chosen coordinates and generally breaks that invariance. Diagonal approximations and finite Euler steps also need not be invariant. For example, if $\theta=2\phi$ and $g_{\theta\theta}=1/4$, then $g_{\phi\phi}=1$. The unregularized steps describe the same physical tangent; applying the same positive $\lambda$ in both coordinate systems generally does not.

Geometry is not free. Estimating $g$ can require additional circuits and shots, and inverting an ill-conditioned matrix amplifies estimator noise. The comparison that matters is total cost to a validated answer, not iterations to a low training objective.

Redundant parameters

If a nonzero vector $\boldsymbol v$ satisfies

$$g\boldsymbol v=0,$$

then the corresponding tangent has zero Fubini–Study length: its first-order change is at most a global phase. The state can still change at higher order along that coordinate direction. Such null directions can come from repeated generators, circuit identities, symmetries, or state-dependent stabilizers. They create flat directions without necessarily creating a many-qubit barren plateau.

The effective local dimension is

$$d_{\mathrm{eff}} = \operatorname{rank}(g).$$

When $d_{\mathrm{eff}}<p$, reporting only the number of trainable parameters overstates the local capacity. For an exact redundancy, such as two consecutive rotations about the same axis, combining parameters removes the redundant coordinate without changing the states. A metric that loses rank only at an isolated point does not by itself justify deleting a parameter from the whole ansatz.

Barren Plateaus

A barren plateau is a scaling phenomenon, not merely a plot that looks flat. For an ensemble of instances or random initializations, a common diagnostic is

$$\mathbb E_{\boldsymbol{\theta}} \left[ \partial_j C \right] = 0, \qquad \operatorname{Var}_{\boldsymbol{\theta}} \left[ \partial_j C \right] \in \mathcal O(b^{-n}),$$

for some $b>1$ as the number of qubits $n$ grows. Typical gradients then become exponentially small. Resolving their sign or relative size with incoherent sampling can require exponentially many measurements.

This definition is about a sequence of problem sizes and a specified sampling ensemble. A small gradient at one point may instead indicate a local optimum, a saddle, a symmetry, a redundant parameter, an insensitive observable, or a poor coordinate scale. Conversely, visibly nonzero gradients on eight qubits do not establish polynomial trainability.

Randomness and unitary designs

For sufficiently expressive randomly initialized circuits, parts of the circuit can approximate unitary 2-designs. Under the assumptions of the standard results, concentration of measure makes expectation gradients exponentially small. Depth, connectivity, gate ensemble, initial state, and observable all affect when that regime appears.

The lesson is not that every deep circuit has a barren plateau. It is that generic expressibility can erase the structured signal the optimizer needs. Random initialization should be treated as a substantive algorithmic choice.

Global and local costs

The support of the measured observable matters. Global costs can concentrate even for shallow circuits. In particular models, replacing a global fidelity- like objective with a sum of local costs changes exponential gradient scaling to polynomial scaling while preserving the same exact optimum.

That is not a universal license to localize every objective. A surrogate local cost must remain operational: low surrogate loss should imply success on the original task, with a quantitative bound if possible. Otherwise trainability is purchased by optimizing the wrong quantity.

Noise-induced plateaus

Noise contracts distinguishable states and can suppress both objective variation and gradients. The theorem of Wang and collaborators assumes layerwise local Pauli noise that strictly contracts every nonidentity Pauli component, together with its stated circuit and observable bounds. It gives exponential gradient suppression with depth; polynomial prefactors do not offset that suppression when depth grows linearly with $n$. A dephasing channel that preserves $Z$, or the identity channel, does not satisfy the strict-contraction premise.

Nonunital noise requires a separate analysis. Singkanipa and Lidar identify noise-induced limit sets, but do not imply that every parameter’s gradient vanishes for every nonunital circuit. For instance, $L$ amplitude-damping steps leave $|0\rangle$ fixed; a final $R_y(\theta)$ still gives $\langle Z\rangle=\cos\theta$ for every $L$. If the rotation precedes the damping instead, with excitation survival probability $\eta$ per step, then

$$C_L(\theta)=1-\eta^L+\eta^L\cos\theta, \qquad C_L'(\theta)=-\eta^L\sin\theta.$$

Noise type and the position of the parameter in the circuit both matter.

This mechanism differs from random-circuit concentration. A carefully initialized problem-inspired ansatz can still lose trainable signal as noisy depth grows. Error mitigation may reduce bias, but its sampling overhead and stability must be included before claiming that it restores trainability.

Gradient-free optimization does not evade concentration

Derivative-free methods compare nearby or modeled cost values. In a barren plateau, those differences are suppressed along with gradients. Resolving them still demands high precision. Changing optimizers can improve finite-size behavior, but it does not remove an information-theoretic signal-to-noise bottleneck.

Worst-case hardness

Bittel and Kliesch show that training broad classes of variational algorithms is NP-hard in the worst case, even for some systems whose underlying quantum dynamics are classically tractable. This result rules out a universal efficient classical optimizer under standard complexity assumptions. It does not prove that every physical instance, ansatz, or initialization is hard. Complexity statements must retain their quantifiers.

Designing for Trainability

There is no single cure, but several design principles can improve the available signal.

Use structure before capacity

Choose initial states, generators, symmetries, and connectivity from the problem. Verify that the target is reachable in the chosen sector. Add depth only when a shallower family fails a prespecified approximation test.

Problem inspiration is not itself a proof against barren plateaus. The dynamical Lie algebra generated by the ansatz, the initial state, and the observable can still produce concentration. Numerical gradient scaling over a range of sizes is useful evidence, but a narrow range should not be fitted to an asymptotic law with false confidence.

Initialize near a meaningful map

Options include:

• parameters corresponding to a known limiting solution;
• identity-block initialization, where new gate blocks initially compose to the identity;
• parameter transfer from a nearby instance or smaller system;
• layerwise growth, with new layers initialized not to perturb the current state;
• restricted randomization around a structured point.

These methods can preserve initial gradients. They can also bias the search toward one basin, so multiple structured seeds and transparent failure reporting remain important.

Match the cost to the information scale

Prefer observables whose changes are resolvable at the available shot budget. Normalize weighted sums so that one large coefficient does not dominate optimizer scaling. For constraints on expectation values, one possible penalty is

$$C_\lambda = C_0 + \sum_r \lambda_r \langle A_r\rangle^2,$$

This penalizes $\langle A_r\rangle\ne0$; it does not generally enforce the stronger condition $A_r|\psi\rangle=0$. For a Hermitian operator, $\langle A_r^2\rangle=0$ does enforce support in its kernel. For example, let $N=n_1+n_2$ and $A=N-1$. The state $(|00\rangle+|11\rangle)/\sqrt2$ has $\langle A\rangle=0$ but $\langle A^2\rangle=1$ and no one-particle component. A penalty on $\langle(N-1)^2\rangle$ detects that violation.

Squaring a sample mean adds another distinction: $\mathbb E[\widehat\mu^2]=\mu^2+\sigma^2/N$ for $N$ independent shots. Thus even the intended mean-value penalty has a finite-sample bias unless corrected or estimated with independent batches. Penalties also change curvature and measurement cost. A coefficient too small permits invalid states; one too large can make the landscape ill-conditioned. Report the chosen scale and a constraint-violation curve.

Grow precision with optimization

Early iterations may need only the direction of a large improvement. Late iterations may require enough shots to distinguish small changes. An adaptive policy can increase shots according to estimated variance, gradient norm, or trust-region acceptance.

For an estimated component $\widehat g_j$ with standard error $\operatorname{SE}(\widehat g_j)$, a simple signal diagnostic is

$$R_j = \frac{ \lvert\widehat g_j\rvert }{ \operatorname{SE}(\widehat g_j) }.$$

This ratio is not a universal stopping test, especially after selecting the largest component, but it exposes updates driven mainly by measurement noise. Prespecify how the shot budget changes when $R_j$ is small.

Noise, Drift, and Mitigation

On hardware, optimization targets the time-dependent implemented objective $C_{\mathrm{phys}}(\boldsymbol{\theta},t)$. If calibration changes during the loop, the optimizer sees a moving surface:

$$\frac{dC_{\mathrm{phys}}}{dt} = \nabla_{\boldsymbol{\theta}}C_{\mathrm{phys}} \cdot \dot{\boldsymbol{\theta}} + \left. \frac{\partial C_{\mathrm{phys}}}{\partial t} \right|_{\boldsymbol{\theta}}.$$

The first term on the right is intended optimization; the last term is drift. Interleaving reference circuits, randomizing execution order, and blocking paired parameter-shift circuits can help distinguish them. A single calibration snapshot before a long run is rarely enough to establish stationarity.

Noise can have several qualitatively different effects:

• bias: the minimum value and minimizer move;
• variance: shot-to-shot outcomes broaden;
• smoothing: high-frequency landscape features are attenuated;
• false structure: coherent errors introduce new parameter dependence;
• leakage or loss: the effective state space and retention probability change;
• nonstationarity: the objective changes during training.

Error mitigation changes the estimator. Readout correction, probabilistic error cancellation, zero-noise extrapolation, symmetry verification, and postselection have different assumptions and overheads. A mitigated objective can have lower bias and much larger variance. Optimization on mitigated values also creates adaptive selection effects. Compare raw and mitigated estimates with their uncertainties and rejected-trial costs. The noise overview explains the physical channels; each mitigation method needs its own assumptions about calibration and sampling.

A One-Qubit Worked Example

Take

$$\lvert\psi(\theta)\rangle = R_y(\theta)\lvert0\rangle, \qquad C(\theta) = \langle Z\rangle_\theta.$$

The exact state is

$$\lvert\psi(\theta)\rangle = \cos\frac{\theta}{2}\lvert0\rangle + \sin\frac{\theta}{2}\lvert1\rangle,$$

so

$$C(\theta) = \cos\theta, \qquad \frac{dC}{d\theta} = -\sin\theta.$$

The parameter-shift rule returns

$$\begin{aligned} \frac12 \left[ C\!\left(\theta+\frac{\pi}{2}\right) - C\!\left(\theta-\frac{\pi}{2}\right) \right] &= \frac12 \left[ -\sin\theta-\sin\theta \right] \\ &= -\sin\theta. \end{aligned}$$

Each $Z$ measurement is a random variable $X\in\{-1,+1\}$ with

$$\operatorname{Var}(X) = 1-C(\theta)^2 = \sin^2\theta.$$

With $N$ shots at each shifted angle, the gradient estimator has variance

$$\operatorname{Var}(\widehat{C'})=\frac{\cos^2\theta}{2N}.$$

At $\theta=\pi/6$, the two shifted means are $-1/2$ and $+1/2$, so the derivative is $-1/2$. With $N=1000$ shots per shifted point, its standard error is $\sqrt{3/8000}\simeq0.0194$. This costs $2000$ state preparations, even though the derivative formula has only two terms.

For $R_y(\theta)|0\rangle$ measured in $Z$, the cost is $\cos\theta$. The lower panel plots variance multiplied by $N$: $N\operatorname{Var}(\widehat C)=\sin^2\theta$ for $N$ direct shots, and $N\operatorname{Var}(\widehat{C'})=\cos^2\theta/2$ for $N$ shots at each of two shifted angles. The gradient estimate therefore uses twice as many preparations as the direct cost estimate.

Near $\theta=0$, the gradient is small because this point is a maximum of the cost, not because of a barren plateau: there is no system-size scaling here. Near $\theta=\pi/2$, both shifted circuits have deterministic ideal outcomes, but hardware noise can reintroduce variance and bias. Even this trivial example separates exact calculus, shot statistics, and physical implementation.

Stopping without mistaking noise for improvement

A small estimated gradient can mean a stationary point, inadequate shots or a poor parameterization. A stopping rule should distinguish “the task criterion is met” from “no further useful improvement was resolved before the budget ran out.” Fresh measurements of the selected point help separate its actual performance from favorable noise encountered during selection.

For repeated statistical tests, a fixed-point confidence interval does not automatically remain valid after choosing when to stop. Use a simultaneous error allocation or a method valid under the stated adaptive sampling. Exercise8 gives a simple conservative construction. For a claim across instances, also evaluate new instances from a specified distribution; fresh shots on one selected instance answer a different question.

Check small cases with exact simulation and assess properties not fixed by the training objective, such as constraint violations or held-out observables. The algorithmic benchmarking page develops comparisons across problem instances.

Resource Accounting

Let iteration $t$ request circuit configurations $\mathcal C_t=\{c_{t1},\ldots,c_{tK_t}\}$ with attempted shot counts $N_{tk}$, including subsequently rejected outcomes. A basic quantum acquisition count is

$$N_{\mathrm{shots}} = \sum_t \sum_{k=1}^{K_t} N_{tk}.$$

Counting attempted shots prevents postselection from hiding rejected trials. Reset time, extra calibration or mitigation circuits, queueing and classical work still affect elapsed time. One possible decomposition is

$$T_{\mathrm{total}} = T_{\mathrm{pre}} + T_{\mathrm{compile}} + T_{\mathrm{queue}} + T_{\mathrm{execute}} + T_{\mathrm{classical}} + T_{\mathrm{validate}}.$$

For a batch-access device, quantum–classical round trips may dominate. Two optimizers with the same iteration count can request very different numbers of shots, shifted circuits or metric measurements. Compare total work, including failed seeds and tuning, at the same task accuracy and success probability. Resource estimation explains conversions from abstract circuit counts to a specified implementation.

The appropriate classical comparison depends on the task: exact diagonalization, tensor networks, Monte Carlo, classical variational families or optimization heuristics may be relevant. A small instance that is classically simulable can validate an experiment without showing an advantage. A broader advantage claim requires representative scaling and a comparably tuned classical method, as discussed in verification of quantum advantage.

Common pitfalls

An ansatz is not yet an algorithm. The parameterized circuit needs an objective, a measurement procedure and an update rule. Useful output must be assessed separately from a decreasing training trace.

A flat trace is not by itself a barren plateau. Check ordinary stationarity, inactive parameters, measurement resolution and drift before studying gradient scaling across sizes and initializations.

A best-of-many run is not typical performance. Fresh measurements can assess that selected run, but all attempted runs contribute to its acquisition cost. Report a typical-run claim and a best-of-many procedure separately.

Where Variational Algorithms Are Used

VQAs appear in ground- and excited-state estimation, combinatorial optimization, dynamical simulation, linear-system objectives, state preparation, compilation, error correction, quantum machine learning, and metrology. These applications share hybrid optimization but differ in what their objectives certify.

The connection to Optimal Control is especially close: both optimize parameterized quantum evolution. Control usually treats physical pulse fields and dynamical constraints as primary, whereas circuit VQAs often treat a gate-level ansatz and an algorithmic objective as primary. The mathematical tools overlap, but their physical constraints and useful outputs differ.

The hybrid architecture, gate-specific gradient identities and cited concentration theorems are established mathematical tools. Their combination does not guarantee efficient optimization of arbitrary instances. Current questions about scalable trainability and utility are discussed in quantum algorithm discovery and negative results and limitations.

Exercises

1. Derive the parameter-shift rule

Let

$$R_P(\theta) = e^{-i\theta P/2}, \qquad P^2=I.$$

Show directly that an expectation $f(\theta)$ is a trigonometric polynomial of the form $a+b\cos\theta+c\sin\theta$, and derive the two-point shift rule.

Solution

Because $P^2=I$,

$$R_P(\theta) = \cos\frac{\theta}{2}I - i\sin\frac{\theta}{2}P.$$

Substituting this expression and its adjoint around the observable produces terms proportional to $\cos^2(\theta/2)$, $\sin^2(\theta/2)$, and $\sin(\theta/2)\cos(\theta/2)$. Double-angle identities therefore give

$$f(\theta) = a+b\cos\theta+c\sin\theta.$$

Its derivative is

$$f'(\theta) = -b\sin\theta+c\cos\theta.$$

Meanwhile,

$$\frac12 \left[ f\!\left(\theta+\frac{\pi}{2}\right) - f\!\left(\theta-\frac{\pi}{2}\right) \right] = -b\sin\theta+c\cos\theta.$$

Thus the shifted expression equals $f'(\theta)$ exactly.

2. Allocate shots between observables

An objective is

$$C = 3\langle O_1\rangle - \langle O_2\rangle.$$

Pilot measurements estimate single-shot standard deviations $\sigma_1=0.4$ and $\sigma_2=0.9$. Allocate $10{,}000$ shots to minimize the variance when the terms are measured independently.

Solution

The continuous optimum obeys

$$N_a \propto \lvert w_a\rvert\sigma_a.$$

The weights are

$$3(0.4)=1.2, \qquad 1(0.9)=0.9.$$

Therefore

$$N_1 = 10000\frac{1.2}{2.1} \approx 5714,$$

and

$$N_2 \approx 4286.$$

Integer rounding can be adjusted to preserve the total. The derivation assumes independent settings and known stable variances; grouping or drift changes the allocation problem.

3. Separate bias from variance

A simulator predicts $C_{\mathrm{ideal}}=-1.20$. Hardware repetitions give $\widehat C=-1.05$ with standard error $0.01$. Explain what increasing the shot count by a factor of $100$ can and cannot establish.

Solution

Under independent stationary sampling, the standard error falls by a factor of $10$, to about $0.001$. This measures the hardware estimand more precisely. It does not force that estimand toward $-1.20$. The observed difference of $0.15$ may be physical bias from noise, compilation, readout, or drift. More shots distinguish a stable discrepancy more sharply but do not diagnose or remove it.

4. Identify a redundant parameter

Consider

$$U(\theta_1,\theta_2) = R_z(\theta_1)R_z(\theta_2)$$

acting on an arbitrary state. Find a null direction of the state-space metric.

Solution

Because rotations about the same axis compose,

$$U(\theta_1,\theta_2) = R_z(\theta_1+\theta_2).$$

Only the sum matters. The displacement

$$\delta\boldsymbol{\theta} = \epsilon(1,-1)$$

leaves the unitary exactly unchanged, so $(1,-1)$ is a null direction of the Fubini–Study metric for every input state. The two-coordinate model has at most one effective local dimension.

5. Diagnose a flat trace

A ten-qubit run shows nearly constant cost for 50 iterations. List four checks needed before calling this a barren plateau.

Solution

Check whether:

1. gradients and cost differences are below the estimator’s resolution;
2. the initialization is already near a stationary point;
3. symmetries or redundant parameters make the chosen directions inactive;
4. calibration drift or optimizer step sizes obscure genuine changes.

Then study gradient distributions over initializations and a sequence of problem sizes. A barren-plateau claim requires exponential scaling under a specified ensemble, not one flat optimization history.

6. Count a naive gradient batch

An objective has 40 independently measured groups. A circuit has 120 parameters, each appearing in one Pauli rotation. A full parameter-shift gradient uses 2,000 shots per group and shifted point. How many shots does one gradient batch use?

Solution

There are two shifted points per parameter, so the number of group evaluations is

$$2(120)(40) = 9600.$$

At 2,000 shots each,

$$N_{\mathrm{shots}} = 9600(2000) = 19{,}200{,}000.$$

This excludes the unshifted objective, metric estimation, calibration, validation, rejected trials, and repeated seeds. The example shows why circuit depth alone is a poor proxy for VQA cost.

7. A correct mean can hide the wrong particle number

For $N=n_1+n_2$, compare $|01\rangle$ with $|\Phi^+\rangle=(|00\rangle+|11\rangle)/\sqrt2$. Compute $\langle N\rangle$, $\langle(N-1)^2\rangle$ and the probability of measuring $N=1$. Then explain the finite-sample bias of estimating $\langle N-1\rangle^2$ by the square of a sample mean.

Solution

Both states have $\langle N\rangle=1$. For $|01\rangle$, $N=1$ with certainty and $\langle(N-1)^2\rangle=0$. For $|\Phi^+\rangle$, the outcomes are $0$ and $2$ with equal probabilities, so the squared deviation is always $1$ and $N=1$ never occurs. Matching the mean is not the same as occupying the one-particle sector.

On the Bell state, measuring $A=N-1$ gives $\pm1$ equally. For $m$ independent samples, $\mathbb E[\widehat{\langle A\rangle}^{\,2}]=1/m$, even though $\langle A\rangle^2=0$. One unbiased estimator of the squared mean is the average product of distinct samples,

$$\frac{(\sum_{i=1}^m A_i)^2-\sum_{i=1}^m A_i^2}{m(m-1)},\qquad m\ge2.$$

It can be negative on one finite data set; unbiasedness is a statement about its mean over repeated experiments. Alternatively, multiply sample means from two independent batches.

8. Design a stopping rule under shot noise

Suppose at most $K$ candidate points are assessed, possibly chosen adaptively. At assessment $t$, collect $n$ fresh independent outcomes in $[-1,1]$ at the selected point. Construct simultaneous bounds with total failure probability at most $\alpha$, and give a rule for accepting a target $C\le C_*$. Assume each assessment samples a stable mean; this does not bound physical model bias.

Solution

Conditioned on the preceding history, Hoeffding’s inequality gives

$$\Pr(|\widehat C_t-C_t|>r\mid\text{history}) \le2e^{-nr^2/2}.$$

Choose $r=\sqrt{2\log(2K/\alpha)/n}$. Each assessment then fails with probability at most $\alpha/K$, including after averaging over the history. A union bound shows that all $K$ intervals hold together with probability at least $1-\alpha$.

Accept a point only when $\widehat C_t+r\le C_*$. Otherwise continue, or stop at the fixed budget and report that the target was not established. The guarantee survives adaptive choice of the points because each test uses fresh shots and the total error was allocated across all possible assessments. It does not prove that an unaccepted point is bad, that the selected point is a global optimum, or that the physical mean equals the ideal objective.

References

• A. Arrasmith, M. Cerezo, P. Czarnik, L. Cincio, and P. J. Coles, “Effect of barren plateaus on gradient-free optimization,” Quantum 5, 558 (2021), doi:10.22331/q-2021-10-05-558.
• L. Banchi and G. E. Crooks, “Measuring analytic gradients of general quantum evolution with the stochastic parameter shift rule,” Quantum 5, 386 (2021), doi:10.22331/q-2021-01-25-386.
• K. Bharti et al., “Noisy intermediate-scale quantum algorithms,” Reviews of Modern Physics 94, 015004 (2022), doi:10.1103/RevModPhys.94.015004.
• L. Bittel and M. Kliesch, “Training variational quantum algorithms is NP-hard,” Physical Review Letters 127, 120502 (2021), doi:10.1103/PhysRevLett.127.120502.
• M. Cerezo et al., “Variational quantum algorithms,” Nature Reviews Physics 3, 625–644 (2021), doi:10.1038/s42254-021-00348-9.
• M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, “Cost function dependent barren plateaus in shallow parametrized quantum circuits,” Nature Communications 12, 1791 (2021), doi:10.1038/s41467-021-21728-w.
• S. Endo, Z. Cai, S. C. Benjamin, and X. Yuan, “Hybrid quantum-classical algorithms and quantum error mitigation,” Journal of the Physical Society of Japan 90, 032001 (2021), doi:10.7566/JPSJ.90.032001.
• E. Grant, L. Wossnig, M. Ostaszewski, and M. Benedetti, “An initialization strategy for addressing barren plateaus in parametrized quantum circuits,” Quantum 3, 214 (2019), doi:10.22331/q-2019-12-09-214.
• T. Haug, K. Bharti, and M. S. Kim, “Capacity and quantum geometry of parametrized quantum circuits,” PRX Quantum 2, 040309 (2021), doi:10.1103/PRXQuantum.2.040309.
• Z. Holmes, K. Sharma, M. Cerezo, and P. J. Coles, “Connecting ansatz expressibility to gradient magnitudes and barren plateaus,” PRX Quantum 3, 010313 (2022), doi:10.1103/PRXQuantum.3.010313.
• J. M. Kübler, A. Arrasmith, L. Cincio, and P. J. Coles, “An adaptive optimizer for measurement-frugal variational algorithms,” Quantum 4, 263 (2020), doi:10.22331/q-2020-05-11-263.
• M. Larocca et al., “Diagnosing barren plateaus with tools from quantum optimal control,” Quantum 6, 824 (2022), doi:10.22331/q-2022-09-29-824.
• J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, “The theory of variational hybrid quantum-classical algorithms,” New Journal of Physics 18, 023023 (2016), doi:10.1088/1367-2630/18/2/023023.
• J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, “Barren plateaus in quantum neural network training landscapes,” Nature Communications 9, 4812 (2018), doi:10.1038/s41467-018-07090-4.
• K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, “Quantum circuit learning,” Physical Review A 98, 032309 (2018), doi:10.1103/PhysRevA.98.032309.
• A. Peruzzo et al., “A variational eigenvalue solver on a photonic quantum processor,” Nature Communications 5, 4213 (2014), doi:10.1038/ncomms5213.
• J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018), doi:10.22331/q-2018-08-06-79.
• M. Schuld, V. Bergholm, C. Gogolin, J. Izaac, and N. Killoran, “Evaluating analytic gradients on quantum hardware,” Physical Review A 99, 032331 (2019), doi:10.1103/PhysRevA.99.032331.
• S. Sim, P. D. Johnson, and A. Aspuru-Guzik, “Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms,” Advanced Quantum Technologies 2, 1900070 (2019), doi:10.1002/qute.201900070.
• P. Singkanipa and D. A. Lidar, “Beyond unital noise in variational quantum algorithms: noise-induced barren plateaus and limit sets,” Quantum 9, 1617 (2025), doi:10.22331/q-2025-01-30-1617.
• A. Skolik, J. R. McClean, M. Mohseni, P. van der Smagt, and M. Leib, “Layerwise learning for quantum neural networks,” Quantum Machine Intelligence 3, 5 (2021), doi:10.1007/s42484-020-00036-4.
• J. C. Spall, “Multivariate stochastic approximation using a simultaneous perturbation gradient approximation,” IEEE Transactions on Automatic Control 37, 332–341 (1992), doi:10.1109/9.119632.
• J. Stokes, J. Izaac, N. Killoran, and G. Carleo, “Quantum natural gradient,” Quantum 4, 269 (2020), doi:10.22331/q-2020-05-25-269.
• R. Sweke et al., “Stochastic gradient descent for hybrid quantum-classical optimization,” Quantum 4, 314 (2020), doi:10.22331/q-2020-08-31-314.
• B. van Straaten and B. Koczor, “Measurement cost of metric-aware variational quantum algorithms,” PRX Quantum 2, 030324 (2021), doi:10.1103/PRXQuantum.2.030324.
• S. Wang et al., “Noise-induced barren plateaus in variational quantum algorithms,” Nature Communications 12, 6961 (2021), doi:10.1038/s41467-021-27045-6.
• D. Wierichs, J. Izaac, C. Wang, and C. Y.-Y. Lin, “General parameter-shift rules for quantum gradients,” Quantum 6, 677 (2022), doi:10.22331/q-2022-03-30-677.