Quantum-Classical Hybrid Algorithms

Every quantum algorithm with a proven exponential speedup — Shor, quantum phase estimation, fault-tolerant chemistry — asks for something today's hardware cannot give: thousands of clean qubits running millions of coherent gates. Real processors decohere after $O(10^2$ – $10^3)$ gates. Quantum-classical hybrid algorithms are the pragmatic answer to that gap. Instead of demanding one deep, fragile circuit, they run many shallow ones and hand the hard part — the iterative search — to a classical computer sitting on top. The quantum device is demoted to a single job: given a parameter vector $\boldsymbol\theta$ , prepare a trial state $|\psi(\boldsymbol\theta)\rangle=U(\boldsymbol\theta)|0\rangle^{\otimes n}$ and return a noisy estimate of one number, an expectation value $E(\boldsymbol\theta)=\langle\psi(\boldsymbol\theta)|H|\psi(\boldsymbol\theta)\rangle$ . A classical optimizer treats that number like any expensive objective and walks downhill. Two algorithms define the paradigm. The Variational Quantum Eigensolver (VQE) finds ground-state energies by minimizing $E(\boldsymbol\theta)$ , leaning on the Rayleigh–Ritz variational principle $E(\boldsymbol\theta)\ge E_0$ to guarantee that lower is always better — a hard floor under the whole landscape. The Quantum Approximate Optimization Algorithm (QAOA) attacks combinatorial cost functions by alternating a problem Hamiltonian and a mixer, a construction that turns out to be a digitized adiabatic sweep. Both sidestep the deep coherent circuits of magic-state distillation or topological computation, and both trade asymptotic guarantees for something you can actually run this year. What they buy in feasibility they pay for in three hard problems — measurement cost, barren plateaus, and the absence of provable speedup — which together define the near-term frontier.

Key takeaways

Hybrid algorithms use a noisy quantum processor only as a fast evaluator of an expectation value $E(\boldsymbol\theta)=\langle\psi(\boldsymbol\theta)|H|\psi(\boldsymbol\theta)\rangle$ over a shallow parameterized circuit, while a classical optimizer iterates the parameters $\boldsymbol\theta$ .
The two flagships are VQE, which minimizes the energy of a Hamiltonian to estimate its ground state, and QAOA, which optimizes $2p$ angles to approximate a classical cost function.
The variational principle $E(\boldsymbol\theta)\ge E_0$ makes the minimization well-posed and gives a rigorous energy upper bound that survives even hardware noise.
Gradients come from hardware exactly, not by finite differences, via the parameter-shift rule $\partial_\theta E=\tfrac12[E(\theta+\tfrac{\pi}{2})-E(\theta-\tfrac{\pi}{2})]$ for gates generated by a two-eigenvalue operator.
The three obstacles are measurement overhead ( $N\sim\epsilon^{-2}$ shots per term), barren plateaus (gradients vanishing as $2^{-\alpha n}$ ), and no proven speedup — these are heuristics for the NISQ era.
Key idea: Use the quantum device only as a fast evaluator of an expectation value $E(\boldsymbol\theta)=\langle\psi(\boldsymbol\theta)|H|\psi(\boldsymbol\theta)\rangle$ over a shallow parameterized circuit, and let a classical optimizer drive $\boldsymbol\theta$ toward the minimum; the variational principle $E(\boldsymbol\theta)\ge E_0$ certifies that lower is always better.

Where this lives today

Hybrid algorithms are the workhorse of the NISQ era, and the frontier is squarely about whether they scale. In quantum chemistry, VQE has mapped the full dissociation curve of H $_2$ on superconducting and trapped-ion hardware — reproducing the exact energy near the $0.74$ Å bond length, about $-1.137$ Hartree — and has reached LiH and BeH $_2$ with hardware-efficient and unitary-coupled-cluster ansätze; the open question is whether any ansatz stays trainable and noise-tolerant past the classically simulable regime. QAOA has been run on hundreds of superconducting qubits and on trapped-ion machines for MaxCut and portfolio problems, but recent analyses show that at fixed shallow depth its approximation ratio can be matched by classical algorithms, so the hunt is for problem structures where it genuinely wins. Around both sits a fast-moving toolkit: error-mitigation methods (zero-noise extrapolation, probabilistic error cancellation) that squeeze usable expectation values out of noisy runs; adaptive ansätze (ADAPT-VQE) that grow the circuit operator by operator to stay shallow; and a rigorous theory of barren plateaus now tied to circuit expressibility, cost-function locality, and entanglement. The honest verdict is that hybrid algorithms have no proven asymptotic speedup — their value is empirical and their limits are theorems, which is exactly why they define the near-term research program rather than settle it.

