The quantum algorithms most likely to produce practical results on today’s hardware are not Shor’s algorithm or Grover’s algorithm — both require error correction that does not yet exist at useful scale. The near-term candidates are variational quantum algorithms: hybrid quantum-classical procedures where a shallow parametrised quantum circuit runs on noisy hardware, a classical computer estimates an objective function from measurement outcomes, and a classical optimiser adjusts the circuit parameters to improve it.

The approach works because the quantum circuit does something useful that is hard to simulate classically — evaluating an expectation value of a quantum Hamiltonian, or estimating the quality of a candidate solution to a combinatorial problem — while offloading the computationally cheap part (parameter optimisation) to classical hardware that handles noise and imprecision gracefully.

Two variational algorithms dominate the NISQ landscape. VQE (Variational Quantum Eigensolver) finds ground state energies of molecular Hamiltonians — the central computational problem in quantum chemistry. QAOA (Quantum Approximate Optimization Algorithm) finds approximate solutions to combinatorial optimisation problems such as Max-Cut, scheduling, and portfolio allocation. Both share the same architecture and the same fundamental limitations. Understanding them requires starting with the mathematical principle they both exploit.

Key Concepts in This Article

Variational Principle

For any trial quantum state |ψ(θ)⟩, the expectation value ⟨ψ(θ)|H|ψ(θ)⟩ ≥ E₀, the true ground state energy. Minimising this expectation value over θ drives the state toward the ground state.

Ansatz

The parametrised circuit structure U(θ) used to prepare the trial state. Chemistry-inspired ansätze mirror the structure of electron correlation; hardware-efficient ansätze match device connectivity. The ansatz choice determines what solutions are reachable.

Cost Hamiltonian

In QAOA, a diagonal operator H_C whose eigenvalues equal the objective function value for each computational basis state. The algorithm maximises ⟨H_C⟩ by constructive interference on high-cost states.

Approximation Ratio

The ratio of QAOA's expected solution quality to the optimal solution: r = ⟨C⟩/C_max. QAOA at p=1 layers achieves r ≥ 0.6924 for Max-Cut. The Goemans-Williamson classical algorithm achieves r ≥ 0.878.

The Variational Principle: The Mathematical Foundation

Both VQE and QAOA rest on a single theorem from quantum mechanics: the variational principle. For any Hamiltonian HH with ground state energy E0E_0 and any normalised quantum state ∣ψ⟩|\psi\rangle:

⟨ψ∣H∣ψ⟩≥E0\langle\psi|H|\psi\rangle \geq E_0

The expectation value of H in any state is always at least as large as the ground state energy. Equality holds only when |ψ⟩ is exactly the ground state.

This gives an algorithm: prepare a family of parametrised states ∣ψ(θ)⟩|\psi(\theta)\rangle, measure ⟨H⟩\langle H \rangle for each θ\theta, and minimise over θ\theta. The minimum found is an upper bound on E0E_0; as the parametrised family becomes more expressive, the bound tightens. The quantum computer’s job is to prepare ∣ψ(θ)⟩|\psi(\theta)\rangle and estimate ⟨H⟩\langle H \rangle — both tasks that are classically hard for large systems. The classical computer’s job is to adjust θ\theta to reduce ⟨H⟩\langle H \rangle.

VQE: Quantum Chemistry’s Killer Application

The central computational problem in quantum chemistry is finding the ground state energy of a molecular Hamiltonian — the energy of the electrons in the lowest-energy configuration for a given nuclear geometry. This energy determines molecular structure, reaction rates, transition states, and binding affinities. Classical methods for solving this problem — CCSD(T), DMRG, quantum Monte Carlo — scale poorly with system size, typically as O(N^6) to O(N^7) in the number of electrons N for the highest-accuracy methods. Quantum chemistry is one of the most computationally expensive problems in science.

VQE was proposed in 2014 by Peruzzo, McClean, and collaborators, and demonstrated on a photonic quantum processor using the hydrogen molecule H₂ — the smallest possible quantum chemistry calculation. The idea: map the molecular Hamiltonian onto qubits using the Jordan-Wigner or Bravyi-Kitaev transformation, prepare a parametrised trial state, and use the variational principle to optimise the circuit parameters until the energy converges.

