Chapter 24: Variational Algorithms

"It reaches the exact answer in principle, and the shot budget is four billion."

Overview

Chapter 23's Shor needs a machine nobody has. Variational algorithms are designed for the hardware that exists, which is why they dominate near-term quantum computing — and why this chapter is where every practical concern from Parts II and III arrives at once.

They work. VQE on the H₂ molecule, four parameters, exact simulator:

   VQE result:  -1.857275030 Ha
   exact:       -1.857275030 Ha
   error:        8.88e-16 Ha        chemical accuracy ACHIEVED

Machine precision on a real molecular Hamiltonian. The algorithm is not the problem.

The shot budget is. Evaluate that same circuit at its optimal parameters with a finite number of shots:

       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

At the known-correct answer, ten thousand shots is still not enough — and that is before any hardware noise, any layout choice, or any optimization. §24.3 works out what a realistic run costs, and the number is in the billions.

And QAOA has a sharper problem. On a MaxCut instance:

     p    approximation ratio    parameters
     1                 0.8086             2
     2                 0.9636             4
     3                 0.9979             6

At depth 1, QAOA scores 0.809 — below the 0.8785 that Goemans–Williamson guarantees classically, in polynomial time, for any graph. §24.5 takes that comparison seriously.

In this chapter, you will learn to:

• Build the hybrid loop and reach chemical accuracy.
• Compute the shot budget for a target precision.
• Implement QAOA and measure approximation ratio against depth.
• Compare against the classical algorithm you would actually run.
• Assemble the full near-term stack.
• State what stands between this and usefulness.

Learning Paths

How to read this chapter by track. - 🔰 Beginner — §24.1 and §24.2. The hybrid loop is the shape of near-term quantum computing. - 🔬 Researcher — §24.3 and §24.7. The shot budget is the binding constraint and it is under-reported. - 🤖 Quantum ML — all of it; Part VI is this chapter with a different cost function. - 🏗️ Quantum Engineer — §24.6, where Chapters 12, 13, and 16 combine. - 🔐 Security — skim; Chapter 23 was your chapter.

24.1 The Hybrid Loop

Every variational algorithm is the same loop:

   1. PREPARE     a parameterized state  |psi(theta)>  on the QPU
   2. MEASURE     an expectation value   <psi(theta)| H |psi(theta)>
   3. OPTIMIZE    theta, CLASSICALLY
   4. repeat

The quantum computer evaluates a function. The classical computer minimizes it.

This is Chapter 20 §20.6's structure again — the quantum subroutine produces a value, classical computation turns values into answers — with one important difference: the loop runs thousands of times, so every cost in it is multiplied by the iteration count.

The variational principle is what makes it sound. For any state $|\psi\rangle$ and Hamiltonian $H$ with ground-state energy $E_0$:

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

So the minimum you find is an upper bound on the true answer — you can never accidentally report an energy below the truth, and any improvement is real progress. That is a genuinely useful guarantee, and it is why VQE is trusted in a way that many heuristics are not.

24.1.1 Why the Bound Holds

The variational principle is the entire theoretical foundation of this chapter, and the proof is three lines of linear algebra. They are worth doing, because the same three lines show precisely where the guarantee stops.

📐 Math Aside — $\langle\psi|H|\psi\rangle \geq E_0$, in three lines.

$H$ is Hermitian, so it has a complete orthonormal eigenbasis $\{|E_k\rangle\}$ with real eigenvalues ordered $E_0 \leq E_1 \leq \cdots \leq E_{d-1}$. Expand any normalized state in that basis:

$$|\psi\rangle = \sum_k c_k |E_k\rangle, \qquad \sum_k |c_k|^2 = 1$$

The expectation value is then a probability-weighted average of the eigenvalues:

$$\langle\psi|H|\psi\rangle = \sum_{j,k} c_j^{*}c_k \langle E_j|H|E_k\rangle = \sum_k |c_k|^2 E_k$$

using $H|E_k\rangle = E_k|E_k\rangle$ and $\langle E_j|E_k\rangle = \delta_{jk}$. An average of numbers, none of which is smaller than $E_0$, cannot itself be smaller than $E_0$:

$$\sum_k |c_k|^2 E_k \;\geq\; \sum_k |c_k|^2 E_0 \;=\; E_0$$

Equality holds if and only if all the weight sits in the ground space — $|c_k|^2 = 0$ for every $k$ with $E_k > E_0$. Nothing in the argument mentions the ansatz, the optimizer, the hardware, or the parameter count. It holds for a random state, an undertrained one, and a state mangled by decoherence.

Three consequences follow at once.

Lower is always better, with no further argument, which is why the classical optimizer can be a black box. Any minimizer that reduces the objective has made real progress.

A failed run still proves something. If your best energy is $-1.80$ Ha, the true ground state is at or below $-1.80$ Ha. That is a statement about the molecule, obtained without converging.

You cannot cheat downward. An energy below an independently computed reference is not a triumph; it is a bug — a wrong Hamiltonian, a wrong reference, or a sign error. vqelab's respects_variational_principle property exists for exactly this check, and §24.3 identifies the one circumstance in which it fires without a bug being present.

24.1.2 What the Bound Does Not Give You

It bounds the answer from one side and says nothing about the size of the gap.

Chapter 36 §36.5 measures this in the sharpest possible form. Running VQE on LiH in a (2e,2o) active space, the converged energy lands within $2.04 \times 10^{-9}$ Ha of the exact answer for that active space — while the active space itself is off by $0.0201$ Ha from the real molecule. The ratio is 9,870,104×. The variational bound was tight on the quantity that did not matter and had nothing at all to say about the one that did.

The structural reason is worth naming, because it recurs three chapters later. VQE optimizes over a restriction — the set of states a parameterized circuit can actually reach. A restriction bounds from the same side that any feasible solution bounds from, and never from the other side. Chapter 37 §37.7.1 states the identical fact for QAOA with the inequality flipped: QAOA maximizes, so its objective is a lower bound on the optimum, and it has no upper bound to offer either.

Goemans–Williamson does have one, because it optimizes over a relaxation — a superset of the feasible solutions — and a maximum over a superset is an upper bound. §24.5's comparison is that difference of direction, and no amount of hardware improvement changes it.

🔬 Honest Assessment — "the variational principle guarantees it" is true, and does less work than it sounds like it does.

It guarantees you have not reported an impossibly good energy. It does not tell you whether $-1.85$ Ha is close to $-1.857$ or nowhere near it, and the only way to find out is to compute the answer another way. For every molecule in this chapter, computing it another way is precisely what §24.7 observes is already possible classically.

The bound is genuinely useful for ranking two runs of your own code — it makes "did that change help?" a decidable question, which is not nothing. It is not evidence about the molecule.

24.2 VQE on a Real Molecule

The Hamiltonian. H₂ at bond length 0.735 Å, in the STO-3G basis, tapered to two qubits:

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

Diagonalizing it directly — the reference value, per Chapter 7 §7.7:

   eigenvalues: [-1.85727503, -1.24458455, -0.88272215, -0.22491125]
   GROUND STATE = -1.857275030 Ha

matching the literature value of about −1.8572 Ha for H₂ at that geometry.

The ansatz. Four parameters, starting from the Hartree–Fock reference state:

@qml.qnode(dev)
def cost(p):
    qml.PauliX(0)                    # Hartree-Fock reference |10>
    qml.RY(p[0], 0); qml.RY(p[1], 1)
    qml.CNOT([0, 1])
    qml.RY(p[2], 0); qml.RY(p[3], 1)
    return qml.expval(H)

⚛️ The Physics Underneath — why you start from Hartree–Fock, not from $|00\rangle$.

The Hartree–Fock state is the best mean-field approximation: each electron moving in the average field of the others. It is classically computable, it is usually within a few percent of the true energy, and it is where the classical chemistry already gets you.

