Simple Algorithm
Quantum Computing · Excited State · 24 min

Variational Algorithms: VQE & QAOA

Hybrid quantum–classical loops for near-term devices.

Today's processors cannot run long algorithms, but they can prepare short parameterized circuits and measure them. Wrap that in a classical optimizer and you have the variational method, the workhorse of near-term quantum computing. Here you will prove why it works, derive how to get exact gradients out of a quantum device, and run it on a toy Hamiltonian, a two-spin magnet and a graph problem.

What you’ll learn

  • Prove the variational principle E(θ)≥E0E(\boldsymbol\theta)\ge E_0 and explain in what sense VQE energies are upper bounds.
  • Derive the parameter-shift rule and compare it with finite differences under shot noise.
  • Compare hardware-efficient, problem-inspired and adaptive ansätze, and common classical optimizers.
  • Write MaxCut as a cost Hamiltonian, build the QAOA circuit, and compute the p=1p=1 expectation value on a single edge.

The hybrid loop

A variational quantum algorithm has four ingredients:

  1. a cost Hamiltonian H=∑iciPiH=\sum_ic_iP_i, a real combination of Pauli strings PiP_i;
  2. an ansatz: a parameterized circuit U(θ)U(\boldsymbol\theta) preparing ∣ψ(θ)⟩=U(θ)∣0⋯0⟩\ket{\psi(\boldsymbol\theta)}=U(\boldsymbol\theta)\ket{0\cdots0};
  3. an estimator of E(θ)=⟨ψ(θ)|H|ψ(θ)⟩=∑ici⟨Pi⟩E(\boldsymbol\theta)=\mel{\psi(\boldsymbol\theta)}{H}{\psi(\boldsymbol\theta)}=\sum_ic_i\expval{P_i} built from shots;
  4. a classical optimizer that proposes the next θ\boldsymbol\theta.

The variational quantum eigensolver (Peruzzo et al., 2014) minimizes the energy of a molecular Hamiltonian. The QAOA (Farhi, Goldstone & Gutmann, 2014) maximizes a classical cost function encoded as a diagonal Hamiltonian. The quantum device does only what it is good at, preparing and sampling states that may be hard to represent classically; everything else is classical.

The variational principle

DerivationProof, and what the excess energy tells you
  1. ∣ψ⟩=∑kak∣k⟩,∑k∣ak∣2=1\ket\psi=\sum_ka_k\ket k,\qquad\sum_k\abs{a_k}^2=1

    Expand in an orthonormal eigenbasis H∣k⟩=Ek∣k⟩H\ket k=E_k\ket k with E0≤E1≤⋯E_0\le E_1\le\cdots:

  2. ⟨ψ|H|ψ⟩=∑k∣ak∣2Ek  ≥  E0∑k∣ak∣2=E0\mel{\psi}{H}{\psi}=\sum_k\abs{a_k}^2E_k\;\ge\;E_0\sum_k\abs{a_k}^2=E_0

    The energy is a weighted average of eigenvalues, so it cannot fall below the smallest:

  3. ∥Π0∣ψ⟩∥2  ≥  1−E(ψ)−E0Δ\norm{\Pi_0\ket\psi}^2\;\ge\;1-\frac{E(\psi)-E_0}{\Delta}

    Equality forces ∣ak∣2(Ek−E0)=0\abs{a_k}^2(E_k-E_0)=0 for every kk, so only ground-state components survive. More quantitatively, if the gap to the next distinct level is Δ\Delta, the weight of ∣ψ⟩\ket\psi in the ground eigenspace (projector Π0\Pi_0) obeys

  4. A mixed state is a convex combination of pure states, so Tr⁡(ρH)≥E0\Tr(\rho H)\ge E_0 follows by averaging. □\square

