Two algorithms, one for graphs and one for molecules: what's actually shared, and what's genuinely different?
Every algorithm this page has built so far is proven: Deutsch's, Simon's, Shor's period-finding all come with a fixed circuit and a guaranteed advantage over any classical algorithm attacking the identical problem. This section is the honest counterpart. QAOA and VQE are a completely different kind of algorithm: built for the noisy, shallow-circuit hardware that actually exists today, and carrying a different guarantee: not "this is fast," but "this can never quietly report a wrong answer as if it were right." Nobody has a proof either one beats its best classical rival on the problems people actually care about: a fact this section states as plainly as the rest of this page states its proofs.
Both algorithms belong to a family usually called variational quantum algorithms, designed on purpose for hardware too noisy and too short-lived to run the deep, fully error-corrected circuits topics 11–13 just built. The trick: keep the quantum part short (a handful of tunable gates) and push all the hard searching onto a classical optimizer sitting outside the quantum computer, the same way an engineer tunes a handful of dials on a physical instrument rather than redesigning it from scratch each time.
QAOA (the Quantum Approximate Optimization Algorithm) points that loop at a combinatorial optimization problem: encode "how good is this cut/assignment/schedule" as a Hamiltonian whose highest eigenvalue is the best possible answer (exactly the Ising-model encoding The Feasible Region's bridges section already introduces), alternate between that cost Hamiltonian and a fixed "mixer" Hamiltonian, and let the optimizer search for the angles that push the expectation value as high as it can go.
VQE (the Variational Quantum Eigensolver) points the identical loop at a completely different Hamiltonian (a real molecule's) searching for the lowest eigenvalue instead of the highest, because a molecule's ground-state energy is exactly that: the smallest possible expectation value of its Hamiltonian over any physical quantum state. The guarantee that makes this trustworthy rather than just plausible is a hundred-year-old fact from ordinary quantum mechanics, not something invented for this algorithm: the variational principle, proved below.
QAOA. For a graph problem such as Max-Cut, the cost Hamiltonian is HC = Σ(i,j)∈E ½(I − ZiZj), whose eigenvalue on a computational-basis state is exactly the number of edges that state's ±1 labelling cuts. The mixer is HM = Σi Xi. At depth p, starting from the uniform superposition |+⟩⊗n:
|γ,β⟩ = e−iβpH_Me−iγpH_C ⋯ e−iβ₁H_Me−iγ₁H_C|+⟩⊗n
and a classical optimizer searches (γ,β) to maximise ⟨γ,β|HC|γ,β⟩. Verified by exact statevector simulation on the same n=6 trap graph already verified by brute force on The Feasible Region and playable at Graph City, District 5 (edges (4,5),(3,5),(0,5),(1,3),(2,4),(0,2), brute-force max cut = 6): the best expectation value found is always sandwiched in [0, 6] at every depth, and adding layers closes the gap toward the true optimum: p=1 reaches 4.44 (74.0% of optimal), p=2 reaches 5.21 (86.9%), p=3 reaches 5.59 (93.1%). This is a real demonstration of "more layers help," on one concrete instance. It is not a claim that QAOA beats the 87.8567% unconditional classical guarantee topic 17's Goemans–Williamson bound already proves; on general instances, nobody has shown that it does (Farhi, Goldstone & Gutmann, arXiv:1411.4028, 2014; Marwaha, Quantum 5, 437 (2021)).
VQE and the variational principle. For any Hermitian H with eigenvalues λ₀≤λ₁≤…, and any normalised |ψ⟩ expanded in H's own eigenbasis as |ψ⟩=Σci|i⟩:
⟨ψ|H|ψ⟩ = Σᵢ |cᵢ|² λᵢ ≥ λ₀ Σᵢ |cᵢ|² = λ₀
: a weighted average can never fall below the smallest value being averaged, with equality only when |ψ⟩ is itself the ground state. This is why VQE's number is trustworthy even when the ansatz is a bad guess: a bad guess reports too high an energy, never too low. Verified on an illustrative 2-qubit Hamiltonian in the six-term structure a real Jordan–Wigner-mapped H₂ Hamiltonian takes (H = g₀I + g₁Z₀ + g₂Z₁ + g₃Z₀Z₁ + g₄X₀X₁ + g₅Y₀Y₁; coefficients here are illustrative, not fitted to any specific bond length): across a full 200×200 grid of the ansatz's two angles (40,000 points) not one ever produced an energy below the true ground state found by exact diagonalization, and a classical optimizer starting from 30 random points converged to the true ground energy to within 10⁻⁹.
Two live cross-links, and one honest limit shared by both QAOA is the quantum side of the exact head-to-head The Feasible Region's topic 17 already runs against Goemans–Williamson's SDP bound, and the graph verified above is the identical District 5 trap from Graph City: the same instance, checked by brute force there and by exact quantum simulation here. VQE's target (a molecule's ground-state energy) is exactly what the next topic explains how to actually reach on real chemistry, and how it connects back to phase estimation (topic 12). Neither algorithm proves a speedup. They exist because they are the best options that fit on hardware available now, not because a theorem guarantees either wins against the best classical method: the same anti-hype standard this site's AI↔quantum page applies throughout. (Quantum machine learning, the other major NISQ-era heuristic family, is covered on that page rather than repeated here.)
Check yourself
Why can VQE never report an energy below the true ground energy, even with a bad ansatz?
A weighted average can never fall below the smallest value being averaged. A bad guess reports too high an energy, never too low.