VQE's job is the remainder — the correlation energy — which is the part mean-field theory cannot capture and which determines chemistry. Starting the ansatz from $|00\rangle$ wastes parameters re-deriving what Hartree–Fock hands you for free.

This is a general principle for ansatz design: encode what you already know. Chapter 16 §16.6 measured that randomly-initialized hardware-efficient ansätze hit barren plateaus; a problem-informed starting point is the main defence, and Hartree–Fock is the cleanest example of one.

The result, best over six random starts, Adam, 400 iterations:

   VQE:    -1.857275030 Ha
   exact:  -1.857275030 Ha
   error:   8.88e-16 Ha

Chemical accuracy is 1.6 mHa — the threshold at which a computed energy is useful for predicting reaction rates. VQE beats it by thirteen orders of magnitude on an exact simulator.

The algorithm works. Everything difficult about it is in the next section.

24.2.1 Five Terms, and Where the Other Ten Went

The Hamiltonian above has five Pauli terms on two qubits. Chapter 36 §36.2 builds the same molecule and gets a different object:

   H2, Chapter 36 §36.2        4 qubits      15 terms
   H2, this chapter            2 qubits       5 terms

Same molecule, same basis set, same bond length. The difference is symmetry tapering, and it is worth knowing about because it is the one preprocessing step that reduces qubit count rather than trading it for something else.

H₂ in STO-3G has four spin orbitals, so the naive Jordan–Wigner encoding uses four qubits. But the electronic Hamiltonian commutes with several symmetry operators — particle number, and the number of spin-up and spin-down electrons separately. A state in the physical sector has fixed eigenvalues under all of them, so two of the four qubits are carrying no information the answer depends on: their values are determined by the others. Tapering identifies those qubits algebraically and substitutes the known eigenvalue, collapsing $4 \to 2$ qubits and $15 \to 5$ terms.

This is free accuracy, not an approximation. The tapered ground-state energy is exactly the untapered one — the sectors removed contained no ground-state amplitude to begin with — which is why the $-1.857275030$ Ha above is the literature value for H₂ and not an artefact of shrinking the problem. Chapter 36's callout on the same subject notes tapering removes two to four qubits from a typical molecular Hamiltonian — a constant, and a good one, but a constant.

Contrast that with an active space, which is the other way to shrink a molecular Hamiltonian. Chapter 36 §36.4 takes LiH from 12 qubits down to a (2e,2o) space and pays $0.0201$ Ha for it — 12.6× chemical accuracy, before any circuit runs. Tapering costs nothing; truncation costs the answer. When someone reports a molecule "on $n$ qubits", the question is which of these two happened.

24.2.2 Ansatz Design: Two Families, One Trade

The four-line ansatz in §24.2 belongs to a family, and choosing the family is the most consequential design decision in VQE. There are two, and they fail in opposite directions.

Hardware-efficient ansätze are built from whatever gates the device executes natively, arranged in repeating layers — Chapter 16's StronglyEntanglingLayers is the canonical example. They ignore the problem entirely.

Chemically-motivated ansätze are built from the physics. UCCSD — unitary coupled cluster with singles and doubles — enumerates the electron excitations out of the Hartree–Fock reference and gives each one a parameter. Chapter 36 §36.5's LiH run uses three parameters, one per allowed excitation, and reaches $2.04 \times 10^{-9}$ Ha.

   family                what it is built from     parameter count     expressibility
   hardware-efficient    the device's gate set     grows with layers   generic
   chemically-motivated  the excitation structure  set by the physics  targeted

The trade runs in both directions and neither family wins outright.

Hardware-efficient wins on circuit depth. Its two-qubit gates are already the ones the device performs, so Chapter 17's routing overhead — up to 3.18× — mostly does not apply, and Chapter 10's transpiler has little to undo.

Chemically-motivated wins on everything else. Its parameter count is set by the problem rather than by a layer budget, so the $2n+1$ gradient bill of §24.3 stays small. Its landscape is not generic, which is the entire defence against barren plateaus. And a physically meaningless region of parameter space is simply not reachable, which removes a large class of local minima.

The cost of the chemically-motivated route is that it requires knowing the physics — the excitation operators, the reference state, the symmetries. That knowledge exists for molecules and does not exist for most problems anyone would like to solve.

★ This is the sharpest form of the chapter's recurring point. The defence against the scaling barriers is problem-specific structure, and problem-specific structure is exactly what the "general near-term quantum algorithm" framing promises you will not need. The ansätze that scale are the ones that already know the answer's shape, and the ones that do not know it are the ones Chapter 16 measured hitting a barren plateau.

⚙️ Under the Transpiler — the H₂ ansatz is one two-qubit gate, and stays one.

The four-parameter ansatz compiled to two different superconducting basis sets, at optimization_level=3:

text basis {rz, sx, x, cz} sx 10 rz 9 cz 1 depth 11 basis {rz, sx, x, ecr} sx 12 rz 14 ecr 1 depth 16

The single CNOT survives as a single two-qubit gate in both, because a CNOT is one CZ or one ECR plus single-qubit dressing. That dressing is the whole difference between the two rows: 19 single-qubit gates against 26, and depth 11 against 16.

The parameters do not survive as four. rz counts of 9 and 14 against four RY rotations — the transpiler decomposes each $R_Y(\theta)$ into $R_Z$–$\sqrt{X}$–$R_Z$ form and then merges adjacent $R_Z$s. This matters for §24.3's arithmetic in exactly one way: the parameter-shift rule counts ansatz parameters, not gates, so the gradient bill is still $2(4)+1 = 9$ evaluations regardless of what the transpiler produced.

And the depth is 11. Chapter 12's median two-qubit error of 0.0078 on a single two-qubit gate is a survival probability of 0.992 — which is why this circuit is not where the difficulty is, and why §24.3 is.

🔀 In Another Framework — the same VQE in Qiskit 2.5.1, without a VQE class.

This chapter is written in PennyLane because the gradient is the primary output. Qiskit ships the pieces and no driver:

```python from qiskit.primitives import StatevectorEstimator from qiskit.quantum_info import SparsePauliOp from scipy.optimize import minimize

H = SparsePauliOp(["II", "IZ", "ZI", "ZZ", "XX"], coeffs=[...]) est = StatevectorEstimator()

def cost(x): return float(est.run([(ansatz, H, x)]).result()[0].data.evs)

best = minimize(cost, x0, method="COBYLA", options={"maxiter": 2000}) ```

Run from six random starts on the identical Hamiltonian and ansatz:

text Qiskit 2.5.1 + StatevectorEstimator + COBYLA: -1.857275030 Ha error 3.44e-12 PennyLane 0.45.1 + Adam (§24.2): -1.857275030 Ha error 8.88e-16

Both reach the answer. The four-orders-of-magnitude gap between the errors is the optimizer, not the framework — COBYLA is gradient-free and stops on a tolerance, Adam ran 400 gradient steps. Both are far inside chemical accuracy and the distinction is irrelevant to anything except a table of decimal places.

What Qiskit does not ship is the loop. There is no VQE class in Qiskit core — see §24.7's version note — so the optimizer, the callback, the convergence check and the shot accounting are yours. PennyLane's advantage here is not the circuit; it is that qml.grad exists and the parameter-shift bookkeeping of §24.3.3 is already done.

🧪 Run It — the cheapest experiment in this chapter, and it takes ninety seconds.

Set every parameter to zero and evaluate the cost. The ansatz reduces to the bare PauliX(0), so you are measuring the Hartree–Fock energy — the classical mean-field answer, for free.

python hf_energy = float(cost(pnp.zeros(4))) print(hf_energy, exact, hf_energy - exact)

The difference is the correlation energy: the entire quantity VQE exists to compute. Now run Exercise 24.5 and ask what fraction of it the converged run recovered.

