Skip to content

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(𝛉)=⟨ψ(𝛉)|H|ψ(𝛉)⟩.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:

|ψ⟩=∑j c j|E j⟩,E(𝛉)=∑j|c j|2 E j≥E min.|\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+1 2 X H=Z+\tfrac12X and prepare |ψ(θ)⟩=R y(θ)|0⟩|\psi(\theta)\rangle=R_y(\theta)|0\rangle. Its Bloch vector is (sin θ,0,cos θ)(\sin\theta,0,\cos\theta), so

E(θ)=cos θ+1 2 sin θ.E(\theta)=\cos\theta+\tfrac12\sin\theta.

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

E(θ)=R cos(θ−δ).E(\theta)=R\cos(\theta-\delta).

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

If θ is restricted to [0,π][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 π 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 θ P/2 e^{-i\theta P/2} with P 2=I P^2=I, an expectation has the form a+b cos θ+c sin θ a+b\cos\theta+c\sin\theta. Therefore

d E d θ=E(θ+π/2)−E(θ−π/2)2.\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.

Laboratory L20 — Variational energy. Manipulate θ and φ for H=Z+X/2, inspect the state and energy, and take gradient steps on θ. Compare with the exact ground energy. The exact classical solution is displayed because this is a learning problem.

## 15.4 QAOA as alternating dynamics

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

|𝛄,𝛃⟩=e−i β p B e−i γ p C⋯e−i β 1 B e−i γ 1 C|+⟩⊗n.|\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 j Z k)/2(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].

Laboratory L21 — A QAOA triangle. Change γ and β, inspect the eight probabilities, and compare expected cut value with the optimum two. The graph and objective are fixed and explicitly shown.

## 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

15.1. Find the eigenvalues of Z+X/2 directly from its matrix.

Show solution / guidance

The determinant of (1−λ 1/2 1/2−1−λ)\begin{pmatrix}1-\lambda&1/2\\1/2&-1-\lambda\end{pmatrix} is λ 2−5/4\lambda^2-5/4. Eigenvalues are ±5/2\pm\sqrt5/2.

15.2. Verify the parameter-shift formula for E(θ)=cosθ+sinθ/2.

Show solution / guidance

Substitute θ±π/2 and subtract: the cosine contribution gives −2 sin θ-2\sin\theta, the sine contribution gives cos θ\cos\theta. Dividing by two matches the derivative.

15.3. What is the expected triangle cut value in the uniform state?

Show solution / guidance

Six strings have cost two and two have zero, so the expectation is (6⋅2)/8=3/2(6\cdot2)/8=3/2. Each edge also has probability 1/2 1/2 of being cut.

15.4. If β=0 in one-layer QAOA, can γ change computational-basis probabilities?

Show solution / guidance

No. The cost unitary is diagonal and changes only phases. Without a later noncommuting operation, the probabilities remain uniform.

15.5. A mitigated VQE energy estimate is below the exact ground energy. List two possible explanations consistent with quantum mechanics.

Show solution / guidance

Finite-shot fluctuation and mitigation bias can produce such an estimate. An incorrect Hamiltonian, calibration error, or software error are additional possibilities. The variational bound applies to the exact expectation of a physical state.

IN THIS CHAPTER