CHAPTER 15

Variational algorithms and their limits

Learning goals. Derive a variational energy, use a parameter-shift gradient, explore QAOA, and evaluate claims under noise and classical comparison.

15.1 A hybrid optimization loop

A parameterized circuit prepares $|\psi(\boldsymbol\theta)\rangle$. Measurements estimate a cost such as

$$E(\boldsymbol\theta)=\langle\psi(\boldsymbol\theta)|H| \psi(\boldsymbol\theta)\rangle.$$

A classical optimizer chooses new parameters, and the loop repeats. The variational principle follows by expanding the state in energy eigenstates:

$$|\psi\rangle=\sum_jc_j|E_j\rangle,\qquad E(\boldsymbol\theta)=\sum_j|c_j|^2E_j\ge E_{\min}.$$

This guarantee assumes the correct Hamiltonian and a physical normalized state. A finite-shot or mitigated estimate can fall below the exact ground energy due to sampling or estimator bias; that does not violate the theorem.

The variational quantum eigensolver (VQE) uses this loop to seek low-energy states [27]. Its performance depends on the ansatz, initialization, optimizer, measurement allocation, and noise. The variational principle gives an energy bound, not a guarantee that the optimizer reaches the best state.

15.2 A fully solvable example

Take $H=Z+\tfrac12X$ and prepare $|\psi(\theta)\rangle=R_y(\theta)|0\rangle$. Its Bloch vector is $(\sin\theta,0,\cos\theta)$, so

$$E(\theta)=\cos\theta+\tfrac12\sin\theta.$$

Let $R=\sqrt{1+1/4}=\sqrt5/2$ and $\delta=\arctan(1/2)$. Then

$$E(\theta)=R\cos(\theta-\delta).$$

The minimum is $-\sqrt5/2$ at $\theta=\pi+\delta$ modulo $2\pi$. Differentiating gives $E'(\theta)=-\sin\theta+\tfrac12\cos\theta$. The condition $\tan\theta=1/2$ has both maximum and minimum solutions; checking curvature or energy selects the minimum.

If θ is restricted to $[0,\pi]$ with relative phase zero, the circuit cannot reach every real direction needed for the optimum. Allowing a negative relative phase or the full $2\pi$ rotation removes that artificial restriction. Parameter ranges are part of an ansatz definition.

15.3 Parameter-shift gradients

For a parameter appearing once in a rotation $e^{-i\theta P/2}$ with $P^2=I$, an expectation has the form $a+b\cos\theta+c\sin\theta$. Therefore

$$\frac{dE}{d\theta} =\frac{E(\theta+\pi/2)-E(\theta-\pi/2)}2.$$

This is exact under the stated generator and occurrence assumptions. It is not a generic two-evaluation formula for every parameterization. If a shared parameter occurs in many gates, contributions must be treated correctly.

With finite-shot evaluations, the gradient also has uncertainty. Optimizing beyond that uncertainty can waste shots or follow noise. Adaptive measurement allocation and stopping criteria belong in a serious experimental workflow.

15.4 QAOA as alternating dynamics

For a bit-string objective C(x), define the diagonal operator $C=\sum_xC(x)|x\rangle\langle x|$ and mixer $B=\sum_jX_j$. A depth-p QAOA state is

$$|\boldsymbol\gamma,\boldsymbol\beta\rangle =e^{-i\beta_pB}e^{-i\gamma_pC}\cdots e^{-i\beta_1B}e^{-i\gamma_1C}|+\rangle^{\otimes n}.$$

For MaxCut, an edge (j,k) contributes $(I-Z_jZ_k)/2$, which is one when the bits differ. The cost phase does not change probabilities by itself; the mixer converts its relative phases into a changed output distribution.

For a triangle, every nonconstant assignment cuts two edges and the two constant strings cut zero. The optimum is two. The laboratory exactly simulates one QAOA layer and shows the entire distribution, so an improved expectation can be distinguished from certainty of the optimal string [28].

15.5 Trainability, noise, and honest benchmarks

A barren plateau is a regime where gradients become very small, often with variance decreasing rapidly with size under a specified random-circuit ensemble. It is not a theorem that every variational circuit is untrainable. Ansatz locality, depth, initialization, cost locality, and data structure matter [29].

An expressive ansatz may approximate many states but require expensive training. A restricted ansatz can be trainable yet miss the desired state. Noise can flatten a cost landscape or bias an optimum. An ideal state-vector optimizer provides information a hardware optimizer must estimate with shots.

A credible benchmark includes total quantum executions, classical optimizer effort, hyperparameter searches, state preparation, mitigation overhead, and the accuracy of the best relevant classical method. Comparing a carefully tuned quantum model with an untuned classical baseline is not evidence of a general advantage.

Annealing and adiabatic algorithms use different control models. In an ideal adiabatic argument, the system follows a changing Hamiltonian’s eigenstate when evolution is sufficiently slow relative to spectral-gap and smoothness conditions. A small minimum gap can make the required time large. A device’s ability to implement an Ising energy function does not establish efficient solutions to all hard optimization problems.

15.6 Exercises