Then do the same thing to your own ansatz, whatever it is, and check that the zero-parameter point is somewhere sensible. An ansatz whose zero point is worse than a classical method you already own is an ansatz that has to spend parameters climbing back to the starting line — which is §24.2's Hartree–Fock argument, stated as a test you can run.

24.3 The Shot Budget

Take the optimal parameters — the exact answer, already found — and simply evaluate the energy with a finite shot budget:

       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 still not enough, and you need about 100,000 per evaluation. No optimization is happening, no noise is present, and the answer is still not good enough.

Averaged over 25 repetitions, because a single draw of a random quantity is not informative — note the standard deviation is comparable to the mean. The measured error tracks the predicted $0.5/\sqrt N$ throughout.

Why: an expectation value estimated from $N$ shots has standard error $\sigma/\sqrt N$, so reaching precision $\epsilon$ needs

$$N \sim \left(\frac{\sigma}{\epsilon}\right)^2$$

   sigma     shots per energy evaluation for 1.6 mHa
     0.1                                      3,907
     0.5                                     97,657
     1.0                                    390,625
     2.0                                  1,562,500

Which matches the measurement: the 100,000-shot row is the first to clear chemical accuracy, and $(0.5/0.0016)^2 = 97{,}656.25$, which shots_for_precision rounds up — you cannot buy a quarter of a shot, and rounding down would leave you just short of the precision you asked for.

🗝️ Version Note — shots on the device is deprecated in PennyLane.

text PennyLaneDeprecationWarning: Setting shots on device is deprecated. Please use the `set_shots` transform on the respective QNode instead.

The current form applies shots per call, leaving the QNode exact:

python dev = qml.device("default.qubit", wires=2, seed=1234) # no shots= noisy = qml.set_shots(cost, shots=10_000) # per-call

And the two forms consume randomness differently, so the same seed gives different draws. That is a good reason not to quote a single seeded draw at all — which is why the table above reports a mean over 25 repetitions rather than one number that happens to be reproducible.

Verified against PennyLane 0.45.1.

24.3.1 Where σ = 0.5 Comes From, and Why It Is Twice Too Large

$\sigma$ is doing all the work in $N \sim (\sigma/\epsilon)^2$, and it was chosen as a round number. It can be computed exactly for this Hamiltonian, and doing so is worth two sections because it explains the measured table, changes the shot count by a factor of four, and changes the conclusion by nothing at all.

Start with what actually gets measured. You cannot measure $H$ directly — there is no detector for a sum of Pauli strings. You measure the strings, and strings that commute and share a measurement basis can be read off the same circuit execution. The H₂ Hamiltonian splits into two such groups:

   group Z    II, IZ, ZI, ZZ    all diagonal in the computational basis
   group X    XX                one basis change on both qubits

   5 terms  ->  2 measurement settings

Each group is one circuit, executed with $N$ shots. The energy estimate is the sum of the two group estimates, and because the two circuits are independent, the variances add:

$$\mathrm{Var}[\hat{E}] \;=\; \frac{\mathrm{Var}(A) + \mathrm{Var}(B)}{N}, \qquad \sigma_{\text{eff}} = \sqrt{\mathrm{Var}(A)+\mathrm{Var}(B)}$$

where $A$ is the $Z$-group observable and $B = 0.1809\,XX$.

📐 Math Aside — at the ground state, the two groups have equal variance, and one term sets the whole shot budget.

Let $H = A + B$ and let $|\psi\rangle$ be an eigenstate of $H$ with $H|\psi\rangle = E_0|\psi\rangle$. Write $A = H - B$ and expand:

$$\langle A^2\rangle = \langle (H-B)^2\rangle = \langle H^2\rangle - \langle HB\rangle > - \langle BH\rangle + \langle B^2\rangle = E_0^2 - 2E_0\langle B\rangle + \langle B^2\rangle$$

using $H|\psi\rangle = E_0|\psi\rangle$ on the right and $\langle\psi|H = E_0\langle\psi|$ on the left. And $\langle A\rangle = E_0 - \langle B\rangle$, so $\langle A\rangle^2 = E_0^2 - 2E_0\langle B\rangle + \langle B\rangle^2$. Subtracting:

$$\mathrm{Var}(A) \;=\; \langle B^2\rangle - \langle B\rangle^2 \;=\; \mathrm{Var}(B)$$

At an eigenstate, splitting $H$ into any two pieces gives the two pieces identical variance and perfectly anticorrelated fluctuations — $\mathrm{Cov}(A,B) = -\mathrm{Var}(B)$, which is exactly what makes $\mathrm{Var}(H) = 0$ as it must be for an eigenstate.

Numerically, for the H₂ ground state:

text <XX> -0.221680 Var(A) = Var(B) 0.031127381 sigma_eff sqrt(2 x 0.031127381) = 0.249509

★ The entire shot budget of this calculation is set by the single $XX$ term. The $Z$ group carries $\langle A\rangle = -1.8172$ Ha of the $-1.8573$ total — 97.8% of the energy — and contributes no independent noise at all, because its variance is forced equal to the $XX$ group's by the eigenstate condition. The expensive term is the small one, and that is not an accident of H₂: it is the off-diagonal term, the one that requires a basis change, and the one encoding the correlation energy VQE exists to compute.

Now check the prediction against the measured table. The reported quantity is a mean absolute error, and for a zero-mean Gaussian the mean absolute deviation is $\sigma\sqrt{2/\pi} = 0.7979\sigma$. Inverting that on each row recovers $\sigma$:

       shots   mean |error|   implied sigma    std/mean
         100       2.09e-02          0.2619       0.708
       1,000       6.52e-03          0.2584       0.701
      10,000       1.75e-03          0.2193       0.594
     100,000       6.80e-04          0.2695       0.801

   mean of the four                  0.2523
   derived above                     0.2495       agreement 1.1%

The derivation and the measurement agree to about one percent, on four rows spanning three orders of magnitude in shot count, and the scatter is what 25 repetitions buys. The std/mean column is a second independent check: a half-normal distribution has $\text{std}/\text{mean} = \sqrt{\pi/2 - 1} = 0.7555$, and the four measured values average 0.70. The error is exactly shot noise, behaving exactly as $\sigma/\sqrt N$ predicts, with a $\sigma$ that can be computed before running anything.

Twenty-five repetitions is a thin sample to settle this on, so it was re-run at 400 — which also settles a second question the derivation depends on. If PennyLane spread $N$ shots across the two measurement groups rather than giving $N$ to each, the standard error would be larger by $\sqrt2$, and the two predictions are far enough apart to distinguish:

   400 independent evaluations at the optimal parameters, noiseless

        N    measured sd    per-group pred.   ratio      split pred.   ratio
    1,000     7.8959e-03        7.8902e-03   1.0007       1.1158e-02   0.708
   10,000     2.4371e-03        2.4951e-03   0.9768       3.5286e-03   0.691

   implied sigma:  0.2497 and 0.2437      derived: 0.2495

★ The derived $\sigma$ is confirmed to a tenth of a percent at 1,000 shots, and the $\sqrt2$ alternative is excluded by 30 standard errors. Each commuting group receives the full shot count, which matters for §24.3.3's accounting and for nothing else.

And one more column from the same run. At the optimal parameters the true expectation value is $E_0$, so the estimator is centred on it — meaning about half of all finite-shot evaluations should land below the exact ground-state energy:

   fraction of the 400 draws below the exact value:   0.505 at N=1,000
                                                      0.492 at N=10,000

Half. §24.3.3's 🐛 Debug This is that observation turned into a diagnosis.

📊 What the Numbers Say — the book's $\sigma = 0.5$ is conservative by a factor of two, which is a factor of four in shots, and it does not matter.

$$\frac{0.5}{0.2495} = 2.004 \qquad\Longrightarrow\qquad \left(\frac{0.5}{0.2495}\right)^2 = 4.016$$

