122
Part Three · B · Algorithms

Variational algorithms: VQE and QAOA

Shor’s and Grover’s algorithms need thousands of error-corrected qubits. The machines of the 2010s had dozens of noisy ones, and coherence lasting only a few hundred gates. The response was a hybrid: let the quantum chip prepare a state from a short circuit with adjustable angles, measure an energy or a cost, and let an ordinary computer adjust the angles to push the number down. These variational algorithms were the main hope for useful near-term quantum computing. The honest question is whether they beat a laptop.

On the plate: the energy of a hydrogen molecule as you turn one knob of a quantum circuit.

The variational quantum eigensolver

The variational principle (Chapter 46) says any trial state has energy at or above the ground state. Alberto Peruzzo and colleagues proposed in 2014 to prepare the trial state ∣ψ(θ)⟩|\psi(\theta)\rangle on a quantum chip, measure ⟨H⟩\langle H\rangle term by term, and minimize classically. For H₂ at its equilibrium bond length in a minimal basis, the problem reduces to two qubits with

H=g0+g1(Z1−Z0)+g2Z0Z1+g3X0X1H = g_0 + g_1(Z_1 - Z_0) + g_2Z_0Z_1 + g_3X_0X_1

with g0=−1.0524g_0 = -1.0524, g1=0.3979g_1 = 0.3979, g2=−0.0113g_2 = -0.0113, g3=0.1809g_3 = 0.1809 hartree. A one-angle ansatz cos⁡θ∣01⟩+sin⁡θ∣10⟩\cos\theta|01\rangle + \sin\theta|10\rangle is enough. Turn θ=\theta = 2.60. The minimum, −1.8573 hartree electronic (−1.1373 with nuclear repulsion), matches the exact answer. The circuit chosen is called the ansatz; choosing one is the art. Chemistry-inspired ansätze such as unitary coupled cluster are accurate but deep; “hardware-efficient” ones are shallow but can be untrainable (Chapter 123). Established

The cost of measuring

Each energy estimate is an average over repeated measurements, and its error falls only as 1/Nshots1/\sqrt{N_\text{shots}}. “Chemical accuracy” is 1.6 millihartree. With 3.00 (log₁₀ shots per estimate), watch the scatter of estimated energies around the true curve. Molecules of real interest have thousands of Hamiltonian terms. Jérôme Gonthier and colleagues estimated in 2022 that measuring the energy of modest molecules to chemical accuracy would take days per single energy evaluation, and an optimization needs many evaluations. Measurement cost, not qubit count, became the roadblock. Established

QAOA

Edward Farhi, Jeffrey Goldstone and Sam Gutmann proposed in 2014 the quantum approximate optimization algorithm. Alternate e−iγCe^{-i\gamma C}, which phases each bit string by its cost CC, with a mixer e−iβ∑Xje^{-i\beta\sum X_j}, for pp rounds. As p→∞p\to\infty it becomes a Trotterized adiabatic path (Chapter 125) and finds the optimum. At p=1p = 1 it can be analysed by hand.

The plate maps the expected cut for MaxCut on a 6-vertex ring over angles γ=\gamma = 0.80, β=\beta = 0.40. The best at p=1p=1 is 4.5 of 6 edges, a ratio of 0.75. The Goemans–Williamson classical algorithm guarantees 0.878 on every graph. QAOA must go to higher pp to compete, and no convincing practical advantage over classical solvers has been shown. Debated

What you now have

The VQE loop, an exact two-qubit H₂ example, the measurement-cost problem, QAOA as a truncated adiabatic algorithm, its p=1p=1 landscape on a ring, and the Goemans–Williamson benchmark it has to beat.

· · ·

Three questions to carry with you.

Why can’t VQE go below the true ground energy?tap
The variational principle: every state’s energy expectation is at or above the ground energy (apart from shot noise).
How does the shot count scale with target accuracy ε?tap
As 1/ε²: halving the error needs four times the shots.
What does QAOA become as p grows?tap
A Trotterized adiabatic evolution, which reaches the optimum in the limit.

And one to work out. A single-shot energy measurement has standard deviation 0.5 hartree. How many shots reach a standard error of 1.6 millihartree?

N ≈

Sources: A. Peruzzo et al., Nat. Commun. 5, 4213 (2014). E. Farhi, J. Goldstone and S. Gutmann, arXiv:1411.4028. A. Kandala et al., Nature 549, 242 (2017). M. Cerezo et al., Nat. Rev. Phys. 3, 625 (2021). J. F. Gonthier et al., Phys. Rev. Research 4, 033154 (2022). M. X. Goemans and D. P. Williamson, J. ACM 42, 1115 (1995). Checked by code: H₂ two-qubit Hamiltonian ground −1.85728 Ha (−1.13731 total); the one-angle ansatz reaches it; QAOA p = 1 on the 6-ring peaks at 4.5.

Next · Chapter 123
Barren plateaus and trainability

The landscape is flat everywhere, and it gets exponentially flatter with each added qubit.

Turn the page