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 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 expectation value on a single edge.
The hybrid loop
A variational quantum algorithm has four ingredients:
- a cost Hamiltonian , a real combination of Pauli strings ;
- an ansatz: a parameterized circuit preparing ;
- an estimator of built from shots;
- a classical optimizer that proposes the next .
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
Expand in an orthonormal eigenbasis with :
The energy is a weighted average of eigenvalues, so it cannot fall below the smallest:
Equality forces for every , so only ground-state components survive. More quantitatively, if the gap to the next distinct level is , the weight of in the ground eigenspace (projector ) obeys
A mixed state is a convex combination of pure states, so follows by averaging.
Apply it to , whose eigenvalues are . The ansatz has Bloch vector , so
Freeze and vary only (the widget's range). What is the lowest energy this restricted ansatz can reach?
Show the answer
-0.8
With , and : the Bloch vector is confined to the half-plane , which excludes the ground state . The minimum over is at the endpoint , where . 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 . 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.
Isolate one parameter: , where is a Pauli string (), is the state before the gate and is the observable pulled back through the later gates. With ,
A first-degree trigonometric polynomial obeys an exact difference identity:
Take . 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, ? If each estimate of has standard error , the finite-difference estimator has standard error , which blows up as , while a large adds bias. The parameter shift has standard error and no bias at all.
For and , . What does the parameter-shift rule give at ?
Show the answer
A.
, exactly .
| Optimizer | Uses | Cost per step | Notes |
|---|---|---|---|
| Gradient descent, Adam | parameter-shift gradients | expectation values for parameters | Simple; step size matters |
| SPSA | random simultaneous perturbation of all parameters | 2 expectation values, for any | Noisy but cheap; popular on hardware |
| COBYLA, Nelder–Mead | function values only | a few evaluations | Gradient-free; struggle in high dimension |
| Quantum natural gradient | gradient plus the Fubini–Study metric | extra evaluations | Follows 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).
| Family | Construction | Strengths | Weaknesses |
|---|---|---|---|
| Hardware-efficient (Kandala et al., 2017) | Layers of native one-qubit rotations and fixed native entanglers | Shallow; no compilation overhead | Ignores symmetries; deep random-like versions have barren plateaus |
| Problem-inspired: UCCSD | with single and double excitations from a Hartree–Fock reference, Trotterized | Chemically meaningful; conserves particle number | Deep 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 pool | Compact, problem-tailored circuits | Many extra measurements to rank the pool |
| QAOA | Alternate problem and mixer evolutions | Structured; adiabatic limit | Needs depth to compete with classical heuristics |
Try a hardware-efficient layer on two qubits: followed by a CNOT. The two-spin Heisenberg Hamiltonian has the singlet as its ground state with ; the three triplet states have . Tune the two angles to reach it.
QAOA and MaxCut
MaxCut: split the vertices of a graph into two sets so as to cut as many edges as possible. Encode a split as a bit string and the objective as a diagonal operator:
QAOA with layers prepares
and maximizes . The cost layer is diagonal: up to a global phase, each edge contributes , compiled as CNOT, , CNOT. The mixer is on every qubit.
Mixer in the Heisenberg picture: since , and
So with , . Pull these through the cost layer and evaluate in , where only products of 's and identities survive. and commute with the cost and have zero mean in . anticommutes with , so it picks up , and :
Collect terms:
The maximum is reached at , : one layer solves a single edge exactly.
On a ring of vertices with even (so the maximum cut contains every edge), each edge has value . What approximation ratio does optimized QAOA achieve?
Show the answer
C.
The maximum of is 1, so each edge is cut with probability ; since the optimum cuts every edge, the ratio is (Farhi, Goldstone & Gutmann, 2014). With it rises to .
Limits, and where to go deeper
Key takeaways
- 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 ; 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 mixer; solves a single edge exactly and achieves 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.
A noiseless VQE run on a molecule returns hartree (statistical error). What does the variational principle let you conclude about the exact ground energy ?
- exactly
- , up to the statistical error
- Nothing, because VQE is a heuristic
Show the answer
B. , up to the statistical error
Every trial state's energy is an upper bound on , so the true lies at or below the estimate, within its uncertainty. A noisy (mixed) state still obeys , but biased estimators, e.g. with readout errors or after error mitigation, can fall below it.
An ansatz has 50 parameters, all in Pauli rotations. How many distinct expectation values does one full parameter-shift gradient need?
- 50
- 51
- 100
- 2500
Show the answer
C. 100
Two shifted evaluations per parameter: , each with its own shots. SPSA needs only 2 regardless of dimension, at the price of a noisy stochastic estimate.
In QAOA for MaxCut, which statement about the two kinds of layers is correct?
- Both layers are diagonal in the computational basis
- The mixer only adds phases; the cost layer moves amplitude between bit strings
- Without the mixer, QAOA would still find the maximum cut
- 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
multiplies each by , invisible in computational-basis statistics on its own. The mixer converts these phase differences into amplitude differences by interference.
Why might a chemist prefer UCCSD to a hardware-efficient ansatz, despite its greater depth?
- UCCSD conserves particle number and starts from a physically meaningful reference, so its parameters explore the relevant states
- UCCSD circuits are always shallower
- Hardware-efficient ansätze cannot create entanglement
- 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
- Barren Plateaus · Why random parameterized circuits are untrainable.
- QAOA in Depth · Alternating operators, adiabatic limits and performance guarantees.
- Measurement Cost & Ansatz Design · Shot budgets, Pauli grouping and hardware-efficient ansätze.
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).