The physical picture

The right mental model is a factorization. On one side sits a quantum processor acting as a black-box function: feed it $\boldsymbol\theta$ , get back a noisy estimate of $E(\boldsymbol\theta)$ . All the interference, entanglement, and exponentially large state space are hidden inside that one scalar. On the other side sits an ordinary classical optimizer — gradient descent, COBYLA, SPSA — that never sees a qubit and simply asks for objective values at points of its choosing. The two talk through a narrow interface: parameters down, an energy up. That narrowness is exactly what makes the scheme robust on noisy hardware, and it is what the first figure draws.

Figure

The hybrid feedback loop: a shallow parameterized circuit U(θ) on the quantum processor prepares the trial state ψ(θ) and returns a noisy estimate of the energy E(θ) = Σ c_a ⟨P_a⟩, while a classical optimizer updates the angles θ toward the minimum and feeds them back — the quantum device is used only as an expectation-value evaluator

The variational principle does the conceptual heavy lifting. Because $E(\boldsymbol\theta)$ can never dip below the true ground energy $E_0$ , the landscape has a hard floor and every downhill step yields a strictly better certified upper bound on $E_0$ — the same logic behind classical variational methods in physics and chemistry, now lifted onto a quantum state a classical machine could not store. The second figure makes this concrete on the smallest possible problem, a single qubit, where the objective and its floor can be written down exactly.

Figure

The VQE energy landscape for the single-qubit Hamiltonian H = X + Z. The cost E(θ) = ⟨H⟩ = cos θ + sin θ is a pure sinusoid that never falls below the true ground energy E₀ = −√2 ≈ −1.414, reached at θ = 225° where the trial state coincides with the exact ground state — the variational principle in one picture

QAOA reveals a second deep structure: its alternating layers are a Trotterized interpolation between a trivial mixer ground state and the unknown problem ground state. As the number of layers $p\to\infty$ with angles approaching a smooth schedule, QAOA literally becomes a digitized adiabatic sweep and, given a slow enough passage relative to the spectral gap, lands on the exact optimum. Finite $p$ is the compressed, variationally-tuned heuristic that fits on a shallow circuit. And in both algorithms, gradients are not clumsy finite differences but exact quantities extracted from two circuit evaluations — a structural consequence of the fact that each variational gate is generated by an operator with only two eigenvalues, so the expectation value is a pure sinusoid in that angle.

The core equations

The whole method rests on one objective. VQE turns "find the smallest eigenvalue of $H$ " into "minimize a function of $\boldsymbol\theta$ ," and the variational principle certifies that the function is bounded below by the answer you seek.

E(\boldsymbol\theta)=\langle\psi(\boldsymbol\theta)|H|\psi(\boldsymbol\theta)\rangle\ge E_0,\qquad |\psi(\boldsymbol\theta)\rangle=U(\boldsymbol\theta)|0\rangle^{\otimes n} \qquad (1)

where: $E(\boldsymbol\theta)$ — variational energy, the cost minimized classically; $H$ — target Hamiltonian; $E_0$ — true ground-state energy (smallest eigenvalue of $H$ ); $U(\boldsymbol\theta)$ — parameterized ansatz unitary; $\boldsymbol\theta$ — vector of rotation angles. Reading it: any trial state gives an energy at or above $E_0$ , so minimizing can only tighten the bound. A quantum computer cannot measure an arbitrary Hermitian operator directly; it measures qubits in the computational basis. The bridge is to write $H$ as a weighted sum of Pauli strings, each of which is measurable after a single-qubit basis rotation.

H=\sum_{a} c_a\,P_a,\qquad P_a\in\{I,X,Y,Z\}^{\otimes n} \qquad (2)

where: $c_a$ — real coefficient of the $a$ -th Pauli string; $P_a$ — tensor product of single-qubit Paulis; $n$ — number of qubits. A generic two-body chemistry Hamiltonian maps to $O(n^4)$ such terms under Jordan–Wigner or Bravyi–Kitaev. Because every $\langle P_a\rangle$ is estimated by sampling, the energy is a statistical quantity, and its error bar sets the dominant practical cost of VQE. The variance of the estimator controls how many shots you must spend.

\langle H\rangle=\sum_a c_a\langle P_a\rangle,\qquad \mathrm{Var}[\hat E]\le\frac{\big(\sum_a|c_a|\big)^2}{N} \qquad (3)

where: $\langle P_a\rangle$ — expectation of $P_a$ , estimated from measurements; $N$ — shots per term; $\hat E$ — statistical estimator of the energy. Reading it: reaching additive precision $\epsilon$ needs $N\gtrsim(\sum_a|c_a|)^2/\epsilon^2$ shots — an inverse-square law in $\epsilon$ . To optimize, the classical loop needs gradients, and the parameter-shift rule delivers them exactly from the same hardware that evaluates the energy — no finite-difference step size, no truncation error.

\frac{\partial E}{\partial\theta_j}=\frac{1}{2}\left[E\!\left(\theta_j+\tfrac{\pi}{2}\right)-E\!\left(\theta_j-\tfrac{\pi}{2}\right)\right] \qquad (4)

where: $\theta_j$ — the $j$ -th variational angle, whose gate is $e^{-i\theta_j G/2}$ with $G^2=I$ ; $E(\theta_j\pm\pi/2)$ — the objective re-evaluated with that one angle shifted. Reading it: two extra circuit runs per parameter give the analytic derivative, not an approximation. QAOA replaces the free-form ansatz of VQE with a structured one built from the problem itself: alternate a phase separator generated by the cost Hamiltonian with a mixer that spreads amplitude across bitstrings.

|\boldsymbol\gamma,\boldsymbol\beta\rangle=\prod_{k=1}^{p}e^{-i\beta_k H_M}\,e^{-i\gamma_k H_C}\,|+\rangle^{\otimes n} \qquad (5)

where: $H_C$ — problem (cost) Hamiltonian, diagonal in the computational basis; $H_M=\sum_j X_j$ — mixing Hamiltonian; $\gamma_k,\beta_k$ — layer- $k$ angles; $p$ — number of layers (depth); $|+\rangle^{\otimes n}$ — uniform superposition, the ground state of $-H_M$ . The $2p$ angles are the classical parameters. Whichever ansatz is used, the classical side is a plain optimization update: step the parameters against the gradient (or use a gradient-free method that samples the objective).

\boldsymbol\theta^{(t+1)}=\boldsymbol\theta^{(t)}-\eta\,\nabla E(\boldsymbol\theta^{(t)}) \qquad (6)

where: $\eta$ — learning rate; $\nabla E$ — gradient from parameter-shift; $t$ — iteration index. Reading it: everything specific to quantum mechanics is upstream, inside $\nabla E$ ; the update itself is ordinary numerical optimization. The catch that governs scalability is that for expressive random circuits the landscape flattens exponentially, so the gradient the update relies on shrinks below the shot noise.

\mathrm{Var}_{\boldsymbol\theta}\!\left[\partial_{\theta_j} E\right]\;\sim\;2^{-\alpha n},\qquad \alpha>0 \qquad (7)

where: $\mathrm{Var}_{\boldsymbol\theta}$ — variance over random parameters drawn from a unitary $2$ -design; $n$ — qubit number; $\alpha$ — positive constant set by depth and locality. Reading it: on a barren plateau the optimizer needs exponentially many shots even to find a downhill direction.

Derivation AWhy the variational energy can never fall below the ground state

The goal is to prove the single inequality that makes VQE well-posed — that the measured energy of any trial state is an upper bound on the true ground energy, $E(\boldsymbol\theta)\ge E_0$ — and to show the bound is so robust it survives arbitrary hardware noise. We expand the trial state in the exact energy eigenbasis, read off the energy as a probability-weighted average of eigenvalues, and observe that an average of numbers each at least $E_0$ cannot be smaller than $E_0$ . Then we repeat the argument for a mixed state to cover noisy devices.

Step 1. Diagonalize the target: let $H|E_k\rangle=E_k|E_k\rangle$ with $E_0\le E_1\le\cdots$ , and expand the trial state $|\psi(\boldsymbol\theta)\rangle=\sum_k a_k|E_k\rangle$ with $\sum_k|a_k|^2=1$ . Why: every normalized state has such an expansion, so we lose no generality by working in the eigenbasis of the very operator whose lowest eigenvalue we want.

Step 2. Compute the energy by acting with $H$ and using orthonormality: $E(\boldsymbol\theta)=\sum_{k}|a_k|^2 E_k$ . Why: the cross terms vanish because eigenstates are orthogonal, leaving a weighted average of eigenvalues with weights $|a_k|^2$ that are genuine probabilities.

Step 3. Bound the average from below: since every $E_k\ge E_0$ and $\sum_k|a_k|^2=1$ , we get $\sum_k|a_k|^2 E_k\ge E_0\sum_k|a_k|^2=E_0$ , with equality only when all weight lies in the ground space. Why: an average can never undershoot its smallest ingredient, which is precisely the hard floor the optimizer descends toward.