Apply it to H=0.8 Z+0.6 XH=0.8\,Z+0.6\,X, whose eigenvalues are ±0.82+0.62=±1\pm\sqrt{0.8^2+0.6^2}=\pm1. The ansatz ∣ψ(θ,φ)⟩=RZ(φ)RY(θ)∣0⟩\ket{\psi(\theta,\varphi)}=R_Z(\varphi)R_Y(\theta)\ket0 has Bloch vector (sin⁡θcos⁡φ, sin⁡θsin⁡φ, cos⁡θ)(\sin\theta\cos\varphi,\ \sin\theta\sin\varphi,\ \cos\theta), so

E(θ,φ)=0.8cos⁡θ+0.6sin⁡θcos⁡φ,min⁡E=−1  at  φ=π, tan⁡θ=−34  (θ≈2.50)E(\theta,\varphi)=0.8\cos\theta+0.6\sin\theta\cos\varphi,\qquad\min E=-1\ \text{ at }\ \varphi=\pi,\ \tan\theta=-\tfrac34\ \ (\theta\approx2.50)
The ground state has Bloch vector (−0.6,0,−0.8)(-0.6,0,-0.8), antiparallel to the "field" direction (0.6,0,0.8)(0.6,0,0.8).
Predict before you look

Freeze φ=0\varphi=0 and vary only θ∈[0,π]\theta\in[0,\pi] (the widget's range). What is the lowest energy this restricted ansatz can reach?

Show the answer

-0.8

With φ=0\varphi=0, E=0.8cos⁡θ+0.6sin⁡θE=0.8\cos\theta+0.6\sin\theta and sin⁡θ≥0\sin\theta\ge0: the Bloch vector is confined to the half-plane x≥0x\ge0, which excludes the ground state (−0.6,0,−0.8)(-0.6,0,-0.8). The minimum over [0,π][0,\pi] is at the endpoint θ=π\theta=\pi, where E=−0.8E=-0.8. The variational bound is only as good as the ansatz's reach: expressibility matters.

Gradients from the device: the parameter-shift rule

Gradient-based optimizers need ∂E/∂θk\partial E/\partial\theta_k. You cannot backpropagate through a quantum device, but for gates generated by Pauli operators the derivative is itself a difference of two expectation values at finite shifts.

DerivationThe parameter-shift rule
  1. E(θ)=cos⁡2 ⁣θ2 ⟨A⟩ϕ+sin⁡2 ⁣θ2 ⟨PAP⟩ϕ+sin⁡θ2cos⁡θ2 ⟨i[P,A]⟩ϕ=α+βcos⁡θ+γsin⁡θE(\theta)=\cos^2\!\tfrac\theta2\,\expval{A}_\phi+\sin^2\!\tfrac\theta2\,\expval{PAP}_\phi+\sin\tfrac\theta2\cos\tfrac\theta2\,\expval{i[P,A]}_\phi=\alpha+\beta\cos\theta+\gamma\sin\theta

    Isolate one parameter: E(θ)=⟨ϕ|eiθP/2Ae−iθP/2|ϕ⟩E(\theta)=\mel{\phi}{e^{i\theta P/2}Ae^{-i\theta P/2}}{\phi}, where PP is a Pauli string (P2=IP^2=\id), ∣ϕ⟩\ket\phi is the state before the gate and AA is the observable pulled back through the later gates. With e−iθP/2=cos⁡θ2 I−isin⁡θ2 Pe^{-i\theta P/2}=\cos\frac\theta2\,\id-i\sin\frac\theta2\,P,

  2. E(θ+s)−E(θ−s)=2sin⁡s (γcos⁡θ−βsin⁡θ)=2sin⁡s  E′(θ)E(\theta+s)-E(\theta-s)=2\sin s\,\big(\gamma\cos\theta-\beta\sin\theta\big)=2\sin s\;E'(\theta)

    A first-degree trigonometric polynomial obeys an exact difference identity:

  3.   ∂E∂θ=E(θ+π2)−E(θ−π2)2  \boxed{\;\frac{\partial E}{\partial\theta}=\frac{E(\theta+\frac\pi2)-E(\theta-\frac\pi2)}{2}\;}

    Take s=π/2s=\pi/2. The result is exact, not a finite-difference approximation, and costs two circuit evaluations per parameter (Mitarai et al., 2018; Schuld et al., 2019):

Why not finite differences, [E(θ+h)−E(θ−h)]/2h[E(\theta+h)-E(\theta-h)]/2h? If each estimate of EE has standard error σ/N\sigma/\sqrt N, the finite-difference estimator has standard error σ/(2N h)\sigma/(\sqrt{2N}\,h), which blows up as h→0h\to0, while a large hh adds bias. The parameter shift has standard error σ/2N\sigma/\sqrt{2N} and no bias at all.

Check your understanding

For ∣ψ(θ)⟩=RY(θ)∣0⟩\ket{\psi(\theta)}=R_Y(\theta)\ket0 and A=ZA=Z, E(θ)=cos⁡θE(\theta)=\cos\theta. What does the parameter-shift rule give at θ=π/3\theta=\pi/3?

  1. −32-\tfrac{\sqrt3}{2}
  2. −12-\tfrac12
  3. 32\tfrac{\sqrt3}{2}
  4. −3-\sqrt3
Show the answer

A. −32-\tfrac{\sqrt3}{2}

12[cos⁡5π6−cos⁡(−π6)]=12[−32−32]=−32\tfrac12\big[\cos\tfrac{5\pi}{6}-\cos\big(-\tfrac\pi6\big)\big]=\tfrac12\big[-\tfrac{\sqrt3}{2}-\tfrac{\sqrt3}{2}\big]=-\tfrac{\sqrt3}{2}, exactly −sin⁡π3-\sin\tfrac\pi3.

OptimizerUsesCost per stepNotes
Gradient descent, Adamparameter-shift gradients2m2m expectation values for mm parametersSimple; step size matters
SPSArandom simultaneous perturbation of all parameters2 expectation values, for any mmNoisy but cheap; popular on hardware
COBYLA, Nelder–Meadfunction values onlya few evaluationsGradient-free; struggle in high dimension
Quantum natural gradientgradient plus the Fubini–Study metricO(m2)O(m^2) extra evaluationsFollows the geometry of states, not of parameters

Choosing an ansatz

The ansatz decides what you can reach (expressibility), how hard the landscape is (trainability), and what the hardware can run (depth).

FamilyConstructionStrengthsWeaknesses
Hardware-efficient (Kandala et al., 2017)Layers of native one-qubit rotations and fixed native entanglersShallow; no compilation overheadIgnores symmetries; deep random-like versions have barren plateaus
Problem-inspired: UCCSDeT−T†e^{T-T^\dagger} with single and double excitations from a Hartree–Fock reference, TrotterizedChemically meaningful; conserves particle numberDeep after compilation; many parameters
Adaptive: ADAPT-VQE (Grimsley et al., 2019)Grow the circuit one operator at a time, picking the largest energy gradient from a poolCompact, problem-tailored circuitsMany extra measurements to rank the pool
QAOAAlternate problem and mixer evolutionsStructured; adiabatic limitNeeds depth to compete with classical heuristics

Try a hardware-efficient layer on two qubits: RY(θ0)⊗RY(θ1)R_Y(\theta_0)\otimes R_Y(\theta_1) followed by a CNOT. The two-spin Heisenberg Hamiltonian H=XX+YY+ZZH=XX+YY+ZZ has the singlet 12(∣01⟩−∣10⟩)\tfrac{1}{\sqrt2}(\ket{01}-\ket{10}) as its ground state with E0=−3E_0=-3; the three triplet states have E=+1E=+1. Tune the two angles to reach it.

QAOA and MaxCut

MaxCut: split the vertices of a graph G=(V,E)G=(V,E) into two sets so as to cut as many edges as possible. Encode a split as a bit string zz and the objective as a diagonal operator:

C=∑(i,j)∈E1−ZiZj2,C∣z⟩=(number of edges cut by z)∣z⟩C=\sum_{(i,j)\in E}\frac{1-Z_iZ_j}{2},\qquad C\ket z=\big(\text{number of edges cut by }z\big)\ket z

QAOA with pp layers prepares

∣γ,β⟩=e−iβpBe−iγpC⋯e−iβ1Be−iγ1C∣+⟩⊗n,B=∑iXi,\ket{\boldsymbol\gamma,\boldsymbol\beta}=e^{-i\beta_pB}e^{-i\gamma_pC}\cdots e^{-i\beta_1B}e^{-i\gamma_1C}\ket{+}^{\otimes n},\qquad B=\sum_iX_i,

and maximizes Fp=⟨γ,β|C|γ,β⟩F_p=\mel{\boldsymbol\gamma,\boldsymbol\beta}{C}{\boldsymbol\gamma,\boldsymbol\beta}. The cost layer is diagonal: up to a global phase, each edge contributes eiγZiZj/2e^{i\gamma Z_iZ_j/2}, compiled as CNOT, RZ(−γ)R_Z(-\gamma), CNOT. The mixer is RX(2β)R_X(2\beta) on every qubit.

Derivationp = 1 on a single edge
  1. eiβXZe−iβX=Zcos⁡2β+Ysin⁡2βe^{i\beta X}Ze^{-i\beta X}=Z\cos2\beta+Y\sin2\beta

    Mixer in the Heisenberg picture: since XZ=−ZXXZ=-ZX, eiβXZ=Ze−iβXe^{i\beta X}Z=Ze^{-i\beta X} and

  2. ⟨Z1Y2⟩γ=⟨Y1Z2⟩γ=isin⁡γ⋅i=−sin⁡γ\expval{Z_1Y_2}_\gamma=\expval{Y_1Z_2}_\gamma=i\sin\gamma\cdot i=-\sin\gamma

    So Z1Z2↦c2Z1Z2+cs (Z1Y2+Y1Z2)+s2Y1Y2Z_1Z_2\mapsto c^2Z_1Z_2+cs\,(Z_1Y_2+Y_1Z_2)+s^2Y_1Y_2 with c=cos⁡2βc=\cos2\beta, s=sin⁡2βs=\sin2\beta. Pull these through the cost layer and evaluate in ∣++⟩\ket{++}, where only products of XX's and identities survive. Z1Z2Z_1Z_2 and Y1Y2Y_1Y_2 commute with the cost and have zero mean in ∣++⟩\ket{++}. Z1Y2Z_1Y_2 anticommutes with Z1Z2Z_1Z_2, so it picks up eiγZ1Z2=cos⁡γ+isin⁡γ Z1Z2e^{i\gamma Z_1Z_2}=\cos\gamma+i\sin\gamma\,Z_1Z_2, and ⟨Z1Y2⋅Z1Z2⟩=⟨iX2⟩=i\expval{Z_1Y_2\cdot Z_1Z_2}=\expval{iX_2}=i:

  3. ⟨Z1Z2⟩=−2cssin⁡γ=−sin⁡4β sin⁡γ,F1=1−⟨Z1Z2⟩2=12+12sin⁡4β sin⁡γ\expval{Z_1Z_2}=-2cs\sin\gamma=-\sin4\beta\,\sin\gamma,\qquad F_1=\frac{1-\expval{Z_1Z_2}}{2}=\frac12+\frac12\sin4\beta\,\sin\gamma

    Collect terms:

  4. The maximum F1=1F_1=1 is reached at γ=π/2\gamma=\pi/2, β=π/8\beta=\pi/8: one layer solves a single edge exactly.

Check your understanding

On a ring of nn vertices with nn even (so the maximum cut contains every edge), each edge has p=1p=1 value 12+14sin⁡4β sin⁡2γ\tfrac12+\tfrac14\sin4\beta\,\sin2\gamma. What approximation ratio does optimized p=1p=1 QAOA achieve?

  1. 12\tfrac12
  2. 23\tfrac23
  3. 34\tfrac34
  4. 11
Show the answer

C. 34\tfrac34

The maximum of sin⁡4β sin⁡2γ\sin4\beta\,\sin2\gamma is 1, so each edge is cut with probability 34\tfrac34; since the optimum cuts every edge, the ratio is 34\tfrac34 (Farhi, Goldstone & Gutmann, 2014). With p=2p=2 it rises to 56\tfrac56.

Limits, and where to go deeper

Key takeaways

  • E(θ)≥E0E(\boldsymbol\theta)\ge E_0 for every state, so VQE energies are upper bounds, up to statistical error and estimator bias.
  • The parameter-shift rule gives exact gradients from two evaluations at ±π/2\pm\pi/2; finite differences amplify shot noise.
  • Ansätze trade expressibility, trainability and depth: hardware-efficient, problem-inspired, adaptive.
  • QAOA alternates a diagonal cost layer with an XX mixer; p=1p=1 solves a single edge exactly and achieves 3/43/4 on even rings.
  • No variational algorithm has a proven practical advantage yet.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A noiseless VQE run on a molecule returns E=−1.137±0.004E=-1.137\pm0.004 hartree (statistical error). What does the variational principle let you conclude about the exact ground energy E0E_0?

  1. E0=−1.137E_0=-1.137 exactly
  2. E0≤−1.137E_0\le-1.137, up to the statistical error
  3. E0≥−1.137E_0\ge-1.137
  4. Nothing, because VQE is a heuristic
Show the answer

B. E0≤−1.137E_0\le-1.137, up to the statistical error

Every trial state's energy is an upper bound on E0E_0, so the true E0E_0 lies at or below the estimate, within its uncertainty. A noisy (mixed) state still obeys Tr⁡(ρH)≥E0\Tr(\rho H)\ge E_0, but biased estimators, e.g. with readout errors or after error mitigation, can fall below it.

Question 2

An ansatz has 50 parameters, all in Pauli rotations. How many distinct expectation values does one full parameter-shift gradient need?

  1. 50
  2. 51
  3. 100
  4. 2500
Show the answer

C. 100

Two shifted evaluations per parameter: 2×50=1002\times50=100, each with its own shots. SPSA needs only 2 regardless of dimension, at the price of a noisy stochastic estimate.

Question 3

In QAOA for MaxCut, which statement about the two kinds of layers is correct?

  1. Both layers are diagonal in the computational basis
  2. The mixer only adds phases; the cost layer moves amplitude between bit strings
  3. Without the mixer, QAOA would still find the maximum cut
  4. The cost layer is diagonal and only adds phases; the mixer moves amplitude between bit strings so that the phases can interfere
Show the answer

D. The cost layer is diagonal and only adds phases; the mixer moves amplitude between bit strings so that the phases can interfere

e−iγCe^{-i\gamma C} multiplies each ∣z⟩\ket z by e−iγC(z)e^{-i\gamma C(z)}, invisible in computational-basis statistics on its own. The mixer converts these phase differences into amplitude differences by interference.

Question 4

Why might a chemist prefer UCCSD to a hardware-efficient ansatz, despite its greater depth?

  1. UCCSD conserves particle number and starts from a physically meaningful reference, so its parameters explore the relevant states
  2. UCCSD circuits are always shallower
  3. Hardware-efficient ansätze cannot create entanglement
  4. UCCSD needs no classical optimizer
Show the answer

A. UCCSD conserves particle number and starts from a physically meaningful reference, so its parameters explore the relevant states

Building in symmetries and a good reference state (Hartree–Fock) restricts the search to physically relevant states, helping both accuracy and trainability. The cost is circuit depth.

Go deeper

Further reading

  • A. Peruzzo et al., "A variational eigenvalue solver on a photonic quantum processor", Nature Communications 5, 4213 (2014).
  • E. Farhi, J. Goldstone & S. Gutmann, "A quantum approximate optimization algorithm", arXiv:1411.4028 (2014).
  • M. Schuld, V. Bergholm, C. Gogolin, J. Izaac & N. Killoran, "Evaluating analytic gradients on quantum hardware", Phys. Rev. A 99, 032331 (2019).
  • M. Cerezo et al., "Variational quantum algorithms", Nature Reviews Physics 3, 625 (2021).