QAOA Revisited: Variational Optimization

Solve combinatorial optimization problems with quantum circuits.

QAOA Revisited: Variational Optimization

QAOA (Quantum Approximate Optimization Algorithm) is one of the most studied near-term quantum algorithms. You built it end to end in the Hardware & NISQ track; this lesson revisits it from the machine learning side, as a member of the same variational family as the models in this track. It tackles combinatorial optimization problems that are hard for classical computers, with the promise of quantum advantage as hardware scales.

The MaxCut Problem

MaxCut is a canonical NP-hard combinatorial optimization problem. Given a graph G = (V, E), partition the vertices into two sets (S and V-S) to maximize the number of edges between the two sets (edges that are "cut").

For example, a 4-cycle graph 0-1-2-3-0 has 4 edges. The optimal MaxCut is 4 (alternating partition: {0,2} vs {1,3}).

The QAOA Approach

QAOA encodes the problem into two Hamiltonians:

Cost Hamiltonian $H_{C}$ : Measures how well the current state satisfies the optimization objective. For MaxCut, an edge $(u, v)$ contributes $(1 - Z_{u} Z_{v}) /2$ to the cost.

Mixer Hamiltonian $H_{B}$ : Drives quantum transitions between states. Typically $H_{B} = \sum_{i} X_{i}$ .

The QAOA circuit alternates p layers of:

1.Cost unitary: $U_{C} (γ) = exp (- iγ H_{C})$
2.Mixer unitary: $U_{B} (β) = exp (- i β H_{B})$

For MaxCut, each edge $(u, v)$ contributes: CNOT $(u, v)$ , $R_{z} (2 γ, v)$ , CNOT $(u, v)$ . The mixer applies $R_{x} (2 β)$ to each qubit.

The Circuit Structure

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

1.Apply H to all qubits to create equal superposition
2.Cost layer: For each edge $(u, v)$ : cx(u,v), rz( $2 γ$ , v), cx(u,v)
3.Mixer layer: rx( $2 β$ , q) for each qubit q
4.Measure all qubits

The angles $γ$ and $β$ are the variational parameters, optimized classically to maximize the expected cut value.

Classical Optimization Loop

After measuring the circuit, compute the expected cut value as a function of $(γ, β)$ . Classically optimize these two parameters:

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 Machine Learning

Apply quantum computing to machine learning with variational circuits and optimization.

Previous lessonVariational Quantum Eigensolver Next lessonBarren Plateaus

This lesson is part of Pro

Unlock Quantum Machine Learning 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