Redo the bill below with the derived $\sigma$ instead of the round one:

text sigma=0.5 (as printed) sigma=0.2495 (derived) shots/eval 97,657 24,317 4 params 175,782,600 43,770,600 100 params 3,925,811,400 977,543,400 100 params, QPU time 4.5 days 1.13 days

The honest number for a hundred-parameter ansatz is 978 million shots and a day of continuous QPU time, not four billion and four and a half days. That is a real correction and it is worth making.

It also changes nothing. The argument of §24.7 is that the shot budget is the binding constraint, and a billion shots binds exactly as hard as four billion. Chapter 36 §36.7 prices the chemistry crossover at $1.91\times10^{20}$ shots — 195 billion times the corrected figure. A factor of four is invisible against a deficit of eleven orders of magnitude.

Which is the useful lesson about conservative estimates: check them, because you should, and then check whether the check moved the conclusion. Here it did not, and reporting that is more informative than either number alone.

24.3.2 Grouping Commuting Terms: Exactly 1.5×, and Why That Is the Ceiling

The assessment closing this section calls grouping commuting terms a "constant factor." That is a measurable claim on this Hamiltonian, so measure it.

The comparison must be at equal total budget, or it is not a comparison. Grouping reduces the number of circuits, so at fixed shots-per-circuit it reduces total shots; the question is what happens when you hold the total fixed and spread it differently.

   scheme        settings   variance at total budget M       sd
   grouped              2      0.124510 / M           0.352859/sqrt(M)
   term-by-term         4      0.186764 / M           0.432162/sqrt(M)

   shots to reach the same precision:  1.5000x more, term-by-term

Exactly 1.500 on this Hamiltonian, to ten decimal places. Grouping is worth a 1.5× reduction in shots — and notice that this is less than the 2× reduction in measurement settings.

The gap between 2× and 1.5× is the part that gets forgotten. Grouping does not reduce variance in proportion to the settings it removes, because the terms inside a group are correlated. $IZ$ and $ZI$ have correlation $-1$ at this ground state; measuring them on the same circuit means their fluctuations are read from the same 25 shots rather than from independent ones, and the group's variance is not the sum of its members'. You buy fewer circuits, not proportionally fewer shots.

⚠️ Common Pitfall — quoting the reduction in measurement settings as if it were the reduction in shots.

"We grouped 1,086 terms into 40 commuting families, a 27× saving" is the sentence, and the saving in shots is smaller than 27 by an amount nobody computed. On H₂ the settings ratio is 2 and the shot ratio is 1.5. The direction of the discrepancy is always the same — correlations within a group can only make the group noisier than its independent-terms bound suggests, never quieter, so the settings count is always the optimistic figure.

The honest version costs one line: estimate the variance of each group directly and compare totals. §24.3.1's arithmetic is the whole method.

Now put the constant next to the exponent. This is the chapter's structural point and the reason §24.3's assessment refuses to treat grouping as a solution:

   grouping commuting terms          x1.5 measured here; Ch.36 estimates 10-100x at scale
   classical shadows                 ~sqrt(n_terms), Ch.35 measured 1.5-1.8x at equal budget
   gradient-free optimizers          removes the 2n+1, adds iterations
   ---------------------------------------------------------------------------
   the 1/epsilon^2                   unchanged by every one of them

Every technique on that list buys a constant. The barrier is an exponent. Chapter 36 §36.7 does the arithmetic at the crossover and reaches the same verdict from the other side: all the corrections together are worth perhaps four orders of magnitude against a deficit of eight.

This is the book's "every remedy is denominated in the currency of the disease" in its cleanest form. The disease is $1/\epsilon^2$ scaling multiplied by an $\mathcal{O}(n^4)$ term count. The remedies are denominated in factors of 1.5, 10, and 100. You cannot pay down an exponent with constants, and listing enough of them in a related-work section does not change that.

And everything above is still the price of a single number.

And that is one evaluation. Chapter 16 §16.4 measured that a gradient costs $2n+1$ evaluations, charged on every iteration:

$$\text{total shots} = (2n+1) \times \text{iterations} \times N_{\text{shots}}$$

   parameters   iterations    shots/eval          total shots
            4          200        97,657          175,782,600
           20          200        97,657          800,787,400
          100          200        97,657        3,925,811,400

Nearly four billion shots for a hundred-parameter ansatz. At a generous 10,000 shots per second that is four and a half days of continuous QPU time — for one molecule, at one geometry, with no noise.

24.3.3 Why a Gradient Costs 2n + 1

The $2n+1$ in the bill above is not a convention or an implementation detail. It is forced by how a derivative can be taken on hardware, and Chapter 16 §16.3 derived the mechanism.

On a simulator you would use finite differences. On hardware you cannot: each evaluation costs thousands of shots and carries statistical noise of order $\sigma/\sqrt N$, so a finite difference divides a small noisy number by a small number. Chapter 16 measured finite differences having a sweet spot in step size and getting worse on both sides of it — truncation error above, floating-point cancellation below — and shot noise moves that sweet spot somewhere much worse.

The parameter-shift rule avoids the problem entirely. For a gate $e^{-i\theta P/2}$ with $P$ a Pauli ($P^2 = I$), the expectation value is exactly sinusoidal in $\theta$:

$$f(\theta) = A\cos\theta + B\sin\theta \qquad\Longrightarrow\qquad \frac{\partial f}{\partial \theta} = \frac{f(\theta + \tfrac{\pi}{2}) - f(\theta - \tfrac{\pi}{2})}{2}$$

Two evaluations, an exact derivative, and no step size to tune. $\pi/2$ is a large shift, which is precisely why the rule survives on noisy hardware where finite differences do not.

Then count. Two shifted evaluations per parameter, plus one unshifted evaluation for the energy itself:

$$\text{evaluations per optimizer step} \;=\; 2n + 1$$

Chapter 16 §16.4 measured exactly this — 3, 5, 9, 17, 33 executions for 1, 2, 4, 8, 16 parameters — and for the H₂ ansatz it is $2(4) + 1 = 9$.

And then multiply by the measurement settings, which is the factor people forget. Each of those 9 evaluations is itself two circuits, one per commuting group from §24.3.1:

   parameters                              4
   evaluations per gradient step   2(4)+1 = 9
   measurement settings                    2
   ------------------------------------------
   CIRCUIT EXECUTIONS per step            18

Eighteen circuit submissions to take one step on a two-qubit molecule, and 6 random starts multiplies that by six again.

And the measurement settings are a factor the printed bill does not contain. §24.3.1 measured that each commuting group receives the full shot count, so shots=97,657 consumes 195,314 physical shots on this Hamiltonian. The table above counts the parameter, not the shots. That correction runs the opposite way from §24.3.1's, and the two partly cancel:

   as printed                                    3,925,811,400
   x 1/4.02   sigma is 0.2495, not 0.5             977,543,400
   x 2        two measurement settings           1,955,247,600      54.3 QPU hours

   net effect of both corrections                 x 0.498

Two billion physical shots and two and a quarter days, against four billion and four and a half. A factor of two, in a quantity that needed to move by a factor of $10^{9}$ — which is the whole reason §24.7 lists the shot budget first and does not list it as solvable.

🐛 Debug This — the optimizer reports an energy below the exact ground state.

Symptom. A finite-shot VQE run converges to $-1.8721$ Ha against an exact reference of $-1.857275$ Ha. respects_variational_principle fails. §24.1's derivation says this is impossible, so something must be broken: a wrong reference, a mislabelled Pauli string, a sign error in a coefficient.

Usually none of those. Check the reference first — that is genuinely the most common cause, and Chapter 7 §7.7's habit of computing it independently is what makes the check possible. But if the reference is right, the second cause is not a bug at all.

