Approximation Ratios

Every approximation algorithm for a combinatorial optimization problem is judged by a single dimensionless number: the approximation ratio. This ratio measures how close the algorithm's solution comes to the best possible answer.

Definition

Let $\text{OPT}$ be the optimal value of the cost function $C$ over all $2^n$ bit strings, and let $\langle C \rangle_{\text{alg}}$ be the expected cost value produced by the algorithm (averaged over its randomness or quantum measurements). The approximation ratio is

For a maximization problem (like Max-Cut) we have $0 \le r \le 1$, with $r = 1$ meaning the algorithm always finds the optimum. A higher $r$ is better.

Why approximation ratios matter

Exact solvers for NP-hard problems require exponential time in the worst case. Approximation algorithms trade optimality for speed: they run in polynomial time but accept a solution that might be slightly worse than optimal. The approximation ratio quantifies the price of that trade.

Two landmark results frame the landscape:

• A random partition of the vertices achieves $r \ge 0.5$ for Max-Cut in expectation, since each edge is cut with probability $\frac{1}{2}$.
• The Goemans-Williamson semidefinite programming algorithm (1995) achieves $r \approx 0.878$, which is known to be nearly tight under the Unique Games Conjecture.

QAOA's approximation ratio for Max-Cut

Farhi, Goldstone, and Gutmann (2014) showed analytically that a $p = 1$ QAOA circuit with optimally chosen angles $(\gamma^*, \beta^*)$ achieves an expected cut fraction satisfying

on ring graphs (simple cycles) in the large-graph limit. This exceeds the random baseline of $0.5$ and narrows the gap toward the Goemans-Williamson bound of $0.878$. On 3-regular graphs the same analysis gives a lower bound of approximately $0.6924$, still comfortably above the random-cut baseline.

As $p \to \infty$, QAOA converges to the exact optimum: the approximation ratio approaches $1$. The open question is how deep $p$ must be to surpass classical heuristics on practically interesting instances.

Computing the ratio in practice

Suppose you run a one-layer QAOA circuit on a small Max-Cut instance, measure many times, and find that the average number of cut edges is $\langle C \rangle$. If you also know (by brute force on a small graph) that the true maximum cut has value $\text{OPT}$, then

For example, on a 4-node ring graph with $\text{OPT} = 4$ cut edges, if $p = 1$ QAOA achieves $\langle C \rangle = 3$ on average, the approximation ratio is $r = 3/4 = 0.75$.

Try it

A Max-Cut instance has an optimal cut value of $5$. QAOA with $p = 1$ finds an expected cut value of $3.75$. Return the approximation ratio as a decimal number.

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