Chapter 21: The Variational Quantum Computing Paradigm

21.1 Hybrid Quantum-Classical Computing

A variational quantum algorithm follows a simple loop, repeated until convergence:

1. Prepare a parameterized quantum state. Apply a circuit $U(\vec{\theta})$ to some initial state $|0\rangle^{\otimes n}$, where $\vec{\theta} = (\theta_1, \theta_2, \ldots, \theta_p)$ is a vector of $p$ real-valued parameters. The resulting state is $|\psi(\vec{\theta})\rangle = U(\vec{\theta})|0\rangle^{\otimes n}$.
2. Measure an observable. Estimate the expectation value of some operator $O$ in the prepared state: $\langle O \rangle = \langle \psi(\vec{\theta})| O |\psi(\vec{\theta})\rangle$. This requires running the circuit many times (many "shots") and averaging the results.
3. Update parameters classically. Feed the measured expectation value into a classical optimization algorithm, which proposes new parameter values $\vec{\theta}'$ intended to reduce (or increase) $\langle O \rangle$.
4. Repeat. Go back to step 1 with the updated parameters. Continue until the cost function converges.

Why Hybrid?

Current quantum processors - often called Noisy Intermediate-Scale Quantum (NISQ) devices - have tens to hundreds of qubits and limited coherence times. They cannot run the deep circuits required by algorithms like Shor's factoring algorithm or full quantum phase estimation. Variational algorithms are designed specifically for this regime: the quantum circuits can be kept shallow (reducing errors from decoherence), while the classical optimizer handles the complexity of navigating the parameter space.

There is a second, more fundamental reason for the hybrid approach. Quantum computers are exceptionally good at preparing and measuring quantum states that have no efficient classical description. But optimization - the iterative process of searching for the best parameters - is something classical computers do extremely well, with decades of algorithmic development behind them. The variational approach plays to each machine's strengths.

Parameterized Quantum Circuits

The heart of any variational algorithm is the parameterized quantum circuit (PQC), also called an ansatz (from the German word for "approach" or "initial guess"). A PQC is a quantum circuit in which some gates depend on continuous parameters. The most common parameterized gates are rotations:

• $R_y(\theta) = e^{-i\theta Y/2}$, which rotates a qubit around the $y$-axis of the Bloch sphere by angle $\theta$.
• $R_z(\phi) = e^{-i\phi Z/2}$, which applies a phase rotation.
• $R_x(\alpha) = e^{-i\alpha X/2}$, which rotates around the $x$-axis.

These rotation gates are combined with fixed entangling gates (typically CNOT or CZ) to create circuits that can, in principle, reach any quantum state. The parameters $\vec{\theta}$ are the angles of the rotation gates, and adjusting them changes the quantum state produced by the circuit.

Consider a simple two-qubit parameterized circuit: apply $R_y(\theta_0)$ to qubit 0, $R_y(\theta_1)$ to qubit 1, entangle them with a CNOT, then apply another $R_y(\theta_2)$ to qubit 0. By varying $\theta_0$, $\theta_1$, and $\theta_2$, this circuit can produce a rich family of two-qubit states. The simulation below lets you explore this circuit by sweeping a single parameter while holding the others fixed.

Drag the $\theta_0$ slider from $0$ to $2\pi$ while keeping $\theta_1$ and $\theta_2$ fixed. Watch how the output probability distribution changes smoothly as the parameter varies. This smooth dependence on parameters is what makes gradient-based optimization possible - small changes in $\theta$ produce small changes in the measurement statistics.

The Cost Function

Every variational algorithm defines a cost function (also called an objective function or loss function) that the classical optimizer seeks to minimize. In most cases, the cost function is the expectation value of some Hermitian operator $H$:

For the Variational Quantum Eigensolver, $H$ is the Hamiltonian of a physical system, and $C(\vec{\theta})$ is the energy. The variational principle of quantum mechanics guarantees that $C(\vec{\theta}) \geq E_0$, where $E_0$ is the true ground-state energy. Minimizing $C$ over all parameters $\vec{\theta}$ therefore yields an upper bound on - and ideally a close approximation to - the ground-state energy.