VQE — HYBRID QUANTUM-CLASSICAL LOOP QUANTUM PROCESSOR U(θ) ansatz circuit |ψ(θ)⟩ Measure ⟨Pᵢ⟩ for each Pauli term ⟨H⟩ = Σᵢ cᵢ⟨Pᵢ⟩ ⟨H⟩(θ) CLASSICAL OPTIMIZER minimise ⟨H⟩(θ) over θ gradient-free: COBYLA, BFGS gradient: parameter-shift rule ∂⟨H⟩/∂θ = [⟨H⟩(θ+π/2)−⟨H⟩(θ−π/2)]/2 converged → θ*, E₀ ≈ ⟨H⟩(θ*) updated θ Input: molecular Hamiltonian H
Figure 1 — The VQE hybrid loop. The quantum processor prepares a parametrised trial state |ψ(θ)⟩ using an ansatz circuit U(θ), then measures expectation values ⟨Pᵢ⟩ for each Pauli string in the Hamiltonian decomposition. The classical computer combines these into ⟨H⟩(θ) and runs an optimiser to find new parameters θ that reduce the energy. The loop iterates until convergence. The classical optimiser uses either gradient-free methods or the parameter-shift rule to compute analytic quantum gradients without finite-difference approximations.

The Hamiltonian in Pieces: Pauli Decomposition

A molecular Hamiltonian, once mapped to qubits via Jordan-Wigner or Bravyi-Kitaev transformation, becomes a weighted sum of Pauli operator strings. For hydrogen H₂ in a minimal basis (STO-3G), the qubit Hamiltonian takes the form:

H₂ HAMILTONIAN — PAULI DECOMPOSITION (STO-3G, R=0.74 Å) PAULI TERM COEFFICIENT (hartree) MEASUREMENT CIRCUIT −0.8126 · II constant no measurement needed +0.1711 · IZ +0.1711 measure qubit 1 in Z basis −0.2252 · ZI −0.2252 measure qubit 0 in Z basis +0.1736 · ZZ +0.1736 measure both qubits in Z basis +0.1200 · XX +0.1200 rotate both to X basis, then measure Z +0.1200 · YY +0.1200 rotate both to Y basis, then measure Z
Figure 2 — The H₂ qubit Hamiltonian in the STO-3G basis at bond length 0.74 Å, after Jordan-Wigner mapping to 2 qubits. Each Pauli string is measured with a separate circuit configuration; the expectation values are multiplied by their coefficients and summed classically to produce ⟨H⟩. For larger molecules the number of Pauli terms scales as O(N⁴) in the number of molecular orbitals — the primary measurement bottleneck in VQE.

Each Pauli string requires a separate set of measurements. The diagonal terms (IZ, ZI, ZZ) are measured directly in the computational basis. The off-diagonal terms (XX, YY) require a basis rotation — applying Hadamard or S·H gates before measurement — to convert the X or Y expectation value into a Z measurement. The total number of circuit executions (“shots”) grows with the number of Pauli terms and the required statistical precision.

For H₂ in a minimal basis: 5 terms, manageable. For a larger molecule like FeMo-co (the active site of nitrogenase, relevant for nitrogen fixation): ~10⁸ Pauli terms — a measurement overhead that makes VQE intractable without grouping commuting terms or other mitigation techniques.

The Ansatz Problem

The choice of ansatz — the parametrised circuit family — determines both the expressibility of the trial states and the depth of the circuit required. Three classes dominate:

Chemistry-inspired (UCCSD): The Unitary Coupled Cluster Singles Doubles ansatz builds circuit layers from fermionic excitation operators motivated by quantum chemistry. It is a physically motivated approximation to the exact ground state but requires deep circuits — too deep for current NISQ hardware without significant truncation.

Hardware-efficient: Generic parametrised layers matched to the native gate set and connectivity of the target device. Shallower and more practical on noisy hardware, but may lack the expressibility to represent the true ground state for complex molecules. Can be trapped in spurious local minima with no physical interpretation.

ADAPT-VQE: A greedy algorithm that grows the ansatz one operator at a time by adding the operator from a predefined pool that most reduces the gradient of ⟨H⟩. More efficient than UCCSD while remaining chemistry-motivated, at the cost of a more complex classical loop.

QAOA: Combinatorial Optimisation on Quantum Hardware

QAOA was introduced by Farhi, Goldstone, and Gutmann in 2014 as a near-term-executable approximation to the quantum adiabatic algorithm. Where VQE targets continuous energy minimisation in chemistry, QAOA targets combinatorial optimisation: finding a bit string x ∈ {0,1}ⁿ that maximises (or minimises) a classical objective function C(x).

