The NISQ Era and Variational Quantum Algorithms

A parameterized quantum circuit (PQC), also called an ansatz, is a quantum circuit $U(\vec\theta)$ built from a fixed sequence of gates whose rotation angles $\vec\theta = (\theta_1, \dots, \theta_m)$ are free classical parameters. Applying $U(\vec\theta)$ to a fixed initial state $|\psi_0\rangle$ (usually $|0\rangots^{\otimes n}$) produces a trial state $|\psi(\vec\theta)\rangle = U(\vec\theta)|\psi_0\rangle$. This is exactly the object introduced under Parameterized Quantum Circuits: a differentiable, trainable quantum state generator, the quantum analogue of a neural network layer. A variational quantum algorithm wraps a PQC in a classical optimization loop. The quantum computer measures some observable — an energy, a cost function, a probability of success — for the current parameters, and the classical computer uses that measurement to propose better parameters, typically via gradient descent or a gradient-free optimizer. The quantum processor never runs a single long, fragile computation; instead it runs the same shallow circuit thousands of times with slightly different parameters, resampling and re-optimizing. This is the defining strategic choice of the NISQ era: sacrifice the theoretical guarantees of deep fault-tolerant circuits for the practical robustness of shallow, repeatable ones. Two flagship instances make this concrete. The Variational Quantum Eigensolver (VQE) targets the ground-state energy of a Hamiltonian $H$, exploiting the variational principle of quantum mechanics: for any normalized state $|\psi\rangle$,

where $E_0$ is the true ground-state energy, with equality if and only if $|\psi\rangle$ is a ground state. Minimizing $\langle\psi(\vec\theta)|H|\psi(\vec\theta)\rangle$ over $\vec\theta$ therefore gives a rigorous upper bound on $E_0$ that tightens as the ansatz improves. The Quantum Approximate Optimization Algorithm (QAOA) targets combinatorial optimization: given a cost function $C(z)$ over bit strings $z \in \{0,1\}^n$, it builds an ansatz from alternating "cost" and "mixer" unitaries, inspired by a Trotterized adiabatic evolution, and searches for parameters that concentrate probability mass on low-cost bit strings.

Variational Quantum Eigensolver. The Hamiltonian $H$, typically the electronic structure Hamiltonian of a molecule, is first decomposed into a sum of Pauli strings via mappings like Jordan-Wigner or Bravyi-Kitaev:

Each Pauli string's expectation value $\langle \psi(\vec\theta)| P_k |\psi(\vec\theta)\rangle$ can be measured directly on hardware by rotating into the eigenbasis of $P_k$ and measuring in the computational basis. The full energy estimate is the weighted sum $\sum_k c_k \langle P_k\rangle$. ``` ALGORITHM VQE(H, ansatz U(θ), initial_θ, optimizer, shots, tol) Decompose H = Σ_k c_k P_k # Pauli decomposition θ ← initial_θ repeat E ← 0 for each Pauli term P_k with coefficient c_k: prepare |ψ(θ)⟩ = U(θ)|0...0⟩ on the QPU rotate basis to diagonalize P_k measure `shots` times, compute empirical ⟨P_k⟩ E ← E + c_k * ⟨P_k⟩ send E (and, if needed, a gradient estimate) to classical optimizer θ ← optimizer.step(θ, E) until |ΔE| < tol or max_iterations reached return θ, E # E approximates E_0 from above ``` The classical optimizer can be gradient-free (Nelder-Mead, COBYLA, SPSA) or gradient-based. A crucial NISQ-friendly fact is the parameter-shift rule: for many common gates (Pauli rotations $R_P(\theta) = e^{-i\theta P/2}$), the exact analytic gradient of an expectation value is

computable using only two extra circuit evaluations on the same hardware, with no need for backpropagation through the quantum device.

