Combinatorial Optimization Problems

Many of the hardest problems in computer science share the same structure: you have a set of discrete choices, a cost function over those choices, and you want the assignment that makes the cost as large (or as small) as possible. These are called combinatorial optimization problems — "combinatorial" because the search space is built from combinations of discrete variables.

The difficulty of exhaustive search

Suppose you have $n$ binary variables $x_1, x_2, \ldots, x_n$ where each $x_i \in \{0, 1\}$ . The number of possible assignments grows as $2^n$ . For $n = 10$ that is only 1024 cases, but for $n = 100$ it reaches $2^{100} \approx 10^{30}$ — far beyond any classical computer's ability to enumerate.

Many natural combinatorial problems are NP-hard: no polynomial-time classical algorithm is known, and most complexity theorists believe none exists. Finding good approximate solutions efficiently is therefore a major open problem, and it is one of the most promising near-term applications of quantum computing.

Graph problems as a unifying language

Graphs provide a compact, visual language for combinatorial problems. A graph $G = (V, E)$ consists of a set of vertices $V$ and edges $E \subseteq V \times V$ . Vertices can represent cities, logic variables, financial assets, or protein residues; edges represent connections, conflicts, or interactions between them.

Assigning a value to each vertex — a colour, a partition label, a spin — while optimizing some score over the edges is the common template behind dozens of NP-hard problems.

Max-Cut: the canonical example

Given an undirected graph $G = (V, E)$ , a cut is a partition of $V$ into two disjoint sets $S$ and $\bar{S} = V \setminus S$ . An edge $(u, v)$ is cut if $u$ and $v$ land in different sets. Max-Cut asks: which partition maximises the number of cut edges?

Encoding with bits

Label each vertex with a bit: $z_i = 0$ if vertex $i$ is in $S$ , and $z_i = 1$ if it is in $\bar{S}$ . An edge $(i, j)$ is cut when $z_i \neq z_j$ , which we can write using the XOR:

\text{cut}(i,j) = z_i \oplus z_j = \frac{1 - (-1)^{z_i + z_j}}{2}.

The total number of cut edges is

C(\mathbf{z}) = \sum_{(i,j) \in E} \frac{1 - (-1)^{z_i + z_j}}{2}.

Maximising $C(\mathbf{z})$ over all $2^{|V|}$ bit strings is the Max-Cut objective.

A small example

Consider a triangle graph: vertices $\{1, 2, 3\}$ with edges $\{(1,2),(2,3),(1,3)\}$ . The three possible partition sizes (up to symmetry) give the following cut counts:

| Partition $S$ | Cut edges | |---|---| | $\{1\}$ vs $\{2,3\}$ | 2 | | $\{2\}$ vs $\{1,3\}$ | 2 | | $\{1,2\}$ vs $\{3\}$ | 2 | | $\{1,2,3\}$ vs $\{\}$ | 0 |

The maximum cut has value 2 (any single vertex against the other two). Note that a perfect 3-cut does not exist for a triangle — this is why Max-Cut is hard in general: constraints between variables can be contradictory, and no assignment satisfies all of them.

Why this matters for QAOA

The Quantum Approximate Optimization Algorithm (QAOA), introduced by Farhi, Goldstone, and Gutmann in 2014, targets exactly this class of problem. The key insight is that each bit variable $z_i \in \{0,1\}$ maps to a qubit: $|0\rangle$ represents being in set $S$ and $|1\rangle$ represents being in $\bar{S}$ . The cost function $C(\mathbf{z})$ then lifts to a quantum operator — a cost Hamiltonian $H_C$ — whose eigenvalues are exactly the values of $C$ for each bitstring.

Finding the maximum cut becomes finding the ground state of $-H_C$ (i.e., the state with the largest eigenvalue of $H_C$ ). QAOA constructs a parameterised quantum state that interpolates between an equal superposition over all bitstrings and the optimal solution, using two alternating unitaries:

$e^{-i\gamma H_C}$ — the cost unitary, which encodes preferences for high-cut assignments.
$e^{-i\beta H_M}$ — the mixing unitary, which explores the space of solutions.

We will construct both of these explicitly in the next lessons.