The canonical example is Max-Cut: given a graph G = (V, E), partition the vertices into two sets S and V\S to maximise the number of edges crossing the partition.

QAOA FOR MAX-CUT — GRAPH AND ENCODING GRAPH G — OPTIMAL CUT = 4 EDGES 0 1 2 3 cut Set S = {0, 2} Set V\S = {1, 3} QAOA ENCODING Cost function: C(x) = number of cut edges = Σ_{(i,j)∈E} (1 − zᵢzⱼ)/2 where zᵢ = 1 − 2xᵢ ∈ {+1, −1} Cost Hamiltonian: H_C = Σ_{(i,j)∈E} (I − ZᵢZⱼ)/2 Optimal: x = 0101 or 1010 → C = 4 QAOA maximises ⟨H_C⟩ over γ, β parameters
Figure 3 — Max-Cut on a 4-cycle graph C₄. The optimal partition places nodes {0,2} in one set (blue) and {1,3} in the other (yellow), cutting all four edges — the maximum possible. The cost function C(x) = Σ (1−zᵢzⱼ)/2 is encoded as the diagonal quantum Hamiltonian H_C, whose eigenstates are computational basis states and whose eigenvalues are the number of cut edges. QAOA maximises ⟨H_C⟩ by preparing a quantum state in which high-cut solutions have large probability amplitudes.

The QAOA Circuit

QAOA CIRCUIT — p = 2 LAYERS (4-QUBIT EXAMPLE) q₀ q₁ q₂ q₃ H⊗⁴ |+⟩⊗⁴ layer p=1: γ₁, β₁ e^{−iγ₁H_C} ZZ gates on each edge e^{−iβ₁H_B} Rx(2β₁) on each qubit layer p=2: γ₂, β₂ e^{−iγ₂H_C} ZZ gates e^{−iβ₂H_B} Rx(2β₂) Measure compute ⟨H_C⟩ Classical optimiser → γ*, β* 2p = 4 variational parameters: (γ₁, β₁, γ₂, β₂)
Figure 4 — QAOA circuit for p=2 layers. Starting from the uniform superposition |+⟩⊗⁴ (from Hadamard on each qubit), two alternating blocks are applied: the phase separator e^{−iγH_C} (implemented as ZZ rotations on each graph edge) and the mixer e^{−iβH_B} (implemented as Rx rotations on each qubit). With p layers there are 2p variational parameters. The classical optimiser tunes γ and β to maximise ⟨H_C⟩, which equals the expected number of cut edges in a random sample from the output state.

The QAOA circuit has a fixed structure motivated by the quantum adiabatic algorithm. Starting from the uniform superposition over all 2ⁿ bit strings:

Phase separator e−iγHCe^{-i\gamma H_C}: a diagonal unitary that multiplies each computational basis state ∣x⟩|x\rangle by e−iγC(x)e^{-i\gamma C(x)}. For Max-Cut, this is implemented by a ZZ rotation on each edge: e−iγZiZj/2e^{-i\gamma Z_i Z_j / 2}. This gate adds a phase proportional to the cost — high-cost states accumulate more phase.

Mixer e−iβHBe^{-i\beta H_B}: where HB=∑iXiH_B = \sum_i X_i. Applied as independent Rx(2β)R_x(2\beta) rotations on each qubit, this gate mixes the amplitudes across different bit strings, preventing the state from getting stuck in a single basis state. Without the mixer, the phase separator would do nothing useful.

The alternation of phase separator and mixer is the quantum analogue of alternating between “evaluate the cost” and “explore the solution space.” With pp layers, the algorithm has 2p2p variational parameters (γ1,…,γp,β1,…,βp)(\gamma_1, \dots, \gamma_p, \beta_1, \dots, \beta_p) that are optimised classically.

Key theoretical result: as p → ∞ with appropriate parameters, QAOA converges to the exact optimum — it recovers the quantum adiabatic algorithm in the limit. For finite p, it produces approximations whose quality improves monotonically with p.

What QAOA Actually Achieves

For Max-Cut, the theoretical performance of QAOA is known precisely at p=1:

QAOA₁(Max-Cut) achieves an approximation ratio ≥ 0.6924 for 3-regular graphs

This means QAOA at a single layer finds, on average, at least 69.24% of the optimal cut. This is better than random (0.5) but worse than the best classical algorithm: the Goemans-Williamson (GW) algorithm, which achieves a guaranteed approximation ratio of ≥ 0.878 using semidefinite programming — a classical polynomial-time algorithm.