The variational principle bounds $\langle\psi|H|\psi\rangle$. It does not bound your estimate of $\langle\psi|H|\psi\rangle$. At the optimal parameters the true expectation equals $E_0$, so a finite-shot estimator centred on $E_0$ lands below it about half the time — measured over 400 independent evaluations in §24.3.1 as 0.505 at 1,000 shots and 0.492 at 10,000. The principle is a statement about a number you never observe.

And the optimizer makes it systematic rather than random. Any procedure that reports the minimum over many noisy evaluations is biased downward. The expected minimum of $k$ independent standard normal draws is about $-3.0$ at $k = 400$ and $-1.27$ at $k = 6$ — measured over 200,000 trials each, and close to the textbook $-\sqrt{2\ln k}$ asymptote. Applied to §24.3's measured per-evaluation standard deviations, this predicts a downward selection bias of:

text shots std k=6 starts k=400 logged iterations 100 1.48e-02 1.9e-02 4.4e-02 1,000 4.57e-03 5.8e-03 1.4e-02 10,000 1.04e-03 1.3e-03 3.1e-03 100,000 5.45e-04 6.9e-04 1.6e-03

At 1,000 shots, reporting the lowest of 400 logged iterations is worth about 14 mHa of pure selection — nine times chemical accuracy, in the flattering direction.

The fix is one line and it is not "more shots". Optimize however you like, then re-evaluate the final parameters in a fresh, independent, high-shot run and report that. Selection bias attaches to the number you selected on; it does not attach to a number you measured afterwards. This is §24.3's table done as a discipline rather than as an experiment — and it is why the table was generated by evaluating at already-known optimal parameters rather than by reading off a run.

💰 Cost and Queue — what the four-billion-shot plan costs in dollars, under three pricing models.

Chapter 39 §39.5 measured that the same job prices differently by 3,718× depending on how a provider counts. Apply its three models to the hundred-parameter bill above — 3,925,811,400 shots across 40,200 evaluations, which at two measurement settings each is 80,400 task submissions:

text per-shot @ $0.00035 + $0.30/task -> $ 1,398,000 per-shot @ $0.01 + $0.30/task -> $ 39,282,000 per-minute @ $96/min on gate time -> $ 11,000

The same calculation is eleven thousand dollars or thirty-nine million, and the physics is identical in both. For scale, Chapter 39 priced Chapter 36's LiH VQE at \$7,432 or \$185,542 for 18,456,984 shots; this run is 213× larger.

And the gate time is under two hours. At Chapter 39's measured circuit duration of 1.69 μs, four billion shots of this tiny ansatz is 1.84 hours of actual quantum evolution. §24.3's "four and a half days" is 10,000 shots/second including overhead — and Chapter 39 §39.3 measured real utilization at a five-minute queue at $2.31\times10^{-5}$, which is 43,340× wall clock. Pick whichever of those three numbers you like; the one on the invoice is none of them.

🔬 Honest Assessment — the shot budget is the binding constraint, and it is under-reported.

Papers reporting VQE results frequently quote the converged energy and the number of iterations. The number that matters is total shots, and it is often absent.

The scaling is unfavourable in three directions at once. Precision costs $1/\epsilon^2$. Parameters cost $2n+1$ per gradient. And the number of Hamiltonian terms grows as $\mathcal{O}(n^4)$ for molecular systems, each needing its own measurement basis.

Techniques exist and they help by constant factors. Grouping commuting terms reduces the number of distinct measurement settings; classical shadows improve the scaling for some observables; gradient-free optimizers avoid the $2n+1$ factor at the cost of more iterations. None of them changes the $1/\epsilon^2$.

This is not a reason to dismiss VQE. It is the reason that "VQE reached chemical accuracy on a simulator" and "VQE is useful" are separated by several orders of magnitude of QPU time — and quoting the first while implying the second is the most common overstatement in this area.

24.4 QAOA

The same loop, aimed at combinatorial optimization.

The problem: MaxCut. Partition a graph's vertices into two sets, maximizing the number of edges crossing between them.

   graph: [(0,1), (1,2), (2,3), (3,0), (0,2)]     4 nodes, 5 edges
   MAX CUT = 4                                     (brute force over 16 assignments)
   random assignment averages 2.5                  ratio 0.625

The ansatz alternates a cost layer (encoding the problem) with a mixer layer (driving transitions), $p$ times:

$$|\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$$

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

Measured, best over eight random starts:

     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

Depth buys quality, and each layer costs two parameters and a full pass of the cost and mixer Hamiltonians.

⚠️ Common Pitfall — QAOA is a sampler. The expectation value is not the deliverable.

$\langle C\rangle$ is what the optimizer minimizes, but what you want is a good cut — a specific assignment. So you sample the optimized state and keep the best result:

text p=3: mean cut 3.9918, BEST sampled cut 4 the optimum appears in 99.5% of shots

And you verify it classically — evaluating a cut is trivial. This makes QAOA a Las Vegas procedure in the same sense as Chapter 23's Shor: the quantum part proposes, and classical verification disposes. A mean of 3.995 would be a disappointing answer and is an excellent sampler.

24.4.1 What the Four-Node Instance Actually Contains

Before reading anything into the approximation ratios, enumerate the instance. Sixteen assignments, brute-forced:

   cut value      0      2      3      4
   assignments    2      4      8      2

   mean 2.5000     sd 1.1180     MAX CUT = 4
   optimal assignments: 0101 and 1010     (2 of 16 = 12.5%)

The optimum is provable by hand, and it is not 5. The graph is a 4-cycle plus the chord $(0,2)$, which creates two triangles — $0$–$1$–$2$ and $0$–$2$–$3$ — sharing that chord. A triangle cannot be fully cut: three vertices in two colours must repeat a colour, so at least one of its edges has both endpoints on the same side. Both triangles contain the chord, so leaving the chord uncut satisfies both, and $\text{MAX CUT} = |E| - 1 = 4$. The two optimal assignments are the bipartition $\{0,2\}$ versus $\{1,3\}$ and its complement.

Now price the quantum advantage on this instance. A uniform random assignment hits the optimum with probability $2/16 = 0.125$. The number of samples needed to see the optimum at least once with 99% confidence is $k \geq \ln(0.01)/\ln(1-P)$:

   uniform random guessing     P = 0.1250   ->    35 samples
   QAOA p=3 (measured 0.995)   P = 0.9950   ->     1 sample

The entire variational apparatus — 300 optimizer steps, eight random starts, 4,000 sampling shots — saves thirty-four coin flips. That sentence is not a criticism of the implementation, which is correct, or of the measured 0.9979, which is real. It is a statement about what a four-node instance can support as evidence.

★ Compare Chapter 37, which runs the same algorithm on a 12-node 3-regular graph. There the uniform superposition places $2/4096 = 0.000488$ of its probability on the optimum, needing 9,430 shots for the same 99% confidence, against 10 shots for QAOA at $p=5$ — a concentration factor of 795× that is genuinely large and genuinely an achievement of the algorithm. You cannot see that effect on four nodes, because on four nodes there is not enough state space for anything to concentrate in.

⚠️ Common Pitfall — a small instance is a debugging instance, not an evidence instance.

The 4-node graph is the right size for exactly one purpose: checking that your implementation is correct against a brute-force answer you can enumerate. It cannot distinguish a good algorithm from a bad one, because 16 assignments is a space that random guessing solves.

And the property that makes the check possible is the property that makes the result meaningless. Chapter 37 §37.7.2 states this in its general form: the experiment that validates QAOA is only runnable at sizes where nobody needs QAOA. At $n = 50$ there are $1.1\times10^{15}$ assignments and there is no MAX CUT column to compare against. The regime where you can verify and the regime where you would need to are disjoint, and no hardware improvement moves the boundary.

24.4.2 The Cost Layer, Counted

$p$ is not free, and the price is exact rather than asymptotic.