Not every cost function is an energy. Variational algorithms have been proposed for a wide range of objectives: minimizing the distance to a target state (variational state preparation), maximizing the value of a combinatorial objective (QAOA), minimizing a classification loss (variational quantum machine learning), and even compiling quantum circuits (variational quantum compiling). In each case, the cost function is designed so that the quantum computer evaluates something hard to compute classically, while the classical optimizer navigates the parameter space.

Convergence and Termination

The variational loop must eventually stop. Common termination criteria include:

• Energy convergence: Stop when $|C(\vec{\theta}^{(k)}) - C(\vec{\theta}^{(k-1)})| < \epsilon$ for some tolerance $\epsilon$ (e.g., $\epsilon = 10^{-3}$ Hartree for chemical accuracy).
• Gradient norm: Stop when $||\nabla C|| < \delta$, indicating the optimizer has reached a stationary point.
• Iteration budget: Stop after a fixed number of iterations, chosen based on available quantum resources.

There is no general guarantee that the variational loop will converge to the global minimum. The optimizer may get trapped in a local minimum, or the ansatz may not be expressive enough to represent the true ground state. These limitations are inherent to the variational approach and motivate the careful ansatz design discussed in the next section.

21.2 Ansatz Design

The choice of ansatz - the structure of the parameterized circuit - is arguably the most important decision in variational quantum computing. A good ansatz must satisfy three competing requirements: it must be expressive enough to represent the target state, trainable (its parameters can be efficiently optimized), and implementable on real hardware with acceptable circuit depth.

Hardware-Efficient Ansatze

The hardware-efficient ansatz (HEA), introduced by Kandala et al. at IBM in 2017, takes a pragmatic approach: build the circuit from whatever gates the hardware natively supports. A typical HEA consists of $L$ repeated layers, where each layer applies single-qubit rotations to every qubit followed by a fixed pattern of entangling gates (e.g., nearest-neighbor CNOTs on a linear chain).

For $n$ qubits and $L$ layers, a typical HEA has $O(nL)$ parameters. The circuit depth is $O(L)$, which can be kept shallow by limiting the number of layers. The appeal is simplicity and hardware compatibility - every gate in the circuit is directly executable without decomposition.

The downside: hardware-efficient ansatze are not informed by the problem's structure. They explore the full Hilbert space democratically, which means most of the parameter space may be irrelevant to the problem at hand. As we will discuss in Section 21.4 and in Chapter 22, this lack of structure can lead to barren plateaus - regions of the parameter landscape where gradients vanish exponentially, making optimization impossible.

Chemically-Inspired Ansatze

For quantum chemistry problems, a more principled approach is to design the ansatz based on the physics of the system being simulated. The most prominent example is the Unitary Coupled Cluster Singles and Doubles (UCCSD) ansatz:

where $|\phi_0\rangle$ is a reference state (typically the Hartree-Fock ground state) and $T = T_1 + T_2$ is the cluster operator containing single excitations ($T_1$, which promote one electron from an occupied orbital to a virtual orbital) and double excitations ($T_2$, which promote two electrons). The operator $e^{T - T^\dagger}$ is explicitly unitary, unlike the classical coupled cluster operator $e^T$ used in traditional quantum chemistry.

UCCSD ansatze have several advantages: they respect the symmetries of the molecule (particle number, spin), they are systematically improvable (add triples, quadruples, etc.), and they encode genuine chemical intuition about electron correlation. The disadvantage is circuit depth - implementing $e^{T - T^\dagger}$ on a quantum computer requires Trotterization, which can produce very deep circuits for large molecules.

Problem-Specific Ansatze

Beyond chemistry, different problems call for different ansatz structures:

• QAOA ansatz: For combinatorial optimization, the Quantum Approximate Optimization Algorithm uses alternating layers of a "problem" unitary $e^{-i\gamma_k H_C}$ (encoding the cost function) and a "mixer" unitary $e^{-i\beta_k H_M}$ (enabling transitions between states). The parameters are the angles $\gamma_k$ and $\beta_k$.
• Hamiltonian variational ansatz: Inspired by adiabatic quantum computing, this ansatz applies Trotterized evolution under the target Hamiltonian with variable time steps. It naturally respects the symmetries of the Hamiltonian.
• Symmetry-preserving ansatze: Circuits designed to preserve specific quantum numbers (total particle number, total spin) throughout the optimization. This reduces the effective search space and often improves convergence.

The Expressiveness-Trainability Trade-off

A central tension pervades ansatz design. An ansatz with very few parameters may be fast to optimize but unable to represent the target state. An ansatz with many parameters can represent nearly any state but may be impossible to train - its optimization landscape becomes an exponentially flat "barren plateau" (discussed further in Chapter 22). The sweet spot is an ansatz that is just expressive enough: it contains the target state in its reachable set but constrains the search to a low-dimensional manifold of the full Hilbert space.

Quantitatively, the expressibility of an ansatz measures how uniformly its parameter space covers the space of quantum states. A fully expressible ansatz (one that can produce any state) forms a 2-design over the unitary group, which is precisely the condition that triggers barren plateaus. Practical ansatze aim for high expressibility within the subspace relevant to the problem, while having limited expressibility in irrelevant directions.

Interactive: Ansatz Explorer

Explore different parameterized circuit architectures (ansatze) used in variational quantum algorithms. Each ansatz has a different structure, parameter count, and expressibility. The circuit depth and parameter count grow with layers.

21.3 The Measurement Problem: Estimating Expectation Values

The variational loop requires evaluating $\langle \psi(\vec{\theta})| H |\psi(\vec{\theta})\rangle$, but a quantum computer does not return expectation values directly. It returns individual measurement outcomes - bit strings - sampled from the output distribution. To extract an expectation value, we must understand how to decompose the operator $H$ into measurable pieces and how many measurements ("shots") we need.

Pauli Decomposition

Any Hermitian operator on $n$ qubits can be written as a weighted sum of Pauli strings:

where each $P_i$ is a tensor product of Pauli operators $P_i \in \{I, X, Y, Z\}^{\otimes n}$ and $c_i$ are real coefficients. For example, the Hamiltonian of the hydrogen molecule (in a minimal basis) can be written as:

with six terms. Each Pauli string can be measured independently: to measure a string like $X \otimes Z$, apply a basis rotation (Hadamard on the first qubit, identity on the second), then measure both qubits in the computational basis. The eigenvalues of any Pauli string are $\pm 1$, so each shot returns $+1$ or $-1$, and the expectation value is estimated by averaging over many shots.

The linearity of expectation then gives us:

We measure each Pauli string separately, multiply by its coefficient, and sum the results.

Shot Budgets and Statistical Error

Each individual measurement of a Pauli string returns $+1$ or $-1$. If the true expectation value is $\langle P_i \rangle$, then after $N_s$ shots, the sample mean has a standard error of:

The total error in $\langle H \rangle$ depends on how we distribute shots among the Pauli terms. If there are $M$ terms and we allocate $N_s$ shots to each, the total number of shots is $M \times N_s$, and the total statistical error scales as:

This reveals a key challenge: as the system size grows, the number of Pauli terms $M$ can grow polynomially (e.g., $O(n^4)$ for molecular Hamiltonians with $n$ qubits), and the total shot count required for a given precision grows correspondingly. Techniques like grouping commuting Pauli strings (measuring compatible observables simultaneously) can significantly reduce the measurement overhead.

Measurement Grouping

Two Pauli strings that commute (i.e., $[P_i, P_j] = 0$) can be measured simultaneously using the same set of shots. For example, $Z \otimes I$ and $I \otimes Z$ commute (both are diagonal in the computational basis), so a single measurement of both qubits provides data for both terms. More aggressive grouping strategies - qubit-wise commutativity, general commutativity, or even non-commuting measurement techniques - can reduce the number of distinct measurement settings from hundreds or thousands down to a manageable number.

Basis Rotations for Non-Z Measurements

A quantum computer typically measures in the computational (Z) basis. To measure a Pauli string containing $X$ or $Y$ operators, we must rotate the relevant qubits before measurement:

• To measure $X$: Apply a Hadamard gate $H$ before measurement. This rotates the $X$ eigenbasis ($|+\rangle$, $|-\rangle$) to the $Z$ eigenbasis ($|0\rangle$, $|1\rangle$).
• To measure $Y$: Apply $S^\dagger$ then $H$ (equivalently, $HS^\dagger$) before measurement. This rotates the $Y$ eigenbasis to the $Z$ eigenbasis.
• To measure $Z$: No rotation needed - measure directly in the computational basis.
• To measure $I$: The identity contributes a constant $c_0$ to the energy and requires no measurement at all.

For a Pauli string like $X \otimes Y \otimes Z$, apply $H$ to the first qubit, $S^\dagger$ then $H$ to the second qubit, and nothing to the third, then measure all three in the computational basis. The product of measurement outcomes ($\pm 1$) gives the eigenvalue of the Pauli string for that shot.

Optimal Shot Allocation

A naive strategy allocates the same number of shots $N_s$ to each Pauli term. A smarter approach allocates more shots to terms with larger coefficients $|c_i|$, since these contribute more to the total energy error. The optimal allocation (minimizing total variance for a fixed shot budget) assigns shots proportional to $|c_i| \cdot \text{Var}(P_i)^{1/2}$. In practice, this can reduce the total number of shots needed for a given precision by a factor of two or more compared to uniform allocation.

21.4 Classical Optimizers for Quantum Circuits

The classical optimizer is the "brain" of the variational loop. Given the current cost function value $C(\vec{\theta})$, it must propose new parameters $\vec{\theta}'$ that reduce $C$. This is a standard optimization problem, but with unusual challenges: the cost function is noisy (estimated from finite shots), the parameter landscape may have many local minima, and evaluating $C$ is expensive (it requires running a quantum circuit).

Gradient-Free Methods

The simplest approach is to use optimizers that do not require gradient information:

• Nelder-Mead (simplex method): Maintains a simplex of $p+1$ points in parameter space and iteratively reflects, expands, or contracts the simplex to find a minimum. Robust to noise but converges slowly in high dimensions.
• COBYLA (Constrained Optimization by Linear Approximation): Builds linear models of the cost function and constraints. Popular in VQE because it handles noisy function evaluations reasonably well.
• SPSA (Simultaneous Perturbation Stochastic Approximation): Estimates gradients using only two function evaluations per iteration, regardless of the number of parameters. Particularly well-suited to noisy quantum cost functions.

Gradient-Based Methods

Gradient-based optimizers - gradient descent, Adam, L-BFGS - typically converge faster than gradient-free methods when accurate gradients are available. The challenge is computing $\nabla_{\vec{\theta}} C(\vec{\theta})$ on a quantum computer.

Classical automatic differentiation (backpropagation) does not work on quantum hardware, because we cannot inspect intermediate quantum states without collapsing them. Instead, the quantum computing community has developed the parameter shift rule, which computes exact analytical gradients using only circuit evaluations.

The Parameter Shift Rule

For a cost function of the form $C(\theta) = \langle 0| U^\dagger(\theta) H U(\theta) |0\rangle$, where $U(\theta)$ contains a gate of the form $e^{-i\theta G/2}$ with $G$ having eigenvalues $\pm 1$ (which includes all standard Pauli rotations $R_x$, $R_y$, $R_z$), the partial derivative with respect to $\theta$ is:

where $s = \pi/2$ is the standard shift. With $s = \pi/2$, this simplifies to:

This is remarkable: to compute the gradient with respect to one parameter, we simply evaluate the same circuit twice - once with $\theta$ shifted forward by $\pi/2$, once shifted backward - and take the difference. No finite-difference approximation is needed; the result is the exact analytical gradient.

The simulation below demonstrates the parameter shift rule in action. Sweep the angle $\theta_0$ to see how the energy landscape varies, and observe how the gradient (the slope of the energy curve) changes sign at the minimum. The circuit prepares a parameterized state and measures the expectation value of $Z \otimes Z$, simulating the core operation of a variational algorithm.

As you sweep $\theta_0$ from $0$ to $2\pi$, notice that the probability distribution oscillates smoothly. The minima and maxima of the energy correspond to zeros of the gradient. A gradient-based optimizer would follow the downhill direction, stepping toward the nearest minimum. The parameter shift rule tells the optimizer precisely which direction is downhill by evaluating the circuit at $\theta_0 \pm \pi/2$.

Interactive: Parameter Energy Landscape

Visualize how the cost function $\langle ZZ \rangle$ varies as a single parameter sweeps from $0$ to $2\pi$. The sinusoidal shape confirms the parameter shift rule prediction.

Interactive: 2D Energy Landscape

Explore the full two-parameter energy landscape. Adjust both parameters to find the minimum of $\langle ZZ \rangle$. The circuit uses $R_y(\theta_0)$ on qubit 0 and $R_y(\theta_1)$ on qubit 1 with a CNOT entangler.

Interactive: Ansatz Gallery

Explore different parameterized circuit architectures (ansatze) used in variational quantum algorithms. Each ansatz has a different structure, parameter count, and expressibility. The circuit depth and parameter count grow with layers.

Interactive: Parameter Shift Rule

Compare the parameter shift rule (exact) with finite differences (approximate). Enter parameter values and compute the gradient vector for the $\langle ZZ \rangle$ cost function.

Choosing an Optimizer

The choice between gradient-free and gradient-based methods depends on the problem:

In practice, many VQE implementations use a two-stage strategy: start with a gradient-free method (like COBYLA) to find a rough neighborhood of the minimum, then switch to a gradient-based method (like Adam or L-BFGS with parameter shift gradients) to refine the answer. The SPSA optimizer occupies a middle ground - it estimates gradients stochastically with just two circuit evaluations per step (regardless of the number of parameters), making it efficient for high-dimensional problems at the cost of noisier gradient estimates.

Why the Parameter Shift Rule Works

The mathematical reason behind the parameter shift rule is elegant. For a gate $e^{-i\theta G/2}$ where $G$ has eigenvalues $\pm 1$, the cost function $C(\theta) = \langle 0|V^\dagger e^{i\theta G/2} H e^{-i\theta G/2} V|0\rangle$ (where $V$ contains all other gates) is a sinusoidal function of $\theta$:

for some constants $A$, $B$, $\phi$ determined by the rest of the circuit and the observable. The derivative of a sine function is a cosine, and $\cos(\theta) = \sin(\theta + \pi/2)$. Therefore:

This identity holds exactly, not approximately. The parameter shift rule exploits the trigonometric structure that arises naturally from Pauli rotation gates. For gates with generators having more than two distinct eigenvalues, generalized parameter shift rules exist that require additional circuit evaluations but maintain the same analytical exactness.

SPSA: A Practical Compromise

The SPSA (Simultaneous Perturbation Stochastic Approximation) optimizer deserves special mention for variational quantum algorithms. Unlike the parameter shift rule, which computes each component of the gradient separately (requiring $2p$ circuit evaluations), SPSA estimates the entire gradient direction using just two circuit evaluations, regardless of $p$:

where $\vec{\Delta}$ is a random perturbation vector (each component drawn from $\{-1, +1\}$ with equal probability) and $\epsilon$ is a small step size. This estimate is unbiased on average, meaning that over many iterations, SPSA converges to the same minimum as exact gradient descent. The trade-off is variance: each individual gradient estimate is noisy, so SPSA typically requires more iterations to converge. For circuits with hundreds of parameters, the per-iteration savings of SPSA (2 evaluations vs. $2p$) can make it the only feasible choice.