Quantum Optimization

Quantum optimization turns a cost into qubit energies. Then it uses interference to make low-cost answers more likely to show up. There is no proof it beats normal methods, and the evidence so far is heuristic (it sometimes works, with no guarantee). This chapter works one max-cut problem fully by hand. It runs a real QAOA circuit on it. Then it shows exactly what the quantum part does and does not buy you.

What does it mean to make optimization quantum?

An optimization problem asks for the best choice among a limited set of options. Think of the best delivery route, the best chip layout, or the best mix of investments. Many such problems can be written as a QUBO, short for Quadratic Unconstrained Binary Optimization. You choose bits z₀, z₁, ..., each 0 or 1. The goal is to make a cost as big or as small as possible. The cost only contains terms for single bits and for pairs of bits. Its physics twin is the Ising model. It is the same math, but with ±1 "spins" instead of 0/1 bits.

The quantum pitch goes like this:

Map each bit to a qubit. A qubit's state carries weights called amplitudes. Squared, they give the chance of each result.
Turn the cost into phase shifts.
Use interference — amplitudes adding up or cancelling out — to make good bitstrings more likely when you measure.

Two kinds of hardware chase this. Quantum annealers are built only for this problem shape. Gate-based machines run algorithms such as QAOA, the Quantum Approximate Optimization Algorithm. The differences are covered in annealing vs gate-based.

Now apply the chapter 1 filter right away. The speedup here is heuristic. Question 1 already fails to find a proof. So the evidence must carry everything. Let's look at the evidence honestly, starting with a problem small enough to solve by hand.