QAOA: Quantum Approximate Optimization

Apply QAOA to solve a simple MaxCut problem on a graph.

QAOA: Quantum Approximate Optimization Algorithm

QAOA is a hybrid quantum-classical algorithm for combinatorial optimization. Given a cost function C(x) over binary strings x in {0,1}^n, QAOA approximates the optimal solution. You analyzed its depth cost at the end of the Quantum Algorithms track; here you build and run the full algorithm on a MaxCut instance.

The MaxCut Problem

Given a graph G=(V,E), find a partition of vertices into two sets S and V-S to maximize the number of edges between the two sets.

For a 4-node cycle graph with edges (0,1), (1,2), (2,3), (3,0):

•Optimal cut value: 4 (alternating partition: {0,2} vs {1,3})
•Optimal bitstrings: 0101 or 1010

QAOA Circuit Structure

A depth-p QAOA circuit alternates cost and mixer unitaries:

1.Initialization: H on all qubits (equal superposition)
2.Cost unitary $U_{C} (γ)$ : For each edge (u,v): CX(u,v), Rz( $2 γ$ , v), CX(u,v)
3.Mixer unitary $U_{B} (β)$ : Rx( $2 β$ , q) for each qubit q
4.Repeat steps 2-3 p times (QAOA depth p)
5.Measure all qubits

Interpreting Results

After running the QAOA circuit, the most frequent bitstrings are the algorithm's best guesses for the optimal solution. For MaxCut on a 4-cycle with pre-computed optimal angles, you should see '0101' and '1010' (the two optimal partitions) appearing most often.

The Classical Optimization Loop

The angles $γ$ and $β$ are variational parameters optimized classically:

1.Run the QAOA circuit with given ( $γ$ , $β$ )
2.Measure expectation value of the cost function
3.Update ( $γ$ , $β$ ) to increase the cost value
4.Repeat until convergence

For p=1 on MaxCut, the exact optimal angles can be computed analytically: $γ = π /8$ , $β = 3 π /8$ .

QAOA Performance Guarantees

For MaxCut on 3-regular graphs at depth p=1, QAOA achieves at least 0.6924 times the optimal cut value (a guarantee proven for that graph family; general graphs have no single p=1 constant). As p increases, the solution quality improves, approaching the optimal in the limit p -> infinity.

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.

Part of: Quantum Hardware & NISQ

Explore the physics of real quantum computers, understand noise, and learn near-term algorithms designed for today's noisy hardware.

Previous lessonVQE Under Hardware Constraints Next lessonQuantum Volume and Device Benchmarks

This lesson is part of Pro

Unlock Quantum Hardware & NISQ and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground