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 on a quantum chip, measure term by term, and minimize classically. For H₂ at its equilibrium bond length in a minimal basis, the problem reduces to two qubits with
with , , , hartree. A one-angle ansatz is enough. Turn 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 . “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 , which phases each bit string by its cost , with a mixer , for rounds. As it becomes a Trotterized adiabatic path (Chapter 125) and finds the optimum. At it can be analysed by hand.
The plate maps the expected cut for MaxCut on a 6-vertex ring over angles 0.80, 0.40. The best at 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 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 landscape on a ring, and the Goemans–Williamson benchmark it has to beat.
· · ·
Three questions to carry with you.
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?
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.