Each edge contributes one $ZZ$ rotation per layer — that is what "the cost layer is built from the graph" means literally. And each $ZZ$ rotation compiles to two two-qubit gates:

$$e^{-i\gamma Z_u Z_v} \;=\; \text{CNOT}_{uv}\;\cdot\;R_Z(2\gamma)_v\;\cdot\;\text{CNOT}_{uv}$$

so a $p$-layer QAOA circuit on a graph with $|E|$ edges has exactly $2p|E|$ two-qubit gates before any routing. Transpiled to a {rz, sx, x, cx} basis at optimization_level=3:

   circuit                    cx    rz    sx    depth      2p|E|
   p=1, 5 edges               10    25    12       23         10
   p=2, 5 edges               20    42    20       43         20
   p=3, 5 edges               30    59    28       63         30

The cx column is $2p|E|$ exactly, and the transpiler removes none of it — cost-layer rotations commute with each other but not with the mixer, so there is nothing to cancel across a layer boundary. Chapter 37 independently reports 90 cx for a $p=3$ circuit on a 15-edge instance, which is $2(3)(15)$, confirming the formula on a second graph.

Then apply Chapter 12's measured error rates. Median two-qubit gate error on a real chip is 0.0078, and the probability that a circuit executes without a two-qubit fault is $(1-0.0078)^{2p|E|}$:

     |E|    p    2q gates    survival @ 0.0078    survival @ best 1.79e-03
       5    1          10               0.9247                     0.9822
       5    3          30               0.7906                     0.9477
     100    1         200               0.2089                     0.6988
     100    3         600               0.0091                     0.3413

On the toy instance the circuit survives. On a hundred-edge graph at $p=3$ it does not — under one percent at the median error rate, and 34% even on Chapter 39's best measured cz link. And the table assumes the graph is already laid out perfectly: Chapter 17 measured up to 3.18× routing overhead when the interaction graph is not local, which multiplies the exponent, not the base.

📉 Noise Report — a global depolarizing rate of 25% erases QAOA's margin at $p=2$, and the circuit that produces it is worth 14.5%.

Every measurement in §24.4 is noiseless. The cheapest model of what changes is a global depolarizing channel: with probability $\lambda$ the prepared state is replaced by the maximally mixed state.

The maximally mixed state samples bitstrings uniformly — and §24.4.1 already enumerated what a uniform bitstring cuts on this graph: a mean of 2.5, ratio 0.625. So the measured ratio degrades linearly between two numbers this chapter already owns:

$$r(\lambda) \;=\; (1-\lambda)\,r_0 \;+\; \lambda\,(0.625)$$

Set that equal to the Goemans–Williamson guarantee and solve for the rate that consumes the entire margin:

text p r0 margin over 0.87856 lambda* 1 0.8086 -0.0700 (none) already below 2 0.9636 +0.0850 0.2512 3 0.9979 +0.1193 0.3200 4 0.9998 +0.1212 0.3235

Now ask what the circuit is actually worth. Treating each two-qubit fault as a depolarizing event, $\lambda = 1 - (1-0.0078)^{2p|E|}$ at Chapter 12's median error:

text |E| p 2q gates implied lambda verdict at p=2's 0.2512 threshold 5 2 20 0.1450 survives 15 2 60 0.3749 margin gone 100 1 200 0.7911 far gone

★ On this chapter's five-edge toy the noise budget holds, and on any graph worth solving it does not — a 15-edge instance at $p=2$ is already past the threshold, and 15 edges is Chapter 37's instance, which is itself a toy.

The linear model is optimistic in one direction and pessimistic in another, and both should be said. Optimistic: real noise is not global depolarizing, and coherent errors can move a variational result further than an incoherent model predicts. Pessimistic: the variational loop can partly absorb noise by re-optimizing the angles on the noisy device, which is the strongest genuine argument for variational methods on near-term hardware — and doing that costs the shot budget of §24.3 all over again, on hardware rather than on a simulator.

24.5 QAOA Against the Classical Algorithm

Now the comparison Chapter 21 §21.7 and Chapter 22 §22.3 have trained you to insist on.

Goemans–Williamson is a classical polynomial-time algorithm for MaxCut, based on semidefinite programming, with a proven approximation guarantee of 0.8785 for any graph.

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

   Goemans-Williamson guarantee:  0.8785  (worst case, any graph, polynomial time)

At depth 1, QAOA is worse than a classical algorithm that has been available since 1995.

Two things must be said about that comparison, and both matter.

In QAOA's favour: the measured ratios above are for one small instance, where QAOA at $p \geq 2$ comfortably exceeds 0.8785 and at $p = 3$ essentially solves the problem. Goemans–Williamson's 0.8785 is a worst-case guarantee; on easy instances it also does better.

Against: QAOA has no guarantee at all. There is no theorem saying QAOA at depth $p$ achieves ratio $f(p)$ for arbitrary graphs, and there are known instance families where low-depth QAOA performs poorly. A proven worst-case bound and a good average-case result are different kinds of claim, and the classical algorithm has the stronger kind.

🔬 Honest Assessment — what QAOA would need to be interesting.

It would need to beat the best classical algorithm on instances people care about, at a depth that current hardware can execute. All three conditions are load-bearing.

Depth is the binding one. Each QAOA layer applies the full cost Hamiltonian — one two-qubit interaction per edge — so a $p$-layer circuit on a graph with $|E|$ edges has $\mathcal{O}(p|E|)$ two-qubit gates. Chapter 12 measured a 288× spread in two-qubit gate error on real hardware and Chapter 17 measured up to 3.18× routing overhead for non-local interaction graphs. Deep QAOA on a realistically-connected graph is not currently executable at useful size.

And $p=1$ is where the hardware is, which is exactly where the classical algorithm wins.

The honest current status: QAOA is a well-motivated heuristic with no performance guarantee, whose quality improves with a depth that hardware cannot yet supply, competing against a classical algorithm with a proven bound. That is not a dismissal — heuristics without guarantees win in practice all the time, and QAOA's structure is genuinely interesting. It is a description of what would have to change.

24.5.1 One Instance, Best of Eight Starts — and What Chapter 37 Measures Instead

§24.4's table is a good measurement of a specific thing, and the specific thing should be stated precisely: one 4-node instance, the best of eight random initializations, expectation value sampled over 4,000 shots. Chapter 37 runs the same algorithm under a different protocol on a different graph and gets different numbers:

     p     this chapter (4 nodes, best of 8)     Ch.37 (12 nodes, MEAN of 8)      std
     1                                0.8086                          0.751    0.000
     2                                0.9636                          0.812    0.008
     3                                0.9979                          0.852    0.016
     4                                0.9998                          0.873    0.021

The $p=3$ ratios differ by 0.146. Two things cause that, and it is worth separating them, because one is a protocol artifact and the other is not.

The protocol is worth about 0.025. "Best of eight" is the maximum of eight draws, and the expected maximum of eight standard normal draws sits $1.42$ standard deviations above the mean — measured over 200,000 trials. Chapter 37 §37.4.1 publishes its eight per-seed ratios at $p=3$, so the effect can be checked directly rather than assumed:

   Ch.37 p=3 per-seed: 0.858 0.858 0.854 0.818 0.836 0.877 0.857 0.857
   mean 0.8519    max 0.8770    std 0.0176
   max - mean = 0.0251 = 1.43 standard deviations        (theory predicts 1.42)

The remaining 0.121 is the instance. A 4-node graph with 5 edges and a hand-provable optimum is easier than a 12-node 3-regular graph, and QAOA at $p=3$ nearly saturating one says nothing about the other.

★ And the conclusion §24.5 draws is the one that survives both changes. At $p=1$ this chapter measures 0.8086 and Chapter 37 measures 0.751 — both below Goemans–Williamson's 0.87856, on different graphs, under different protocols, with different sample sizes. The finding that gets weaker under scrutiny is the flattering one at $p \geq 2$; the finding that gets stronger is the one at $p=1$.

