Quantum Optimization

An optimization problem asks for the best choice among finitely many options: the delivery route, the chip layout, the portfolio. Many such problems can be written as a QUBO, Quadratic Unconstrained Binary Optimization: choose bits z₀, z₁, ..., each 0 or 1, to maximize or minimize a cost function containing only single-bit and bit-pair terms. The physics-flavored twin is the Ising model, identical mathematics with ±1 'spins' instead of 0/1 bits.

The quantum pitch: map each bit to a qubit (a quantum bit whose state carries complex weights called amplitudes; squared magnitudes give outcome probabilities), turn the cost function into phase shifts, and use interference, the adding and cancelling of amplitudes, to make good bitstrings more likely to appear when you measure. Two hardware families pursue this: quantum annealers, built solely for this problem shape, and gate-based machines running algorithms such as QAOA, the Quantum Approximate Optimization Algorithm. The differences are covered in annealing vs gate-based. Applying the chapter 1 filter immediately: the speedup here is heuristic, question 1 already fails to give a proof, so the evidence must carry everything. Let us look at the evidence honestly, starting from a problem small enough to solve by hand.

Max-cut: split a graph's nodes into two groups so that as many edges as possible run between the groups. Our graph: three nodes 0, 1, 2 in a line, with two edges (0,1) and (1,2). Assign bit z_i = 0 or 1 to say which group node i joins. An edge is 'cut' when its endpoints differ. The cost to maximize is C(z) = [z₀ ≠ z₁] + [z₁ ≠ z₂], where each square bracket counts 1 when the statement inside it is true and 0 when it is false. As a QUBO polynomial each term is z_i + z_j − 2z_iz_j; check for z₀=0, z₁=1: 0 + 1 − 0 = 1, correct.

Enumerate all 2³ = 8 assignments. We write bitstrings in this site's display convention, z₂z₁z₀ with qubit 2 leftmost:

• 000: no edge cut, C = 0
• 001: edge (0,1) cut, C = 1
• 010: both edges cut, C = 2
• 011: edge (1,2) cut, C = 1
• 100: edge (1,2) cut, C = 1
• 101: both edges cut, C = 2
• 110: edge (0,1) cut, C = 1
• 111: no edge cut, C = 0

The optima are 010 and 101: node 1 alone on one side, nodes 0 and 2 on the other, in either labeling. Keep this table; every prediction below refers to it. Note the brute-force count doubles per added node; at 50 nodes it is the same 2⁵⁰ ≈ 10¹⁵ wall we met in chapter 2, which is why heuristics, classical and quantum, exist at all.

QAOA with one layer does three things:

1. Superpose everything. An H gate on each qubit creates an equal superposition of all 8 bitstrings, amplitude 1/√8 each.
2. Phase by cost. For each edge (i,j), the block CX, RZ, CX multiplies each bitstring's amplitude by a phase (a rotation of the complex amplitude that leaves probabilities alone) that depends on whether that edge is cut. With our chosen angle, each string picks up the phase i^C(z), where i is the imaginary unit from the amplitude arithmetic, so each unit of cost rotates the string's amplitude a quarter turn in the complex plane: strings are marked by their cost, invisibly to any immediate measurement. The two-qubit CX (controlled-NOT) is explained in CNOT and controlled operations and two-qubit gates.
3. Mix to convert phase into probability. An RX rotation on every qubit makes differently-phased paths land on the same bitstrings and interfere, exactly the mechanism from interference.

We pick both angles to be π/4 radians (cost blocks use RZ(π/2), mixer uses RX(π/2); by the standard convention the gate's parameter is twice the algorithm's angle, which is why π/4 appears as π/2 in the gate list), chosen because the resulting amplitudes can be traced exactly by hand. In production QAOA a classical optimizer tunes these angles in a feedback loop; we are deliberately running one fixed, analyzable setting.

Compare the run's exact distribution against uniform random guessing, arithmetic in full:

• Probability of sampling an optimal cut. QAOA run: P(010) + P(101) = 1/4 + 1/4 = 0.50. Random guessing: 2 optima out of 8 strings = 2/8 = 0.25. A genuine 2× improvement.
• Expected cut value. QAOA run: 0.25×0 + 0.25×2 + 0.25×2 + 0.25×0 = 1.00. Random guessing: (2×0 + 4×1 + 2×2)/8 = 8/8 = 1.00. Identical.

Both numbers are true simultaneously: at these fixed angles, QAOA doubled the chance of hitting an optimum, by suppressing the mediocre strings, while also doubling the chance of the worst strings, leaving the average unchanged. This is the honest texture of heuristic algorithms: improvements are real but partial, parameter-dependent, and problem-dependent. Production QAOA spends most of its effort in the classical tuning loop searching for better angles, and for small instances that loop costs more than solving the problem classically outright.

Using this site's classifications:

• Proved theory: none, in the sense that matters. There is no proof that QAOA or quantum annealing beats the best classical algorithms on any natural optimization problem class.
• Hardware demonstrated: QAOA and annealing runs on hundreds to thousands of variables exist. Published head-to-head comparisons at matched effort have so far shown classical heuristics equal or better on problems of practical shape.
• The moving baseline bites hard here (filter question 5): simulated annealing, local search, and industrial branch-and-bound solvers are extraordinarily strong, run on cheap hardware, and improve every year. Several early annealing 'speedup' claims dissolved when the classical baseline was upgraded.
• Roadmap claim: quantum advantage on real logistics or finance problems. No demonstrated instance exists as of this writing.

Track specific claims with sources on the optimization reality page. When you read an optimization case study, ask chapter 1's questions, especially: which classical baseline, at what tuning effort, and who chose the benchmark instances?

Our 12-gate circuit assumed adjacent qubits can always interact. On real gate-based devices, connectivity, which qubit pairs can execute a two-qubit gate directly, is limited, and routing around it inserts SWAP gates that lengthen circuits (see swap insertion and connectivity costs). Dense optimization problems, where every variable interacts with every other, are the worst case for sparse-connectivity chips: gate counts grow quickly, and with them the error budget from chapter 1. At an archetype 0.5% two-qubit error, even a few hundred entangling gates leaves most shots corrupted, which flattens the carefully engineered distribution back toward uniform, precisely the failure your try-this just simulated by deleting the mixer. Compare real connectivity and fidelity figures across devices at hardware compare; annealers are listed separately on the QPU pages because gate-level metrics do not apply to them.