Quantum Approximate Optimization Algorithm. Given a classical cost function $C(z)$ over $n$-bit strings, encode it as a diagonal Hamiltonian $H_C$ with $H_C|z\rangle = C(z)|z\rangle$ (built directly from the problem's constraint structure, e.g. edges of a graph for Max-Cut). Define a mixer Hamiltonian, typically $H_M = \sum_i X_i$. The QAOA ansatz at depth $p$ is

alternating $p$ layers of "phase-cost" evolution and "mixing" evolution — a Trotterized approximation to adiabatic evolution from the ground state of $H_M$ toward the ground state of $H_C$. ``` ALGORITHM QAOA(C, p, optimizer, shots, tol) build H_C from cost function C # diagonal in computational basis H_M ← Σ_i X_i # standard transverse-field mixer (γ, β) ← random initial parameters, length p each repeat prepare |+⟩^n for layer l = 1 to p: apply e^{-i γ_l H_C} apply e^{-i β_l H_M} measure in computational basis, `shots` times estimate ⟨C⟩ = Σ_z C(z) · P(observed z) (γ, β) ← optimizer.step(γ, β, ⟨C⟩) until convergence or iteration budget exhausted sample z from final circuit, output best observed z return best z, C(best z) ``` The output is not the expectation value itself but the best bit string sampled from the final distribution — QAOA is fundamentally a sampler tuned to concentrate on good solutions, not an exact solver. ```svg , E(θ) (VQE)

Circuit depth and qubit count. VQE ansätze come in two flavors. Chemically-inspired ansätze like Unitary Coupled Cluster (UCCSD) use $O(n^4)$ gates for $n$ qubits (from double excitations), giving circuits too deep for near-term devices at large $n$. Hardware-efficient ansätze instead use $O(n \cdot L)$ two-qubit gates for $L$ layers of alternating single- and two-qubit rotations, trading chemical accuracy for shallow depth — a direct concession to limited coherence time. QAOA at depth $p$ uses $O(p \cdot m)$ two-qubit gates, where $m$ is the number of cost-function terms (e.g., graph edges for Max-Cut), and $O(p)$ circuit depth in the best case with parallelizable layers.

Measurement cost. Each expectation value $\langle P_k \rangle$ must be estimated from finite samples, and standard concentration bounds show that achieving additive error $\epsilon$ requires

per Pauli term, by Hoeffding's inequality on bounded $\pm 1$-valued measurement outcomes. With $K$ Pauli terms in the Hamiltonian, naively this multiplies total shot budget by $K$, though grouping commuting Pauli terms (Qubit-Wise Commuting or Fully Commuting groupings) reduces the number of distinct circuit settings needed. This $1/\epsilon^2$ scaling — inherited from the statistical nature of quantum measurement, not from any algorithmic inefficiency — is a hard floor: no amount of classical post-processing removes it, only smarter measurement grouping and error mitigation reduce the constant.

Classical optimization cost. The number of classical optimizer iterations to converge is problem- and landscape-dependent, with no universal bound; in the worst case the variational landscape has exponentially many local minima. This is the most honest caveat about these algorithms: unlike Grover's or Shor's algorithm, VQE and QAOA carry no proven worst-case runtime guarantee. Their appeal is empirical and heuristic, akin to classical local-search heuristics for NP-hard problems.

Correctness argument for VQE. Correctness rests entirely on the variational principle. Expand $|\psi(\vec\theta)\rangle$ in the eigenbasis $\{|E_i\rangle\}$ of $H$:

The inequality uses $E_i \geq E_0$ for all $i$ and normalization $\sum_i |\alpha_i|^2 = 1$. Hence every measured energy is a rigorous upper bound on the true ground state, and the algorithm's classical optimizer is simply minimizing this upper bound — the tightest bound achievable is the ansatz's best approximation to $|E_0\rangle$. If the ansatz is not expressive enough to represent states close to $|E_0\rangle$, VQE converges to a biased answer no matter how well the optimizer performs; this is an expressibility limitation, distinct from an optimization failure.

Correctness argument for QAOA. For $p \to \infty$ with optimal parameters, QAOA provably converges to the adiabatic theorem's exact ground state of $H_C$ (Trotterization error vanishes as $p$ grows and step size shrinks). At finite $p$, no general approximation ratio guarantee holds for arbitrary cost functions; specific results exist for special cases (e.g., a $0.6924$ approximation ratio for Max-Cut on 3-regular graphs at $p=1$ was proven by Farhi, Goldstone, and Gutmann), but classical algorithms sometimes match or beat these bounds, making the general-purpose quantum advantage of QAOA unproven in the worst case.

Noise tolerance. These algorithms are explicitly designed around the constraints of The Threshold Theorem: since no logical encoding protects the circuit, every added gate directly multiplies decoherence probability. Shallow ansätze keep the product (depth) × (gate error rate) below the point where output is pure noise, but they cannot escape it entirely — this motivates active error mitigation techniques (zero-noise extrapolation, probabilistic error cancellation) that estimate and subtract noise bias in post-processing without full error correction.

Consider Max-Cut on a 4-node ring graph with edges $\{(0,1),(1,2),(2,3),(3,0)\}$, solved via QAOA at depth $p=1$. The cost Hamiltonian is

maximized (equivalently, $-H_C$ minimized) when adjacent bits differ. The optimal cuts are the two alternating strings $0101$ and $1010$, each cutting all 4 edges (cost 4), while any single bit-flip from these drops the cut value.

Each row corresponds to one full pass of the algorithm: prepare $|{+}\rangle^{\otimes 4}$, apply $e^{-i\gamma H_C}$ (two-qubit $ZZ$ rotations along the four edges), apply $e^{-i\beta H_M}$ (single-qubit $X$ rotations), measure 4096 shots, compute the empirical $\langle C \rangle$, and hand it to a classical optimizer (here, a simple gradient-free search over the two-parameter landscape). By iteration 30, the distribution has concentrated 81% of its probability mass on the two true optimal cuts, and $\langle C \rangle \approx 3.7$ approaches — but does not reach — the maximum possible value of 4, reflecting both finite $p$ and finite shot noise. Running the classical post-processing step "return the best sampled string" would very likely return `0101` or `1010`, the correct answer, even though the expectation value itself never equals the optimum. This illustrates the core QAOA philosophy: it is a biased sampler that concentrates on good answers, not an algorithm that computes the optimal cost value exactly. For VQE, contrast this with the H$_2$ molecule at its equilibrium bond length using a minimal STO-3G basis and a 4-qubit Jordan-Wigner-mapped Hamiltonian. A hardware-efficient ansatz with 2 layers of $R_y$ and $R_z$ rotations plus entangling CNOTs, optimized via gradient descent using the parameter-shift rule, typically converges to within a few milli-Hartree of the exact ground state energy ($-1.137$ Hartree) after 50–100 iterations — close enough for the "chemical accuracy" threshold of $1.6\times10^{-3}$ Hartree in favorable noise conditions, but degrading noticeably as circuit depth or hardware noise increases.

Cloud quantum platforms — IBM Quantum, Google Quantum AI, Amazon Braket, IonQ, and Rigetti's systems — expose exactly the NISQ hardware model this article describes, and VQE/QAOA are the flagship algorithms researchers deploy on them today. Pharmaceutical and materials companies (including partnerships between IBM and Boehringer Ingelheim, or Google's collaborations on catalyst simulation) use VQE-style methods to explore small molecule and materials ground states as a testbed for eventual quantum chemistry advantage. Logistics and finance groups experiment with QAOA on portfolio optimization, routing, and scheduling problems formulated as quadratic unconstrained binary optimization (QUBO), often benchmarking directly against classical heuristics like simulated annealing. The techniques generalize directly into the broader field of Quantum Machine Learning: An Introduction, where parameterized circuits play the role of trainable models, and into open debates addressed under The Outlook for Quantum Advantage, since whether VQE or QAOA can ever provably outperform classical algorithms on practically relevant instances remains one of the field's unresolved central questions.

Ask the tutor: How do barren plateaus specifically depend on ansatz depth and qubit count, and what circuit designs are known to avoid them?