Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 39 ยท Applications and Outlook

QAOA and Quantum Optimization (MaxCut)

Learn the Quantum Approximate Optimization Algorithm: encode MaxCut as a cost Hamiltonian, build the QAOA circuit and optimize its angles in NumPy.

Many real problems ask for the best choice among exponentially many: routing deliveries, scheduling shifts, assigning frequencies, packing containers, selecting a portfolio. These are combinatorial optimization problems, and many are NP-hard. A quantum computer is not known to solve NP-hard problems efficiently, but it may offer better approximations or speed-ups on some instances. The Quantum Approximate Optimization Algorithm (QAOA), proposed by Farhi, Goldstone and Gutmann in 2014, is the standard gate-based heuristic for this.

QAOA is a close cousin of VQE: a shallow parameterized circuit, a cost you measure, and a classical optimizer for the parameters. The difference is that its circuit structure comes from the problem.

Step 1: write the problem as a cost function over bits

Take MaxCut: given a graph, color each vertex 0 or 1 so that as many edges as possible connect different colors. For a bit string z, the number of cut edges is

Text
C(z) = sum over edges (i, j) of  (1 - s_i * s_j) / 2        with s_i = +1 if z_i = 0 else -1

Any problem of this quadratic unconstrained binary (QUBO) form, or equivalently an Ising model, becomes a diagonal operator on qubits: the cost Hamiltonian H_C has eigenvalue C(z) on basis state |z>. Maximizing the cut means finding the highest-energy eigenstate (or minimizing -C).

Step 2: the QAOA circuit

Start in the equal superposition |+>^n. Then repeat p layers, each with two parameters (gamma_k, beta_k):

  1. Cost layer exp(-i * gamma * H_C): adds the phase e^(-i*gamma*C(z)) to every basis state. For MaxCut this is a ZZ rotation on every edge, built from two CNOTs and an RZ.
  2. Mixer layer exp(-i * beta * sum X_j): an RX(2*beta) on every qubit, which moves amplitude between neighboring bit strings.

Finally measure and keep the best bit string you see. The parameters are tuned so that the final state favors high-cost strings. With p -> infinity QAOA can approach the exact optimum (it contains a discretized version of quantum annealing); with small p it is a heuristic with a guaranteed minimum quality only for a few problems (for 3-regular MaxCut, p = 1 guarantees an approximation ratio of 0.6924, while the classical Goemans-Williamson algorithm gives 0.878).

flowchart LR
    A["|+>^n"] --> B["Cost layer: phase by C(z)"]
    B --> C["Mixer layer: RX(2 beta)"]
    C -->|"p layers"| B
    C --> D["Measure: sample bit strings"]
    D --> E["Optimizer updates gamma, beta"]
    E --> B

QAOA alternates problem-dependent phases and mixing; a classical loop tunes the angles.

Build it for a small graph

The graph below has 6 vertices: a hexagon plus one diagonal. The cost values for all 64 bit strings are computed classically (that is fine for a simulator; on hardware only the circuit exists). The cost layer multiplies each amplitude by a phase and the mixer is a tensor product of single-qubit rotations.

Python QAOA p=1 and p=2 for MaxCut on 6 vertices

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see that p = 1 already beats the random average and p = 2 improves further, with a rising probability of sampling an optimal cut. The best strings come in complementary pairs (flipping all bits gives the same cut), so the probability splits between them.

From MaxCut to other problems

The recipe is general:

  1. Write the objective and constraints as a QUBO: minimize x^T Q x with x in {0,1}^n. Constraints become penalty terms.
  2. Substitute x_i = (1 - s_i) / 2 to obtain an Ising Hamiltonian, then s_i -> Z_i.
  3. Build the cost layer from Z, ZZ rotations; choose a mixer (the plain X mixer for unconstrained problems; special mixers that stay within the feasible set for constrained ones such as Traveling Salesman).
Python Turn a small problem into a QUBO and check it by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sum is 26, so a perfect split of 13 and 13 exists (difference 0). The same J matrix would define the ZZ couplings in a QAOA cost layer.

Reality check

  • No proven general advantage yet. Optimized classical heuristics (simulated annealing, tabu search, branch and bound solvers, Goemans-Williamson) are strong. Studies of QAOA suggest that a speed-up might need large p, which means deep circuits.
  • Parameter landscape. Good angles for one graph often transfer to similar graphs, so you can train on small instances and reuse parameters.
  • Hardware today. QAOA runs on tens to over a hundred qubits, but noise washes out the advantage of deeper layers.
  • Alternatives. Quantum annealers (D-Wave) solve Ising problems physically and have thousands of qubits; Grover-style methods give a provable quadratic speed-up for unstructured search (Grover's algorithm); warm-start and "Quantum Imaginary Time" variants exist.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the two parts of one QAOA layer?

    exp(-igammaH_C) followed by exp(-ibetasum X).
  2. 2. What does the cost Hamiltonian look like for MaxCut?

    Each edge contributes (1 - Z_i Z_j)/2, which is the indicator that the endpoints differ.
  3. 3. What is QAOA's initial state?

    It is the ground state of the mixer, an unbiased superposition over all candidate solutions.
  4. 4. What does QUBO stand for?

    Problems of this form map directly to Ising Hamiltonians for QAOA or annealers.
  5. 5. Which statement about QAOA today is accurate?

    Strong classical competitors exist, and noise limits circuit depth.

Summary

  • QAOA solves combinatorial problems by alternating a problem-specific phase layer and a mixing layer, with 2p classically tuned angles.
  • MaxCut and other problems map to QUBO/Ising form, which becomes a sum of Z and ZZ terms.
  • Small instances can be simulated exactly with NumPy; larger ones need hardware, where noise limits depth.
  • A proven practical advantage is still an open research question.

Next: Quantum Machine Learning