For p=2 and beyond, the approximation ratio improves but the classical simulation becomes harder to bound theoretically. Numerical experiments on random graphs suggest QAOA can approach or match GW for moderate p, but no proof of quantum advantage over GW has been established for any p.

The honest picture: QAOA has not been shown to outperform the best classical algorithms for Max-Cut, MAXSAT, or any other standard combinatorial optimisation problem at any circuit depth currently implementable. This is not a fatal objection to QAOA — quantum advantage may exist for specific problem instances, specific graph structures, or at circuit depths not yet experimentally accessible — but it is the state of knowledge as of mid-2025.

The Classical Optimiser Problem

Both VQE and QAOA face a challenge from the classical optimisation loop that is independent of hardware quality: the barren plateau problem. As circuit depth and qubit count grow, the gradient of the objective function with respect to circuit parameters vanishes exponentially in the number of qubits. The classical optimiser navigates an increasingly flat landscape where every direction looks equally uninformative.

This problem, covered in depth in Vanishing Gradients at Quantum Scale, is the most fundamental obstacle to scaling variational algorithms. Hardware-efficient ansätze are particularly susceptible because they lack the structural inductive bias of chemistry-inspired designs. Mitigation strategies — local cost functions, problem-inspired initialisation, layerwise training — partially address the issue but do not eliminate it.

Beyond barren plateaus, both algorithms face:

VQE: Where It Stands

VQE has been experimentally demonstrated for small molecules on superconducting, trapped-ion, and photonic hardware. Key milestones:

The fundamental problem: every molecule VQE has simulated can be computed more accurately — and faster — by classical quantum chemistry methods (CCSD(T), DMRG, selected CI) on classical computers. The quantum advantage regime requires approximately 50–100 qubits of system size with circuit depths that exceed current NISQ capabilities. The crossover point — where VQE on quantum hardware beats CCSD(T) for chemistry of practical interest — has not been reached.

The Path Forward

The trajectory of both QAOA and VQE leads through error correction. The near-term NISQ versions are constrained by noise tolerance, circuit depth, and qubit count. The long-term versions — fault-tolerant quantum algorithms for chemistry and optimisation — are genuinely exponentially hard classically and would require logical qubit resources that will not be available for years to decades.

The intermediate case — “early fault-tolerant” algorithms that use partial error correction to run somewhat deeper circuits — is an active research direction. These algorithms aim to demonstrate advantage before full fault-tolerance by using a small number of logical qubits with moderate error suppression.

For QAOA, the most optimistic near-term scenario is that a specific graph structure or problem class exists where quantum interference provides a structural advantage that classical algorithms cannot replicate — an advantage that appears before the circuit depth becomes intractable for NISQ hardware. No such class has been rigorously identified, but theoretical work on random quantum circuits and on average-case hardness of QAOA suggests it is not implausible.

For VQE, the most optimistic near-term scenario is a chemical system where the quantum state is genuinely hard to represent classically — strongly correlated electrons in transition metal complexes, for example — but where the quantum circuit can be kept shallow enough to run on noisy hardware with sufficient accuracy. Again, this remains a target rather than a demonstrated result.

Both algorithms are not failures — they are the correct approach for the hardware that currently exists, and they have driven enormous advances in quantum hardware benchmarking, error mitigation, and the development of the classical-quantum interface. The honest assessment is that practical quantum advantage via variational algorithms is likely to require hardware improvements — lower noise, more qubits, deeper coherent circuits — rather than solely algorithmic innovation. Whether that hardware arrives before classical algorithms close the gap on the problems QAOA and VQE target is the defining open question of the NISQ era.

Sources & Further Reading

  1. Edward Farhi, Jeffrey Goldstone, Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 (2014)
  2. Alberto Peruzzo, Jarrod McClean, et al.. A Variational Eigenvalue Solver on a Photonic Quantum Processor. Nature Communications 5, 4213 (2014)
  3. M. Cerezo, Andrew Arrasmith, et al.. Variational Quantum Algorithms. Nature Reviews Physics 3, 625; arXiv:2012.09265 (2021)
  4. Michel X. Goemans, David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM 42(6) (1995)
More in Quantum Algorithms
Tags#QAOA#VQE#variational quantum algorithms#quantum chemistry#combinatorial optimization#NISQ#quantum algorithms#Max-Cut

Discussion

← All articles