Step 4. Extend to noise: a noisy device prepares a mixed state $\rho$ , and $\mathrm{Tr}(\rho H)=\sum_k \langle E_k|\rho|E_k\rangle E_k\ge E_0$ because the diagonal entries $\langle E_k|\rho|E_k\rangle$ are still non-negative and sum to one. Why: this is why VQE reports a trustworthy upper bound even on imperfect hardware — noise can raise the estimate but never push it below $E_0$ . *Verified: $E(\boldsymbol\theta)=\sum_k|a_k|^2E_k\ge E_0$ ; the mixed-state form $\mathrm{Tr}(\rho H)\ge E_0$ ; recompute against Nielsen and Chuang Ch. 2 (Born rule, spectral decomposition) and the Rayleigh–Ritz principle.*

Go deeper · Derivation B · 1 minHow QAOA becomes an adiabatic sweep in the deep-circuit limit

Derivation BHow QAOA becomes an adiabatic sweep in the deep-circuit limit

The goal is to show that the alternating QAOA ansatz is not an arbitrary heuristic but a Trotterized adiabatic evolution, so that as depth grows it inherits the adiabatic theorem's guarantee of reaching the optimum. We write down a linear interpolation from mixer to problem Hamiltonian, discretize the time-ordered evolution into thin slices, Trotter-split each slice into the two QAOA generators, and identify the initial state — recovering equation (5) exactly, with the layer angles playing the role of a time schedule.

Step 1. Define the adiabatic path $H(t)=(1-\tfrac{t}{T})H_M+\tfrac{t}{T}H_C$ for $t\in[0,T]$ , with evolution $U_{\mathrm{adb}}=\mathcal{T}\exp(-i\int_0^T H(t)\,\mathrm{d}t)$ . Why: this sweeps continuously from a Hamiltonian whose ground state is trivial to the one whose ground state encodes the answer, the standard adiabatic setup.

Step 2. Discretize into $p$ slices of width $\Delta t=T/p$ : $U_{\mathrm{adb}}\approx\prod_{k=1}^{p}\exp[-i\,\Delta t\,H(t_k)]$ . Why: over a thin slice $H(t)$ is nearly constant, so the time-ordered exponential factorizes into a product of ordinary exponentials — the first controlled approximation, exact as $p\to\infty$ .

Step 3. Trotter-split each slice into the two non-commuting pieces, $e^{-i\Delta t\,H(t_k)}\approx e^{-i\gamma_k H_C}e^{-i\beta_k H_M}+O(\Delta t^2)$ , with $\gamma_k=\tfrac{t_k}{T}\Delta t$ and $\beta_k=(1-\tfrac{t_k}{T})\Delta t$ . Why: this is exactly the QAOA layer, and the first-order Trotter error is $O(\Delta t^2)$ per slice, vanishing in the deep-circuit limit.

Step 4. Match the boundary and apply the adiabatic theorem: the mixer ground state is $|+\rangle^{\otimes n}$ , the QAOA initial state, and if $T$ exceeds the inverse-square spectral gap the evolved state tracks the instantaneous ground state, giving $\lim_{p\to\infty}\max_{\boldsymbol\gamma,\boldsymbol\beta}\langle H_C\rangle=C_{\max}$ . Why: deep QAOA thus reaches the exact optimum, while finite- $p$ optimization — free to choose non-monotone schedules — can beat a naive linear sweep at the same depth. *Verified: Suzuki–Trotter first-order splitting (Nielsen and Chuang Sec. 4.7) and the adiabatic theorem; consistent with Farhi, Goldstone, Gutmann (2014).*

Go deeper · Derivation C · 1 minThe parameter-shift rule as an exact hardware gradient

Derivation CThe parameter-shift rule as an exact hardware gradient

The goal is to derive the identity that lets a variational circuit be trained on hardware — that the derivative of an expectation value with respect to a gate angle equals half the difference of the objective at two shifted angles — and to make clear it is an algebraic fact, not a finite-difference approximation. We use that a Pauli-generated gate has a generator squaring to the identity, expand it in an Euler form, differentiate to get a commutator, and then show the two $\pm\tfrac{\pi}{2}$ evaluations reproduce exactly twice that commutator.

Step 1. Write the gate in Euler form using $G^2=I$ : $V(\theta)=e^{-i\theta G/2}=\cos\tfrac{\theta}{2}\,I-i\sin\tfrac{\theta}{2}\,G$ , and let $E(\theta)=\langle\psi|V^\dagger A V|\psi\rangle$ where $A$ absorbs the observable and all later gates. Why: collapsing the rest of the circuit into one effective observable $A$ isolates the single angle we differentiate.