📊 What the Numbers Say — "best of eight starts" and "mean of eight starts" are different statistics, and only one of them predicts your next run.

Both are honest reports of the same eight numbers. The maximum tells you what QAOA can do on a good day and the mean tells you what it will do on Tuesday, and a user of an optimizer gets Tuesday.

The book has made the corresponding error seven times and documented each one — Chapter 27's false-failure rate (1.0% from 2 runs in 200, actually 0.150% at 2,000), Chapter 28's optimization levels (identical from two circuits, different in 14 of 40), Chapter 37's $p=4$ "regression" that vanished at eight seeds. A result from one or two samples is a draw from a distribution.

§24.4's table is not one of those errors — it reports what it measured, on the instance it measured it on. It becomes one the moment it is quoted as "QAOA achieves 0.998."

🔬 Honest Assessment — and even 0.87856 is generous to QAOA, because it is not what Goemans–Williamson actually scores.

0.87856 is a worst-case guarantee — a floor, proven for every graph. Chapter 37 §37.6.1 measures what the algorithm achieves by running 1,000 random hyperplane roundings on each of ten instances:

text GW proven worst-case bound 0.87856 GW measured mean over 1,000 roundings per graph 0.9600 GW single rounding hits the exact optimum 0.68 of the time QAOA p=3 measured mean, same instances 0.8908

The bar QAOA is usually held to is the floor of the classical algorithm, not its performance. Against the performance, Chapter 37's ten-instance head-to-head is QAOA 0 wins, GW 6, four ties; compared distribution against distribution — the comparison QAOA's defenders should prefer — it is 0–10, with GW's worst per-instance mean (0.9371) above QAOA's best (0.9220).

§24.5's comparison against 0.87856 is therefore the charitable version, and QAOA loses it at $p=1$ anyway.

24.6 Everything Arrives at Once

Variational algorithms are where the whole book converges, and it is worth seeing the stack assembled.

Every one of these applies simultaneously to a single VQE run, and they interact:

More parameters → better ansatz expressibility → larger gradient bill (§24.3) and flatter landscape (Ch. 16 §16.6).

Deeper ansatz → better expressibility → more two-qubit gates → more error → more mitigation → more shots.

Better layout → less error → fewer shots for the same precision.

🧱 Project Checkpoint — vqelab/variational_algorithms.py: the loop, with its bill.

This is the module the whole project has been building toward, and it composes the earlier ones.

vqe(hamiltonian, ansatz, optimizer, shots) runs the loop and returns a VQEResult carrying the energy, the reference value from exact diagonalization, the error, whether chemical accuracy was reached, and — the point — the total shot count actually consumed.

shot_budget(n_params, iterations, target_precision, sigma) implements §24.3's arithmetic before you run anything, so a four-billion-shot plan is visible in advance rather than discovered.

qaoa_maxcut(graph, p) returns a QAOAResult with the mean cut, the best sampled cut, the approximation ratio, and the Goemans–Williamson comparison — because §24.5's comparison should not be optional.

stack_report(circuit, backend) pulls together the layout score (Ch. 12), the connectivity overhead (Ch. 17), the gradient cost (Ch. 16), and the mitigation recommendation (Ch. 13) into one object, so §24.6's interacting concerns are visible together.

Its tests assert: VQE reaches chemical accuracy on H₂ against an independently diagonalized reference; the shot budget is reported and exceeds 10⁸ for a realistic run; QAOA's approximation ratio increases with $p$; and QAOA at $p=1$ is flagged as below the Goemans–Williamson guarantee.

24.7 Does Any of This Beat a Classical Computer?

Not yet, and it is worth being precise about why rather than hedging.

For quantum chemistry (VQE): the molecules currently within reach — H₂, LiH, BeH₂, small chains — are all classically solvable exactly. Full configuration interaction handles them, and for somewhat larger systems coupled-cluster methods are extremely good. The crossover is estimated at somewhere around 50 or more well-correlated orbitals, which needs both more qubits and far better error rates than exist.

For optimization (QAOA): §24.5's comparison. No performance guarantee, and quality requires depth the hardware cannot supply.

The three barriers, in order of severity:

1. The shot budget (§24.3). $1/\epsilon^2$, times $2n+1$ per gradient, times the iteration count. Billions of shots for a modest problem, and no technique changes the $1/\epsilon^2$.

2. Barren plateaus (Ch. 16 §16.6). Gradient variance halving per qubit; at 50 qubits, roughly $10^{15}$ shots to resolve a gradient. Problem-informed ansätze are the main defence and they require knowing a lot about your problem.

3. Hardware noise (Ch. 12, 13). A 288× spread in gate quality, mitigation that costs more shots, and depth limits that constrain ansatz expressibility.

24.7.1 Which Barrier Binds First

The three are listed in order of severity, and the ordering is not a matter of taste. It can be computed, because all three are denominated in the same unit: shots.

Barrier 1 costs $(\sigma/\epsilon)^2$ shots per evaluation — 24,317 for chemical accuracy on H₂ (§24.3.1), and that number does not depend on the qubit count. It is set by the precision you want.

Barrier 2 costs $1/\mathrm{Var}[\partial f]$ shots to resolve one gradient component against shot noise, and that number depends on nothing else. Chapter 16 fitted $\mathrm{Var} \sim e^{-0.676n}$ across 2 to 10 qubits:

   qubits    Var[gradient]      shots to resolve one component
        2       1.043e-01                                  10
        6       6.982e-03                                 143
       10       4.674e-04                               2,140
       14       3.128e-05                              31,960
       20       5.418e-07                           1,846,000
       50       8.440e-16                            1.19e+15

Barrier 3 costs whatever mitigation costs, which Chapter 13 measured: readout mitigation removes 64% of readout error and needs calibration circuits; ZNE needs 3–5× the circuits. Both are multipliers on the other two.

Set barriers 1 and 2 equal and solve for the crossover:

$$\frac{1}{\mathrm{Var}[\partial f]} \;=\; \left(\frac{\sigma}{\epsilon}\right)^2 \quad\Longrightarrow\quad 0.1043\,e^{-0.676(n-2)} = \frac{1}{24{,}319} \quad\Longrightarrow\quad n \approx 13.6$$

★ Below about fourteen qubits, precision sets the shot count. Above it, the barren plateau does. At the round $\sigma=0.5$ the crossover moves to $n \approx 15.7$ — the answer is insensitive to which $\sigma$ you use, because one side of the equation is exponential and the other is not.

Which settles the ordering, and it is not the intuitive one. The barren plateau is the barrier everyone names, and at the scale anyone is currently running it is not the binding one. §24.3's measurement was taken at two qubits, at the exactly-correct parameters, with no noise, no optimizer, and no plateau — and ten thousand shots was still not enough. The shot budget binds first because it binds immediately, at a problem size where nothing else has started.

And the ordering inverts around fourteen qubits, which is roughly where the interesting molecules start. Chapter 36's LiH is 12 qubits and BeH₂ and H₂O are 14. The regime where variational chemistry becomes worth doing is precisely the regime where the second barrier overtakes the first, and both are priced in the same currency, so they add.

24.7.2 Where This Would Flip

The chapter's conclusion is negative, so the useful question is what would have to be true for it to reverse. Four things, ranked by how close each is.

1. A measurement strategy that beats $1/\epsilon^2$. This is the one that would change everything, and one is known: phase estimation gets $\epsilon$ precision from $\mathcal{O}(1/\epsilon)$ circuit depth rather than $\mathcal{O}(1/\epsilon^2)$ samples. Chapter 22 §22.4 measured it returning exact answers for dyadic phases. Trading a squared sample count for a linear depth is the single largest available improvement in this chapter's arithmetic — one more digit of precision costs 10× instead of 100×.

