VQE and QAOA — near-term tasters

Shor’s, Grover’s, and the QFT are all famous, beautiful, and… mostly inapplicable to today’s hardware. Running them on problem sizes relevant to real cryptography or search needs millions of physical qubits with full error correction — devices that may not exist for a decade or more.

This is a problem. We have quantum computers now, but they’re small (hundreds of qubits), noisy (one gate in every 10³–10⁴ fails), and can only run shallow circuits before decoherence scrambles everything. If we want to do useful work on these machines, we need algorithms designed for them, not for the fault-tolerant future.

The two most promising families are variational quantum algorithms (VQAs): algorithms that combine a short, parameterized quantum circuit with a classical optimization loop. VQE and QAOA are the headline examples.

VQE: variational quantum eigensolver

Problem: Find the ground state energy of a quantum system — the lowest eigenvalue of a given Hamiltonian $H$. This is the central computational problem in quantum chemistry.

Why it matters: Ground state energies tell you molecular bonding, reaction rates, catalyst efficiency, drug binding strength. Classical algorithms for this problem (coupled cluster, DFT, etc.) either scale badly or sacrifice accuracy. A quantum computer is natively suited for representing quantum states — it’s the obvious tool.

The algorithm:

1. Pick a parameterized quantum circuit $U(\vec\theta)$ — a family of circuits with adjustable gate angles. This is called the ansatz.
2. Prepare the state $|\psi(\vec\theta)\rangle = U(\vec\theta)|0\rangle$ on the quantum computer.
3. Measure the expectation value $\langle\psi(\vec\theta)|H|\psi(\vec\theta)\rangle$ — the “energy” of the current trial state. This requires running the circuit many times with different measurements and averaging.
4. Pass the energy to a classical optimizer (Adam, SPSA, Nelder-Mead, whatever). The optimizer adjusts the parameters $\vec\theta$ to try to lower the energy.
5. Repeat. The optimizer searches for parameters that minimize the energy — and the minimum is the ground state energy by the variational principle.

The key trick: we don’t need a deep, fault-tolerant circuit. The ansatz can be shallow (low gate count) and the algorithm tolerates some noise because we’re just measuring expectation values. The classical optimizer does the heavy lifting; the quantum computer is used only to evaluate the cost function efficiently.

QAOA: quantum approximate optimization algorithm

Problem: Combinatorial optimization — find the assignment of variables that minimizes some cost function (think: MaxCut, TSP, scheduling).

Why it matters: Optimization is everywhere. If quantum algorithms could give even modest speedups on NP-hard optimization, it would be a big practical deal.

The algorithm: QAOA is structurally very similar to VQE:

1. Encode the cost function as a Hamiltonian $H_C$ whose ground state is the optimal assignment.
2. Pick a “mixer” Hamiltonian $H_M$ (typically a sum of X gates).
3. Alternate: apply $e^{-i\gamma_k H_C}$ then $e^{-i\beta_k H_M}$ for $p$ rounds, with parameters $\vec\gamma, \vec\beta$.
4. Measure the resulting state — the sample is a candidate assignment.
5. Use a classical optimizer to tune $\vec\gamma, \vec\beta$ to maximize the expected solution quality.

QAOA at $p \to \infty$ is provably optimal, but for small $p$ (which is all we can run on current hardware), its performance is problem-dependent. Some problems show QAOA advantages; others don’t.

Are they actually faster?

Honest answer: we don’t know yet. VQE and QAOA are actively researched, but there are no proven quantum advantages for practical-sized problems. Some small demonstrations show interesting behavior; some show that classical heuristics match or beat the quantum versions. The situation is evolving.

The research question is whether, with enough qubits and shallow circuits, these algorithms can beat the best classical heuristics on problems of real-world size. If yes, they’ll be the first practical quantum advantage of the NISQ (noisy intermediate-scale quantum) era. If no, we’ll need to wait for full error correction to realize quantum speedups in practice.

Either way, VQE and QAOA are the algorithms people are actually running on real quantum hardware in 2025–2026. They’re the best shot at “useful” quantum computing before full fault tolerance.

You’ve finished Module 7

That’s the full algorithms tour: toy (Deutsch-Jozsa), family resemblance (Bernstein-Vazirani, Simon’s), famous search (Grover), the Fourier engine (QFT), the famous breakthrough (Shor), and the near-term hope (VQE/QAOA). You now have a map of quantum algorithms that will let you read any paper in the field and understand the structural moves, even if you don’t follow every line of math.

Module 8 turns to the elephant in the room: noise. Every algorithm we’ve discussed assumes perfect gates. Real quantum hardware doesn’t have those. The next module is about how we fight back.