Step 2. Differentiate: the derivative pulls down a factor $-iG/2$ on each side, collecting into $\partial_\theta E=-\tfrac{i}{2}\langle\psi|V^\dagger[A,G]V|\psi\rangle$ . Why: the whole $\theta$ -dependence sits in the conjugation by $V$ , so the gradient is a single commutator expectation — the object the shift rule will reproduce.

Step 3. Evaluate the shifted gates: substituting $\theta\to\theta\pm\tfrac{\pi}{2}$ into the Euler form gives $V(\theta\pm\tfrac{\pi}{2})=\tfrac{1}{\sqrt2}(I\mp iG)V(\theta)$ . Why: because $\cos\tfrac{\pi}{4}=\sin\tfrac{\pi}{4}=\tfrac{1}{\sqrt2}$ , a quarter-turn shift factors cleanly into a fixed Clifford times the original gate — no small-angle limit involved.

Step 4. Subtract the two shifted objectives: the cross terms combine to give $E(\theta+\tfrac{\pi}{2})-E(\theta-\tfrac{\pi}{2})=-i\langle V^\dagger[A,G]V\rangle=2\,\partial_\theta E$ , hence $\partial_\theta E=\tfrac12[E(\theta+\tfrac{\pi}{2})-E(\theta-\tfrac{\pi}{2})]$ . Why: the result is exact for any $\theta$ — the only inaccuracy in practice is the shot noise on the two energy estimates, unlike a finite difference whose step size trades bias against noise. *Verified: direct matrix algebra for $G\in\{X,Y,Z\}$ ; the expectation is a pure sinusoid in $\theta$ , so its derivative is captured exactly by two quarter-period samples; consistent with Mitarai et al. (2018).*

Limiting cases

Hybrid algorithms interpolate between several known regimes, set by circuit depth, ansatz expressivity, and qubit number.

Case	Result	Meaning
$p\to\infty$ (QAOA)	$\lim_{p\to\infty}\max_{\boldsymbol\gamma,\boldsymbol\beta}\langle H_C\rangle=C_{\max}$	infinitely many layers recover the adiabatic theorem and the exact optimum, but demand deep coherent circuits beyond NISQ reach
Expressive ansatz	$\min_{\boldsymbol\theta}E(\boldsymbol\theta)=E_0$	if $U(\boldsymbol\theta)$ can reach the true ground state, VQE is exact in principle; real ansätze are restricted, giving only $E(\boldsymbol\theta)\ge E_0$
Many qubits, deep random ansatz	$\mathrm{Var}[\partial_\theta E]\sim 2^{-\alpha n}$	barren plateau: gradients vanish exponentially in $n$ , so the optimizer sees an essentially flat landscape and stalls
Shallow / local ansatz	$\mathrm{Var}[\partial_\theta E]\sim \mathrm{poly}(n)^{-1}$	local cost functions with logarithmic-depth circuits avoid barren plateaus, restoring trainability
Noisy hardware	$\mathrm{Tr}(\rho H)\ge E_0$ still holds	the variational bound survives, but noise raises the floor and flattens gradients (noise-induced plateaus)

Common trapA low value of E(θ) means the ansatz found the ground state

Not necessarily — and three distinct failures hide behind a "converged" run. First, convergence is to the minimum reachable by your ansatz, not to $E_0$ : if $U(\boldsymbol\theta)$ cannot express the true ground state, the optimizer will happily settle at some $E(\boldsymbol\theta)>E_0$ and report it. The variational bound tells you the answer is an upper bound, never how tight. Second, energies are statistical: each Pauli expectation needs $\sim\epsilon^{-2}$ shots, and with hundreds of terms a single objective evaluation can cost $10^6$ – $10^9$ shots, so a "low" energy may just be a badly under-sampled one. Third, on a barren plateau the gradient is buried in shot noise and the optimizer drifts rather than descends, so apparent flatness can be an exponentially small signal rather than a genuine minimum. A credible VQE result quotes the ansatz, the shot budget, and evidence that the gradient was resolvable.

Worked examples

1 · Single-qubit VQE, done exactly (confidence builder)

Take $H=X+Z$ on one qubit and the ansatz $|\psi(\theta)\rangle=R_y(\theta)|0\rangle=\cos\tfrac{\theta}{2}|0\rangle+\sin\tfrac{\theta}{2}|1\rangle$ . Find the exact ground energy, the optimal angle, and verify the parameter-shift gradient.

Step 1. The true ground energy is the smaller eigenvalue of $H=X+Z$ . Since $H^2=(X+Z)^2=X^2+Z^2+XZ+ZX=2I$ (using $X^2=Z^2=I$ and $XZ+ZX=0$ ), the eigenvalues are $\pm\sqrt2$ . So $E_0=\mathbf{-\sqrt2\approx-1.4142}$ .

Step 2. Build the objective. With $\langle Z\rangle=\cos\theta$ and $\langle X\rangle=\sin\theta$ for this ansatz, $E(\theta)=\langle X\rangle+\langle Z\rangle=\cos\theta+\sin\theta=\sqrt2\,\sin(\theta+45^\circ)$ . Its minimum is $-\sqrt2$ , attained where $\theta+45^\circ=270^\circ$ , i.e. $\theta=\mathbf{225^\circ}$ . The floor equals $E_0$ exactly — this ansatz is expressive enough to reach the ground state.

Step 3. Verify the parameter-shift rule at a generic point, say $\theta=60^\circ$ . The analytic gradient is $E'(\theta)=\cos\theta-\sin\theta=\cos60^\circ-\sin60^\circ=0.5-0.8660=\mathbf{-0.3660}$ . The shift rule gives $\tfrac12[E(150^\circ)-E(-30^\circ)]=\tfrac12[(-0.8660+0.5)-(0.8660-0.5)]=\tfrac12[-0.3660-0.3660]=\mathbf{-0.3660}$ . The two agree to all digits, confirming the gradient is exact, not approximate.

Step 4. Check the optimum: at $\theta=225^\circ$ , $E'=\cos225^\circ-\sin225^\circ=-\tfrac{\sqrt2}{2}+\tfrac{\sqrt2}{2}=0$ , so the gradient vanishes precisely where $E=E_0$ . The optimizer descends a sinusoid to a hard floor at $-\sqrt2$ , reached at $\theta=225^\circ$ , with a gradient it can read exactly from two extra circuit runs.

2 · QAOA on a single edge

Run one QAOA layer ( $p=1$ ) on the MaxCut of a single edge, cost $C=\tfrac12(1-Z_0Z_1)$ so that $C_{\max}=1$ . Find the best achievable approximation ratio.

Step 1. With state $|\boldsymbol\gamma,\boldsymbol\beta\rangle=e^{-i\beta(X_0+X_1)}e^{-i\gamma Z_0Z_1}|+\rangle^{\otimes2}$ , conjugate $Z_0Z_1$ through the mixer using $e^{i\beta X}Ze^{-i\beta X}=\cos2\beta\,Z+\sin2\beta\,Y$ , giving four terms $(\cos2\beta\,Z_0+\sin2\beta\,Y_0)(\cos2\beta\,Z_1+\sin2\beta\,Y_1)$ .

Step 2. Push each term through the phase separator $e^{i\gamma Z_0Z_1}(\cdot)e^{-i\gamma Z_0Z_1}$ and evaluate in $|+\rangle^{\otimes2}$ . The $Z_0Z_1$ and $Y_0Y_1$ terms commute or vanish on $|+\rangle^{\otimes2}$ ; the two mixed terms each contribute $\cos2\beta\sin2\beta\,\sin2\gamma$ . Summing gives $\langle Z_0Z_1\rangle=\mathbf{\sin4\beta\,\sin2\gamma}$ .

Step 3. Hence the expected cut is $\langle C\rangle=\tfrac12(1-\sin4\beta\,\sin2\gamma)$ . Maximizing over the angles drives $\sin4\beta\,\sin2\gamma\to-1$ — for instance $\beta=\tfrac{3\pi}{8}$ , $\gamma=\tfrac{\pi}{4}$ — giving $\langle C\rangle=\mathbf{1}$ and approximation ratio $r=\langle C\rangle/C_{\max}=\mathbf{1}$ .

Step 4. So a single layer solves one edge exactly. This is the easy end of a hard spectrum: on a triangle (3 edges, $C_{\max}=2$ ) the same $p=1$ ansatz cannot separate all edges at once and $r<1$ , and on $3$ -regular graphs Farhi's $p=1$ bound is only $r\ge0.6924$ . $p=1$ is exact on a single edge but merely a bounded heuristic on real graphs — the motivation to grow $p$ .

3 · The measurement budget for chemical accuracy

A molecular Hamiltonian has Pauli coefficients with $\ell_1$ norm $\Lambda=\sum_a|c_a|\approx2$ Hartree. How many shots does one energy evaluation need to reach chemical accuracy, $\epsilon=1.6\times10^{-3}$ Hartree?

Step 1. From the variance bound (3), the requirement is $N\gtrsim\Lambda^2/\epsilon^2$ . This is the naive per-evaluation budget with independent shot allocation across terms.

Step 2. Substitute: $N\gtrsim(2)^2/(1.6\times10^{-3})^2=4/2.56\times10^{-6}\approx\mathbf{1.6\times10^{6}}$ shots — for a single point $\boldsymbol\theta$ , before the optimizer has taken one step.

