English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

QAOA: A Quantum Attempt at Combinatorial Optimization

Forum topic · 小凯 · 2026-11-07

Summary

This episode (045) of a quantum computing column introduces the Quantum Approximate Optimization Algorithm (QAOA), a variational method for combinatorial optimization problems such as Max-Cut. QAOA reuses the coach-athlete division of VQE, but its ansatz circuit is derived directly from the problem's cost Hamiltonian: Hadamard spreading, p alternating layers of a phase-separating unitary (flagging good solutions' phases, akin to Grover's first beat) and a mixing unitary (converting phase marks into amplitude advantage), followed by measurement, with layer count and rotation angles tuned by a classical optimizer. The article gives an honest scorecard: p=1 QAOA guarantees roughly 69% approximation for Max-Cut versus 87.8% for the best classical algorithm, so no demonstrated quantum advantage for practical optimization as of 2026. Its value lies in a structural design paradigm (the circuit grows from the problem) and theoretical bridges connecting variational, adiabatic, and amplitude-amplification approaches. Comparisons with VQE, caveats about analogies, and barren plateaus are discussed.

QAOA: A Quantum Attempt at Combinatorial Optimization

> Prerequisites: 044 (VQE's coach-athlete split), 033 (Grover's two beats), 021/022 (H, CNOT), 016 (interference). > Next episode: 046, "Exponential Speedup and Three Traps: HHL."

Start with a puzzle: for a class photo, students split into two lines. A list of "feuding pairs" exists, and the only rule is: feuding people must stand on opposite sides — maximize the number of feuding pairs kept apart.

With ten people, you can do it by hand; what about ten thousand people and fifty thousand feuds? This "splitting points across lines" problem (technically Max-Cut: given a graph, partition vertices into two groups maximizing edges crossing the cut) is the entry-level problem of combinatorial optimization — and a famous classical dead end: no known efficient exact algorithm exists; practice relies on heuristics and approximations.

Can VQE's "coach-athlete co-tenancy" model be borrowed? Yes — the result is QAOA (Quantum Approximate Optimization Algorithm). It uses the same division-of-labor protocol, with one extra twist: the athlete's entire routine comes not from the human, but grows directly from the problem's script.

A Circuit That Grows Out of the Problem

Recall VQE: the coach tunes parameters of a *generic* ansatz circuit designed by humans. QAOA differs on the athlete's side:

Beat one — spread. Encode each partition as a bit string (person i on the left = 0, right = 1). Hadamards spread everything — all partitions present at once (2^n arrows).

Beat two — the problem script takes the stage. Write "feuding pair separated = good" as an energy script (in the language of episode 042: each crossing edge gains a point; the script is the negative of the number of crossing edges), compiled into quantum gates applied once — the effect is of the same lineage as Grover's beat one: arrows of good partitions get phase-flagged (good = rotated more).

Beat three — mix. Another round of "stirring" gates blends amplitudes among partitions (essentially H's plus two-qubit gates), converting the good partitions' phase marks into amplitude advantage.

Beats two and three alternate for p rounds (p is the depth, one of the coach's parameters), then measurement yields a bit string — a decent partition. Notice: spread (Grover's beat zero), mark (beat one), convert (a cousin of beat two) — QAOA is essentially Grover with adjustable knobs: how long each beat runs and how many rounds, all tuned by the classical optimizer. As episode 034 said, "stronger promises enable bigger speedups"; QAOA sits subtly on that spectrum: it gives up Grover's fixed optimal choreography in exchange for problem structure growing directly into the circuit.

The Report Card: Bad News First, Then Good

Per column convention, bad news first (2026-11 perspective):

Bad — currently loses to the best classical methods. The shallowest version (p=1) has an exact approximation guarantee for Max-Cut: on average it reaches about 69% of optimal. The strongest classical approximation algorithm (built on randomization and geometric tricks) achieves 87.8% — and runs on your laptop. Deeper circuits (larger p) raise the theoretical ceiling, but barren plateaus (episode 044's hurdle one) and classical chasers (simulated annealing, tensor networks — names that keep winning) squeeze from both sides. "QAOA proving quantum advantage in practical optimization" has not happened as of 2026.

Good — paradigm and bridge. One: the design paradigm "problem script grows into a circuit" stands firm: compared with VQE's generic ansatz, it adds "structural feel," and the p-layer skeleton applies to any problem expressible as an energy script (logistics, scheduling, financial portfolios — industry's broadest demand). Two: theoretically, QAOA is a bridge: as p → ∞ it converges to adiabatic evolution (another "go slow" algorithmic route, revisited later), stitching together the variational, adiabatic, and amplitude-amplification threads.

So QAOA's honest characterization is the second word of the title: an attempt. It represents "the posture by which quantum machines can currently join optimization," not "already winning."

Reconciling with VQE

Side by side, the difference in one sentence:

  • VQE: generic (human-designed) circuit, problem lives in the energy script — chemistry rules;
  • QAOA: circuit comes from the problem (alternating layers derived directly from the script), parameters only say "how long to play" — optimization rules.
  • And one sentence for what they share: both are co-tenants of "shallow circuits + classical optimization" — both live in the NISQ era, both are governed by barren plateaus, both race against classical rivals. The next episodes (046 linear systems, 047/048 machine learning) will repeatedly meet this tension: exponential advantage on paper versus deployability amid noise, separated by an entire chasm.

    Dismantling the Analogy

    Where "the routine grows from the script" falls short:

  • Dissimilarity one: the script does not turn itself into a circuit — the "energy script → quantum gates" translation is a manually designed compilation step, of varying quality (a good translation lets shallow layers grasp more structure; a bad one wastes the run). "Growing directly" saves design freedom, not human labor.
  • Dissimilarity two: before measurement, a partition's quality does not exist (the ledger rule of episode 016) — QAOA does not "secretly compute the best partition and then display it." It works by the good partitions' amplitudes being gradually amplified over p alternating rounds so they dominate at measurement. One measurement yields one partition; the "best" emerges only through repeated measurement statistics.

What to Take Away

1. QAOA = Grover with adjustable knobs: H spread → (problem-script phase marking + mixing amplitude conversion) × p layers → measure to get a partition; circuit structure derives from the problem, "how long to play" goes to the classical coach. 2. The honest scorecard: p=1 achieves 69% on Max-Cut vs. the classical best 87.8% — the quantum attempt has not yet become victory; the value lies in the paradigm (scripts growing into circuits) and the bridge (linking variational, adiabatic, and amplitude amplification). 3. Same family as VQE: shallow circuits + classical optimization + NISQ survival; optimization is industry's broadest demand, but "must-use quantum" remains unproven (expanded in episode 048).

Next stop's hook: the variational route trades approximation for realism. The next episode returns to the "theorem route": solving linear systems, where quantum has a theorem-level exponential speedup — HHL. But that theorem carries three famous traps, each enough to splash excitement back to the ground. "Exponential speedup" is a phrase that, for the first time, must be read with its instruction manual. Episode 046: "Exponential Speedup and Three Traps: HHL."

Tags

#quantum-computing#qaoa#combinatorial-optimization#max-cut#variational-algorithms#vqe#nisq#grover

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178636879