Chapter 24 — Key Takeaways (Variational Algorithms)

Where every practical concern from Parts II and III arrives at once. §24.3's shot budget is the binding constraint.

The hybrid loop

   1. PREPARE   |psi(theta)>                   on the QPU
   2. MEASURE   <psi(theta)| H |psi(theta)>
   3. OPTIMIZE  theta, CLASSICALLY
   4. repeat

The quantum computer evaluates a function; the classical computer minimizes it. Chapter 20 §20.6's structure — with the difference that the loop runs thousands of times, so every cost is multiplied.

$$\langle\psi|H|\psi\rangle \;\geq\; E_0$$

The variational principle: the minimum you find is an upper bound. You can never accidentally report an energy below the truth.

★ VQE works

H₂, STO-3G, 0.735 Å, tapered to two qubits:

$$H = -1.0524\,II + 0.3979\,IZ - 0.3979\,ZI - 0.0113\,ZZ + 0.1809\,XX$$

   exact (diagonalized):  -1.857275030 Ha
   VQE (4 params, Adam):  -1.857275030 Ha      error 8.88e-16
   chemical accuracy:      0.0016 Ha           ACHIEVED by 1e13x

Every random start converged to the same value.

⚛️ Start from HARTREE–FOCK, not $|00\rangle$. Hartree–Fock is the best mean-field solution — classically free, usually within a few percent. VQE's job is the correlation energy, the part mean-field cannot capture. Starting from $|00\rangle$ wastes parameters re-deriving it.

General principle: encode what you already know. Chapter 16 §16.6 measured that randomly- initialized hardware-efficient ansätze hit barren plateaus; a problem-informed start is the defence.

★★ The shot budget

At the optimal parameters, on a noiseless simulator, mean over 25 repetitions:

       shots   mean |error|         std   0.5/sqrt(N)   chem acc?
         100       2.09e-02    1.48e-02      5.00e-02          NO
       1,000       6.52e-03    4.57e-03      1.58e-02          NO
      10,000       1.75e-03    1.04e-03      5.00e-03          NO
     100,000       6.80e-04    5.45e-04      1.58e-03         yes
       exact       8.88e-16           -             -         yes

Ten thousand shots is not enough. The error tracks $0.5/\sqrt N$, and the std is comparable to the mean — a single draw is not informative.

$$N \sim \left(\frac{\sigma}{\epsilon}\right)^2 \quad\Longrightarrow\quad \left(\frac{0.5}{0.0016}\right)^2 \approx 97{,}656 \text{ per evaluation}$$

And a gradient costs $2n+1$ evaluations, every iteration (Ch. 16 §16.4):

   params   iterations   shots/eval        TOTAL SHOTS     QPU time
        4          200       97,657        175,782,600       4.9 hr
       20          200       97,657        800,787,400      22.2 hr
      100          200       97,657      3,925,811,400       4.5 days

Four billion shots for a 100-parameter ansatz — one molecule, one geometry, no noise.

🔬 Papers quote the converged energy and the ITERATION count. The number that matters is TOTAL SHOTS, and it is often absent.

Unfavourable in three directions: precision $1/\epsilon^2$ · parameters $2n+1$ · Hamiltonian $\mathcal{O}(n^4)$ terms. Grouping commuting terms, classical shadows, and gradient-free optimizers help by constant factors. None changes the $1/\epsilon^2$.

🗝️ shots on the device is deprecated in PennyLane 0.45. Use qml.set_shots(qnode, shots=N). The two forms consume randomness differently, which is a good reason to report a mean over repetitions rather than one seeded draw.

QAOA

$$|\psi(\gamma,\beta)\rangle = \prod_{k=1}^{p} e^{-i\beta_k H_M} e^{-i\gamma_k H_C}\;H^{\otimes n}|0\rangle$$

$2p$ parameters, and problem-informed by construction — the cost layer is built from the graph.

     p    <C>          mean cut   approximation ratio   parameters
     1   -3.237109       3.2342                0.8086            2
     2   -3.855836       3.8542                0.9636            4
     3   -3.994008       3.9918                0.9979            6
     4   -3.999328       3.9992                0.9998            8

⚠️ QAOA is a SAMPLER. $\langle C\rangle$ is what the optimizer minimizes; what you want is a specific good cut. Sample the optimized state and keep the best — p=3: mean 3.9918, BEST sampled cut 4, optimum in 99.5% of shots — then verify classically. A Las Vegas procedure, like Ch. 23's Shor: the quantum part proposes, verification disposes.

★★ Against the classical algorithm

Goemans–Williamson (1995), polynomial time, proven guarantee 0.87856 for any graph:

   QAOA p=1:  0.8086     <- BELOW the classical guarantee
   QAOA p=2:  0.9636
   QAOA p=3:  0.9979

In QAOA's favour: one small instance; G–W's 0.8785 is worst-case and it also does better on easy instances.

Against: QAOA has no guarantee at all. No theorem gives ratio $f(p)$ for arbitrary graphs, and known instance families defeat low-depth QAOA.

A proven worst-case bound and a good average-case result are different kinds of claim.

And depth is the binding constraint. Each layer applies the full cost Hamiltonian — one two-qubit interaction per edge — so $\mathcal{O}(p|E|)$ two-qubit gates, plus Ch. 17's up-to-3.18× routing overhead. $p=1$ is where the hardware is, and that is where the classical algorithm wins.

★ Everything arrives at once

And they interact: more parameters → bigger gradient bill and flatter landscape. Deeper ansatz → more error → more mitigation → more shots. Better layout → fewer shots for the same precision.

Mitigation can make things worse at a fixed budget, because it spends the shots precision needs.

🔬 Does it beat classical? Not yet.

Chemistry: every molecule currently in reach is exactly solvable classically (full CI); coupled cluster handles more. Crossover estimated around 50+ well-correlated orbitals.

Optimization: §24.5.

Three barriers, in order of severity:

1. The shot budget — $1/\epsilon^2 \times (2n+1) \times$ iterations. Billions of shots, and no known technique changes the exponent.
2. Barren plateaus — Ch. 16: variance halving per qubit; ~$10^{15}$ shots per gradient at 50 qubits.
3. Hardware noise — 288× gate-quality spread, mitigation overhead, depth limits.

Variational algorithms are the best available way to use current hardware — a real thing to be — and an active research programme rather than a deployed technology. "VQE computed a molecule's ground state" has been true since 2014; "VQE computed one no classical computer could" has not happened.

Hold their claims to the standard Chapters 21–23 applied to Grover, the QFT, and Shor. Shor's is the one that clears it.

Common pitfalls

• Developing on an exact simulator, which hides shot noise entirely.
• Testing at two levels instead of three (exact → noiseless + shots → noisy + shots).
• Quoting iterations instead of total shots.
• Quoting one seeded draw of a random quantity.
• Benchmarking against your current solver rather than the best classical algorithm.
• Comparing a measured ratio with a proven guarantee as if they were the same claim.
• Adding mitigation at a fixed budget when shot noise already dominates.

Project piece added this chapter

vqelab/variational_algorithms.py — shots_for_precision, shot_budget (the arithmetic before you run anything), vqe() returning a VQEResult with error, chemical_accuracy, respects_variational_principle, and total_shots; qaoa_maxcut() returning a QAOAResult with the best sample and beats_goemans_williamson. 16 tests pass, including test_the_budget_is_reported_and_it_is_enormous and test_qaoa_at_depth_one_is_BELOW_the_classical_guarantee.