And it needs the machine Chapter 23 said nobody has. Phase estimation on a molecular Hamiltonian requires controlled time evolution to a depth that is meaningless without error correction, and Chapter 15 priced one $T$ gate at 450 → 2,882 physical qubits. The known route around the shot budget runs through fault tolerance, which is why §24.7's answer is "not yet" rather than "not ever" — and why Chapter 25 is the next chapter.

2. QAOA beating Goemans–Williamson at executable depth. The gap at $p=1$ is small in absolute terms:

   ratio needed to clear 0.87856       0.87856
   measured at p=1                     0.8086
   shortfall                           0.0700   (8.65% relative)
   in cut terms: 3.5142 edges needed, 3.2342 measured, deficit 0.28 of 5 edges

Less than a third of one edge. But §24.5.1 measured that the honest bar is not 0.87856 — it is GW's achieved 0.9600, and closing 0.15 at a depth of one is a different proposition from closing 0.07. And QAOA would still return an uncertified answer, which Chapter 37 §37.7 shows is a difference in what the two algorithms produce rather than in how they score. That gap does not close with better hardware at all.

3. Ansätze that are both problem-informed and general. §24.2.2's trade is the crux: the ansätze that avoid barren plateaus are the ones built from problem structure, and problem structure is what a general algorithm does not have. ADAPT-VQE and its relatives grow the ansatz from measured gradients rather than fixing it in advance, which is a genuine attack on the right target. This is the most active of the four and the hardest to price, because a method that adds operators adaptively also adds evaluations adaptively, and papers reporting parameter counts rarely report the selection cost.

4. Gate fidelities good enough to drop mitigation. Chapter 29 measured that hardware-aware compilation at optimization level 1 (0.9116) beats naive level 3 (0.7720), and that a calibration-picked qubit chain scores 0.9764 against a hand-picked 0.6790. Those are large wins available today and they are constant factors — they buy depth, not scaling, which moves barrier 3 and leaves barriers 1 and 2 exactly where they were.

🔬 Honest Assessment — three of the four are constants, and the book has a name for that.

Better fidelities, better layouts, better mitigation and better ansätze are all real and all denominated in factors of 1.5, 3, and 100. Chapter 36 §36.7 adds up every correction it can justify and reaches four orders of magnitude against a deficit of eight.

Only item 1 changes an exponent, and item 1 is fault tolerance. Every remedy is denominated in the currency of the disease — and the disease here is $1/\epsilon^2$, which is not a hardware property, a compiler property, or an ansatz property. It is a property of estimating a mean from samples, and the only known way out is to stop estimating a mean from samples.

🗝️ Version Note — there is no VQE class in Qiskit, and there has not been since 1.0.

python from qiskit.algorithms import VQE # ModuleNotFoundError since Qiskit 1.0 from qiskit.algorithms.minimum_eigensolvers import VQE # same

Verified against Qiskit 2.5.1: qiskit.algorithms does not exist. The algorithm classes moved to a separate qiskit-algorithms package; molecular Hamiltonian construction moved to qiskit-nature; the optimization problem modelling moved to qiskit-optimization. None of the three is installed in this book's environment, which is why §24.2's Qiskit example builds the loop from StatevectorEstimator and SciPy directly.

What Qiskit core still ships is everything below the driver: SparsePauliOp for the Hamiltonian, EfficientSU2 and TwoLocal for hardware-efficient ansätze, QAOAAnsatz for §24.4's circuit, and the primitives to evaluate them. If a tutorial imports VQE from Qiskit directly, it predates 1.0 — which for VQE tutorials is most of them, because the class existed for the years when this material was first being written up.

The same removal took qiskit.pulse in Qiskit 2.0, along with add_calibration, .calibrations, backend.defaults and instruction_schedule_map — Chapter 31 documents what that costs.

🔬 Honest Assessment — what variational algorithms are actually for, today.

They are the best available way to use current hardware, and that is a real thing to be. Every result in Parts II and III came from running something on a device that exists, and variational circuits are the shape of program that fits.

They are also an active research programme rather than a deployed technology. The distinction matters because the two get conflated constantly: "VQE computed the ground state of a molecule" is true and has been true since 2014, and "VQE computed a ground state no classical computer could" has not happened.

What would change the picture: substantially better gate fidelities (reducing both mitigation overhead and depth limits), a principled solution to barren plateaus rather than a collection of heuristics, and shot-efficient measurement strategies that improve on $1/\epsilon^2$ scaling. All three are actively worked on and none is solved.

The honest recommendation: learn variational algorithms because they are how you use the hardware, and hold the advantage claims to the same standard Chapters 21–23 held Grover, the QFT, and Shor. Shor's is the one that clears it.

24.8 Summary

Every variational algorithm is one loop: prepare a parameterized state, measure an expectation value, optimize classically, repeat. The variational principle guarantees $\langle\psi|H|\psi\rangle \geq E_0$, so the result is always an upper bound — you cannot accidentally report an energy below the truth.

★ VQE works. On H₂ (STO-3G, 0.735 Å, two qubits), a four-parameter ansatz from the Hartree–Fock reference reaches −1.857275030 Ha against an exact −1.857275030 Ha — error 8.88 × 10⁻¹⁶, beating chemical accuracy (1.6 mHa) by thirteen orders of magnitude. Start from Hartree–Fock: it is classically free, and VQE's job is the correlation energy that mean-field theory cannot capture.

★★ The shot budget is the binding constraint. At the optimal parameters, with no noise:

     100 shots -> error 3.04e-02      1,000 shots -> error 8.00e-03
  10,000 shots -> error 1.43e-03      (chemical accuracy = 1.6e-03)

Precision costs $N \sim (\sigma/\epsilon)^2$, a gradient costs $2n+1$ evaluations (Ch. 16), and the loop runs hundreds of times:

   100 parameters x 200 iterations x 97,657 shots = 3,925,811,400 shots

Four billion shots — about four and a half days of continuous QPU time at 10,000 shots/second, for one molecule at one geometry with no noise. Papers report converged energies and iteration counts; the number that matters is total shots, and it is often absent.

QAOA alternates cost and mixer layers, $2p$ parameters for depth $p$, and is problem-informed by construction. Measured on a MaxCut instance: $p=1 \to 0.8086$, $p=2 \to 0.9636$, $p=3 \to 0.9979$. It is a sampler — keep the best sample and verify classically; at $p=3$ the optimum appeared in 99.5% of shots.

★★ And at $p=1$, QAOA scores 0.8086 — below Goemans–Williamson's 0.8785, a classical polynomial-time algorithm with a proven worst-case guarantee for any graph. QAOA has no guarantee at all, its quality needs depth the hardware cannot execute, and $p=1$ is where the hardware is.

Everything from Parts II and III arrives at once — layout choice (100×), mitigation ordering (−79%), barren plateaus, the $2n+1$ gradient bill, connectivity overhead, ancilla hygiene — and they interact: more parameters means a larger gradient bill and a flatter landscape; deeper ansätze mean more error and more mitigation and more shots.

Does it beat classical? Not yet. Molecules within reach are exactly solvable classically; the crossover is estimated around 50+ well-correlated orbitals. Three barriers in order of severity: the shot budget ($1/\epsilon^2$, unchanged by any known technique), barren plateaus, and hardware noise.

Variational algorithms are the best available way to use current hardware, and an active research programme rather than a deployed technology. Hold their advantage claims to the standard Chapters 21–23 applied to Grover, the QFT, and Shor. Shor's is the one that clears it.

Next: Chapter 25 — Part IV closes with the thing that changes all of this. Chapter 15 priced fault tolerance and Chapter 23 needed it; this chapter builds it: the three-qubit codes, the surface code, syndrome extraction, and a measurement of the threshold below which error correction helps and above which it makes things worse.