Cost Hamiltonians

In the Quantum Approximate Optimization Algorithm (QAOA), finding a good solution to a combinatorial problem requires encoding that problem's objective function as a Hamiltonian. The circuit then applies this Hamiltonian as a phase gate, so that basis states representing cheaper solutions accumulate more phase — which interference amplifies into higher probability. This lesson shows exactly how that encoding works.

From cost function to Hamiltonian

Consider the MaxCut problem: given a graph, partition its vertices into two sets so that the number of edges crossing the partition is as large as possible. Each vertex $v$ is assigned a binary variable $z_v \in \{0, 1\}$.

An edge $(u, v)$ contributes to the cut when $z_u \neq z_v$. The contribution of a single edge can be written as

$C_{uv}(z) = \frac{1 - (-1)^{z_u + z_v}}{2} = \frac{1 - (-1)^{z_u}(-1)^{z_v}}{2}.$

The Pauli $Z$ operator has eigenvalues $+1$ on $|0\rangle$ and $-1$ on $|1\rangle$, so $(-1)^{z_v}$ is exactly the eigenvalue of $Z_v$. Replacing classical bits by Pauli operators gives the quantum operator for one edge:

$H_{uv} = \frac{1}{2}(I - Z_u Z_v).$

The full cost Hamiltonian is the sum over all edges:

$H_C = \sum_{(u,v) \in E} H_{uv} = \sum_{(u,v) \in E} \frac{1}{2}(I - Z_u Z_v).$

Because $H_C$ is diagonal in the computational basis, its eigenvalues are exactly the integer cut values of each bitstring. A bitstring that cuts $k$ edges is an eigenstate of $H_C$ with eigenvalue $k$.

The phase-encoding unitary

QAOA does not apply $H_C$ as a measurement; it applies it as a time evolution with variational angle $\gamma$:

$U_C(\gamma) = e^{-i\gamma H_C}.$

Because each $H_{uv}$ commutes with every other (they share the same diagonal basis), the product factorizes edge by edge:

$U_C(\gamma) = \prod_{(u,v) \in E} e^{-i\gamma H_{uv}} = \prod_{(u,v) \in E} e^{-i\gamma(I - Z_u Z_v)/2}.$

The global phase from the identity part is unobservable, so only the $ZZ$ term matters. For one edge the essential unitary is

$e^{i\theta Z_u Z_v}, \quad \theta = \frac{\gamma}{2}.$

Circuit for $e^{i\theta Z_u Z_v}$

To implement $e^{i\theta Z_u Z_v}$ in terms of standard gates, use the identity

$Z_u Z_v = \text{CNOT}_{u \to v} \cdot (I_u \otimes Z_v) \cdot \text{CNOT}_{u \to v},$

which follows from $\text{CNOT}$ mapping $|x, y\rangle \to |x, x \oplus y\rangle$ and from how Pauli operators transform under conjugation. Inserting this decomposition yields

$e^{i\theta Z_u Z_v} = \text{CNOT}_{u \to v} \cdot R_z(-2\theta)_v \cdot \text{CNOT}_{u \to v},$

where $R_z(\phi) = e^{-i\phi Z/2}$ is the standard rotation. For a single edge with $\gamma = \pi/4$ the angle is $\theta = \pi/8$ and the $R_z$ argument is $-\pi/4$.

The three-gate sequence has depth 3 (two CNOTs and one $R_z$) and applies one edge's cost Hamiltonian exactly, without approximation.

Try it

Complete the circuit that starts in the uniform superposition $|{++}\rangle$ and applies $e^{i(\pi/8)\,Z_0 Z_1}$ — the cost unitary for a single-edge MaxCut instance with $\gamma = \pi/4$. The grader checks the full statevector, so the correct three-gate insertion is required to pass.

Sign in on the full site to ask questions and join the discussion.