Step 3. Multiply by the optimization: a run touching thousands of iterations, each needing gradients over dozens of parameters, easily reaches $10^{9}$ – $10^{10}$ shots. Grouping commuting Paulis and smarter estimators cut the prefactor, but the $\epsilon^{-2}$ scaling is why measurement — not gates — is the dominant cost of VQE.

Physics of the portrait

The variational quantum eigensolver is not the work of one person but of a lineage — from Feynman's dream of simulating nature with nature, through the first small chip experiments, to the theory that named its limits.

Origins · 1 minvariational quantum eigensolver and how this was discovered

variational quantum eigensolver

the flagship hybrid algorithm, E(θ) = ⟨ψ(θ) · H

The idea that a quantum computer might be used not to run a deep algorithm but to evaluate a quantity too hard for classical machines traces to Richard Feynman's 1982 proposal to simulate quantum systems with controllable quantum hardware. For three decades this stayed aspirational, waiting on qubits. The variational route was opened in 2014 by Alberto Peruzzo, Jarrod McClean, Alán Aspuru-Guzik and collaborators, who ran the first VQE on a two-qubit photonic chip to estimate the ground-state energy of helium hydride — using the machine only to measure an expectation value and letting a laptop do the optimization. The same year Edward Farhi, Jeffrey Goldstone and Sam Gutmann introduced QAOA, giving the combinatorial-optimization branch of the same paradigm and its first performance bound (the $0.6924$ ratio for $p=1$ MaxCut on $3$ -regular graphs). McClean, Romero, Babbush and Aspuru-Guzik codified the general theory of variational hybrid algorithms in 2016, and in 2018 McClean, Boixo, Smelyanskiy, Babbush and Neven identified the barren-plateau phenomenon that governs whether such circuits are trainable at scale. That same year John Preskill named the era these algorithms serve — Noisy Intermediate-Scale Quantum — arguing that near-term devices, though far from fault tolerance, might still do something useful precisely through this hybrid strategy. The modern picture, $E(\boldsymbol\theta)=\langle\psi(\boldsymbol\theta)|H|\psi(\boldsymbol\theta)\rangle$ minimized against a hard floor $E_0$ , completes what Feynman began: a quantum device turned into a tunable evaluator inside a classical loop.

History

1982

— Feynman proposes simulating quantum systems with controllable quantum hardware

2000

— Farhi, Goldstone, Gutmann, Sipser introduce adiabatic quantum computation

2014

— Peruzzo, McClean, Aspuru-Guzik et al. run the first VQE on a photonic chip; Farhi et al. propose QAOA

2016

— McClean et al. set out the theory of variational hybrid quantum-classical algorithms

2018

— McClean et al. identify barren plateaus; Preskill names the NISQ era

Going further

Texts and papers. Nielsen and Chuang, Quantum Computation and Quantum Information, Ch. 2, 4 (Born rule, Pauli measurement, Suzuki–Trotter) · Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018) · Peruzzo et al., A variational eigenvalue solver on a photonic quantum processor, Nat. Commun. 5, 4213 (2014) · Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014) · McClean, Romero, Babbush, Aspuru-Guzik, The theory of variational hybrid quantum-classical algorithms, New J. Phys. 18, 023023 (2016) · Mitarai et al., Quantum circuit learning, Phys. Rev. A 98, 032309 (2018) · McClean et al., Barren plateaus in quantum neural network training landscapes, Nat. Commun. 9, 4812 (2018) · Cerezo et al., Variational Quantum Algorithms, Nat. Rev. Phys. 3, 625 (2021).

Provenance. The variational bound $E(\boldsymbol\theta)\ge E_0$ is the Rayleigh–Ritz principle applied in the eigenbasis (Nielsen and Chuang Ch. 2). VQE formulation and the $\epsilon^{-2}$ shot scaling: Peruzzo et al. (2014), McClean et al. (2016), with the variance bound from single-shot Pauli variance $\le1$ and the central limit theorem. QAOA and its adiabatic limit: Farhi et al. (2014), first-order Trotter (Nielsen and Chuang Sec. 4.7) plus the adiabatic theorem. Parameter-shift rule: algebraic identity for $G^2=I$ , Mitarai et al. (2018). Barren plateaus: McClean et al. (2018). A verifier should recheck: the eigenbasis bound; $N\gtrsim\Lambda^2/\epsilon^2$ ; the single-qubit worked values ( $E_0=-\sqrt2$ , $\theta=225^\circ$ , gradient $-0.3660$ at $60^\circ$ ); $\langle Z_0Z_1\rangle=\sin4\beta\sin2\gamma$ for single-edge $p=1$ QAOA; and the $\ge0.6924$ MaxCut bound from Farhi et al.

Prerequisites. Variational principle (Rayleigh–Ritz) · Pauli operators and observables · Quantum measurement and Born rule · Magic State Distillation. Leads to. Quantum chemistry simulation · Combinatorial optimization · Topological Quantum Computation.

Ask the tutor: Ask me to walk through the single-qubit VQE landscape step by step, or to show how QAOA's alternating layers turn into an adiabatic sweep as p grows.

What is the actual advantage of a hybrid algorithm if it has no proven speedup?

The advantage is feasibility, not asymptotics. Hybrid algorithms fit on hardware that exists now: shallow circuits, a few hundred to a few thousand gates, run many times, with all the iteration offloaded to a classical machine. They are also partly self-correcting — because the optimizer only cares about the value of $E(\boldsymbol\theta)$ , it can absorb systematic miscalibrations by shifting the parameters, something a fixed deep circuit cannot do. What they do not offer is a theorem that they beat the best classical method. So they are best understood as a bridge: a way to extract possibly-useful results from pre-fault-tolerant devices, and a testbed for the ansätze and error-mitigation ideas that a fault-tolerant machine will inherit.

How is VQE different from classical variational methods like Hartree–Fock?

The structure is identical — pick a parameterized trial state, minimize its energy, lean on $E\ge E_0$ — but the trial state lives somewhere classical methods cannot follow. Hartree–Fock and its descendants restrict the wavefunction to forms a classical computer can store and integrate (a single Slater determinant, or a polynomial-sized expansion). VQE prepares $|\psi(\boldsymbol\theta)\rangle$ directly on qubits, so the trial state can be a genuinely entangled superposition over an exponentially large Hilbert space that no classical representation captures compactly. The optimizer is classical, the bound is the same Rayleigh–Ritz inequality, but the reachable set of trial states is enlarged — that enlargement is the entire hoped-for advantage.

Why not just use finite differences instead of the parameter-shift rule?

You can, but it is worse on both bias and noise. A finite difference $[E(\theta+h)-E(\theta-h)]/2h$ carries an $O(h^2)$ truncation bias, so a small $h$ is needed for accuracy — yet a small $h$ divides two nearly-equal noisy energy estimates by a small number, amplifying the shot noise. You are trapped between bias and variance. The parameter-shift rule sidesteps the tradeoff entirely: because the objective is a pure sinusoid in each angle, the shift $h=\pi/2$ gives the derivative exactly, with no truncation term at all. The only inaccuracy is the statistical noise on the two energy evaluations, which you would have anyway.

Does the parameter-shift rule work for every gate?

No — it works for gates whose generator has just two distinct eigenvalues, the archetype being a Pauli rotation $e^{-i\theta P/2}$ with $P^2=I$ . For those, the expectation is a single sinusoid and the two-point shift is exact. Gates with more eigenvalues (say a controlled rotation seen as a whole, or a multi-frequency generator) produce expectations that are sums of several sinusoids, and then you need a generalized shift rule with more evaluation points, or you decompose the gate into elementary Pauli rotations first. In practice, ansätze are built from single- and two-qubit Pauli rotations precisely so the simple two-point rule applies throughout.

What exactly is a barren plateau, and can it be avoided?

It is an exponential flattening of the cost landscape: for sufficiently expressive random circuits, the gradient's variance decays like $2^{-\alpha n}$ in the qubit number, so away from special points the landscape is essentially flat and the gradient sinks below the shot noise. The optimizer then needs exponentially many shots even to find a downhill direction, erasing any hoped-for scaling. It can be mitigated but not casually ignored: shallow circuits, local (rather than global) cost functions, problem-informed ansätze that break the random-circuit assumption, and careful initialization (for example small-angle or identity-block starts) all help keep gradients polynomially large. Noise introduces its own related flattening, so mitigation and plateau-avoidance are studied together.

How does QAOA compare to just running the adiabatic algorithm?

They are two ends of one continuum. Analog adiabatic quantum computation evolves slowly and continuously from mixer to problem Hamiltonian; QAOA is that same evolution chopped into $p$ discrete alternating steps and then handed to an optimizer to tune the step sizes. The key difference is freedom: the adiabatic schedule is usually fixed (often linear) and must be slow enough to respect the spectral gap, whereas QAOA's angles are optimized and need not follow any monotone schedule, so at a given depth QAOA can outperform a naive adiabatic sweep. As $p\to\infty$ the two coincide and both reach the optimum; at the small $p$ that fits on real hardware, QAOA is the compressed, trainable version.