NISQ and Variational Circuits

In 2018 John Preskill gave the present moment a name: NISQ, for Noisy Intermediate-Scale Quantum. The three words are a specification. Noisy: gates and qubits carry the errors of Chapter 4, and there is no error correction to sweep them away. Intermediate-scale: tens to a few hundred qubits — too many to simulate trivially on a laptop, too few and too faulty to run the fault-tolerant algorithms of Part II at useful sizes. The deep, coherent circuits that Shor and phase estimation demand would accumulate error long before they finished. So the NISQ question is sharp: what can you compute with a circuit only a few layers deep, whose every run is a little bit wrong?

The era's answer is to stop asking the quantum computer to do the whole job. Split the work. Let the quantum device do the one thing it is uniquely good at — hold a state in a $2^n$-dimensional space and give you a measurement statistic from it — and hand everything else to a classical computer sitting beside it. The quantum circuit is kept shallow (so noise stays tolerable) and parametrized by a handful of gate angles $\theta$. The classical machine reads out a number, decides how to change $\theta$, and asks for another run. This back-and-forth is the variational pattern, and it is the organizing idea of the whole chapter.

Everything rests on a fact about Hermitian operators so simple it is almost a definition. Let $H$ be a Hamiltonian with eigenstates $|E_k⟩$ and real eigenvalues ordered $E_0\le E_1\le \cdots$, so that $E_0$ is the ground energy. Any normalized state expands in that eigenbasis,

Its expected energy is then a probability-weighted average of the eigenvalues,

where the inequality just replaces every $E_k$ by the smallest one, $E_0$. That is the whole variational principle: no state has an expected energy below the ground energy, and equality holds if and only if all the weight sits on the ground level (a ground state). Turn it into an algorithm and it reads: take any family of states $|\psi (\theta )⟩$ you can prepare, and minimize $E(\theta )=⟨\psi (\theta )|H|\psi (\theta )⟩$ over $\theta$. Whatever minimum you reach is a rigorous upper bound on $E_0$, and if your family is rich enough to contain the ground state, the bound is tight. You cannot cheat downward — the floor $E_0$ is inviolable — so the only failure mode is stopping short, above the floor.

This is exactly the guarantee a NISQ machine needs. It does not require the circuit to be deep, or exact, or noiseless to be safe: any state it manages to prepare gives an honest bound. The quantum device's job is just to evaluate $E(\theta )$ for whatever $\theta$ the classical optimizer proposes.

The Variational Quantum Eigensolver (VQE) is the variational principle wired into a loop. Three pieces. First, an ansatz: a parametrized circuit $U(\theta )$ that prepares the trial state $|\psi (\theta )⟩=U(\theta )|0\cdots 0⟩$. A hardware-efficient ansatz uses only the gates the device runs well — layers of single-qubit rotations interleaved with entangling CNOTs:

Second, the energy evaluation: to get $E(\theta )$ the device prepares $|\psi (\theta )⟩$ and measures $H$. A Hamiltonian is a sum of Pauli terms; you estimate each term's expectation by sampling in the right basis and add them up. Third, the classical optimizer: it takes $E(\theta )$ and returns a better $\theta$, closing the loop. The three fit together as one hybrid machine:

Because measurement is sampling, the energy comes with shot noise: a finite number of shots gives a noisy estimate of each expectation, with a statistical error that shrinks only as $1/\sqrt{N_{\text{shots}}}$. The estimate is unbiased — it converges to the true $E(\theta )$ — but every evaluation the optimizer sees is jittered, which is one of the practical frictions of the method (the lab quantifies it as a clean 5$\sigma$ check).

Before the many-qubit machinery, feel the principle on a single qubit. Take $H=Z+0.6X+0.4Y$ and a two-angle ansatz $|\psi (\theta ,\varphi )⟩=R_Z(\varphi )R_Y(\theta )|0⟩$. The energy landscape $E(\theta ,\varphi )$ is drawn below as a slice at your chosen $\varphi$; the red floor is the exact $E_0=-\Vert (1,0.6,0.4)\Vert$. Steer the angles and watch the curve ride above that floor everywhere, kissing it only when the trial state lines up with the true ground state:

That is VQE in one qubit. The lab does the same thing on a 3-qubit chain: a 12-angle ansatz, gradient descent, and a measured energy that settles onto the exact ground line from above and never below.

The same variational skeleton solves a different kind of problem. The Quantum Approximate Optimization Algorithm (QAOA) targets combinatorial optimization — problems where you seek the best assignment of bits. The showcase is Max-Cut: given a graph, split its nodes into two sets so as to cut as many edges as possible. Encode the objective as a diagonal cost Hamiltonian whose eigenvalue on a bitstring is that string's cut value,

since $(1-Z_i{Z}_j)/2$ is $1$ when spins $i$ and $j$ disagree (the edge is cut) and $0$ when they agree. Maximizing $⟨H_C⟩$ maximizes the expected number of cut edges. QAOA builds its trial state by starting from the uniform superposition $|+{⟩}^{\otimes n}$ and alternating two unitaries for $p$ rounds — the cost unitary and a mixer built from $H_M={\sum }_i{X}_i$:

(Mind the ordering: the $\ell =1$ factor stands rightmost, next to the initial state, so it acts first; each later layer multiplies on the left — exactly the order in which the lab applies them.) The cost unitary $e^{-i\gamma H_C}$ is diagonal — it stamps a phase on each basis state proportional to its cut value — while the mixer $e^{-i\beta H_M}$ is a layer of one-qubit $X$-rotations that spreads amplitude between bitstrings. A classical optimizer tunes the $2p$ angles $(\gamma ,\beta )$ to maximize $⟨H_C⟩$. The quality of the answer is the approximation ratio

where $C_{\max }$ is the true optimum (found by brute force in the lab, for a small graph). Two facts make $p$ the dial of interest. First, $p$ layers contain $p-1$ as a special case — set the last layer's ${\gamma }_p={\beta }_p=0$ and the extra round is the identity — so the optimal ratio can only rise with depth. Second, as $p\to \infty$ QAOA can approach the exact optimum. Note what the first fact is about: the optima. Whether a finite optimizer actually finds them at every depth is a separate, empirical question — so the lab optimizes each $p$ from independent random starts and measures the climb, rather than seeding each depth from the last (which would make the climb true by construction). Measured that way, the ratio still rises with $p$ and clears the random-guessing baseline at the very first layer. The catch, of course, is that larger $p$ means a deeper circuit — precisely what NISQ noise makes costly to run.

Now the sober accounting the book has promised at every turn. Variational algorithms are the flagship of the NISQ era, and it is tempting to read their flexibility as a guarantee of advantage. It is not. Here is where things actually stand.

No proven speedup. Unlike Shor's factoring or Hamiltonian simulation, neither VQE nor QAOA has a proof that it beats the best classical algorithm on a problem of practical interest. For many instances, classical methods — from clever heuristics to tensor-network and other simulation techniques — keep pace or win. Whether these methods ever deliver a decisive advantage is a genuinely open question, not a settled win.

Barren plateaus. As the number of qubits and the ansatz depth grow, the energy landscape can flatten exponentially: gradients vanish across almost all of parameter space, and the optimizer has no slope to follow. This barren-plateau phenomenon (which Chapter 16 studies in earnest) can make a generic hardware-efficient ansatz untrainable at scale — the very expressiveness that lets it reach any state is what buries the gradient.

Noise caps the depth. Deeper circuits express more, and QAOA's ratio improves with $p$ — but on real NISQ hardware each extra layer injects more error, until the signal drowns. Depth is exactly the resource the era is short of. Shot noise compounds it: resolving a small energy difference to steer the optimizer can demand enormous numbers of measurements.

None of this makes the approach worthless. It makes it honest: variational circuits are the best we know how to do on the hardware we have, before fault tolerance arrives to lift the depth limit. They may yet find a niche of real advantage; they may turn out to be a bridge we walk across and leave behind. The book's stance is to run them, measure them, and refuse to overclaim — which is exactly what the lab does next.

The lab builds both algorithms on a real state-vector simulator with a hand-written classical optimizer — no quantum SDK. For VQE the trial state is a hardware-efficient ansatz: because $R_Y$ and CNOT are real and $|0\cdots 0⟩$ is real, the whole search stays in the reals, which is all a real symmetric Hamiltonian's ground state needs:

1/// Prepare |ψ(θ)⟩ = U(θ)|0…0⟩ for the hardware-efficient ansatz:
2/// an initial R_Y layer, then L blocks of [CNOT ladder, R_Y layer].
3/// Parameter count = n·(L+1).
4fn ansatz_state(theta: &[f64], n: usize, l: usize) -> Vec<f64> {
5    let dim = 1usize << n;
6    let mut s = vec![0.0; dim];
7    s[0] = 1.0;
8    let mut idx = 0;
9    for q in 0..n {
10        apply_ry(&mut s, n, q, theta[idx]);
11        idx += 1;
12    }
13    for _ in 0..l {
14        for q in 0..n - 1 {
15            apply_cnot(&mut s, n, q, q + 1);
16        }
17        for q in 0..n {
18            apply_ry(&mut s, n, q, theta[idx]);
19            idx += 1;
20        }
21    }
22    s
23}

The optimizer is gradient descent, and the gradient is not a finite difference but the parameter-shift rule (derived in Chapter 16): for a rotation gate generated by a Pauli, the exact derivative is a difference of two energies evaluated at shifted angles $\theta \pm \frac{\pi }{2}$ — themselves ordinary circuit runs. Every one of those shifted evaluations is a legitimate sampled $\theta$, and so must obey the variational bound:

1/// The parameter-shift rule for an R_Y(θ)=exp(-iθY/2) gate (generator Y/2 with
2/// eigenvalues ±½): ∂⟨H⟩/∂θ_k = ½[E(θ+½π e_k) - E(θ-½π e_k)], EXACT — no finite
3/// step, no truncation. Every energy evaluated here is a genuine sampled θ and
4/// so is fed through `eval`, which tracks the variational-bound minimum.
5fn param_shift_grad(theta: &[f64], eval: &mut dyn FnMut(&[f64]) -> f64) -> Vec<f64> {
6    let shift = std::f64::consts::FRAC_PI_2;
7    let mut g = vec![0.0; theta.len()];
8    let mut t = theta.to_vec();
9    for k in 0..theta.len() {
10        let orig = t[k];
11        t[k] = orig + shift;
12        let ep = eval(&t);
13        t[k] = orig - shift;
14        let em = eval(&t);
15        t[k] = orig;
16        g[k] = 0.5 * (ep - em);
17    }
18    g
19}

QAOA reuses the same simulator with a diagonal cost unitary and an $X$-rotation mixer, optimized this time by a hand-written Nelder–Mead simplex over the $2p$ angles:

1/// Apply the cost unitary e^{-iγ H_C}, H_C = Σ (1 - Z_iZ_j)/2. Up to a global
2/// phase this multiplies every basis state by e^{-iγ} once per CUT edge.
3fn apply_cost(state: &mut [C], n: usize, edges: &[(usize, usize)], gamma: f64) {
4    for (k, amp) in state.iter_mut().enumerate() {
5        let cut = cut_value(k, n, edges) as f64;
6        *amp *= C::from_polar(1.0, -gamma * cut);
7    }
8}
9
10/// Apply the mixer e^{-iβ H_M}, H_M = Σ X_i, as e^{-iβ X} on each qubit:
11/// e^{-iβX} = cos β · I - i sin β · X.
12fn apply_mixer(state: &mut [C], n: usize, beta: f64) {
13    let co = C::new(beta.cos(), 0.0);
14    let si = C::new(0.0, -beta.sin()); // -i sin β
15    // …
16}

A bench of referees runs and writes its verdicts to JSON, which the panel below reads live — nothing is hardcoded, down to the number of checks. Most of the bench grades the machinery route against route, so that no check compares a computation with itself: the gate loops against a dense Kronecker-built unitary, the $R_Y$ closed form against the exponential of its generator, the parameter-shift gradient against Richardson-extrapolated finite differences, the QAOA circuit against dense matrix exponentials of (13.4) and (13.5), and $E_0$ itself computed twice — once by a library eigensolver, once by a hand-written matrix-free power iteration. Only because of that last pair does the variational-floor referee mean anything: $E(\theta )$ comes from the dense Hamiltonian, $E_0$ from the matrix-free route, and over every angle the optimizer touched plus 40,000 random ones, the deepest excursion below $E_0$ is a round-off-sized number of either sign — a few parts in $10^{15}$, which is what an inequality honestly looks like in floating point, never a meaningful breach (the panel shows your run's value):

1// --- Referee 6: the variational floor, across two independent routes -----
2// E(θ) comes from the dense Hamiltonian; E₀ comes from the matrix-free power
3// iteration. As a theorem the difference cannot be negative for a normalized
4// state, so what this referee actually gates is that BOTH routes are right
5// and the ansatz stays normalized — and the value it reports is honest
6// double-precision noise, of order 1e-15 and of either sign, not an exact 0.
7assert!(min_bound_gap.is_finite());
8referees.push(Referee {
9    name: "Variational floor  min(E_dense(θ) − E₀_free) ≥ −round-off".into(),
10    value: min_bound_gap,
11    tol: -8e-15,
12    pass: min_bound_gap >= -8e-15,
13});

The rest follow: VQE reaches the exact ground energy to machine precision — the panel shows your run's $E_0$ and gap; the shot-noise estimate at 50,000 shots per measurement setting (2 settings, so 100,000 circuit runs in all) lands well within 5$\sigma$ of the exact energy, where $\sigma$ is the exact per-setting standard deviation of the two summed observables, computed from the state itself — and a second referee confirms that this $\sigma$ is neither inflated nor optimistic by checking $\mathrm{mean}(z^2)=1$ over hundreds of random angles; QAOA's Max-Cut approximation ratio, each depth optimized from 120 independent random starts, climbs across $p=1,2,3$ to 0.965, comfortably above the random baseline of 0.60 (both numbers are your run's, read from the JSON); and the last two referees certify Exercise 5's triangle closed form and its ratio-1 optimum against the brute-force simulator:

Run it yourself with cargo run --release in Rust-QML/ch13-vqe. This is the last lab of Part III. We have kept quanta alive two ways now — by correcting their errors (the expensive, future way) and by designing algorithms shallow enough to survive the errors we cannot yet correct (the pragmatic, present way). What both share is a loop: prepare, measure, adjust, repeat. In VQE and QAOA the “adjust” was a classical optimizer chasing a lower energy. In Part IV it becomes something with a grander name — learning — and the circuits we have just trained turn out to be the first machine-learning models built from amplitudes.