QAOA: the 0.6924 MaxCut ratio and what it does not beat

Definition

The quantum approximate optimization algorithm, QAOA, looks for good solutions of a combinatorial optimization problem by applying a short parameterized circuit and measuring bit strings. Farhi, Goldstone, and Gutmann introduced it in 2014. The circuit is indexed by a positive integer p, the number of layers. Each layer applies a diagonal unitary built from the cost function, then a mixer unitary that flips bits. A classical optimizer chooses the 2p angles. The quantum computer prepares the state and returns samples.

For fixed p the circuit is local: its gates are no more nonlocal than the clauses of the objective. The paper's analyzed example is MaxCut on regular graphs.

Intuition

Encode the objective as a Hamiltonian that is diagonal in the computational basis, so an eigenstate that is a bit string has the cost of that string as its energy. The mixer is usually a sum of single-qubit X operators, which generates transitions between strings. Alternating the two is an ansatz: a family of states indexed by the angles, not a search over every string.

At small p the state only "sees" a bounded neighborhood of each vertex, which is why the p = 1 MaxCut calculation on a 3-regular graph reduces to a small classical optimization over subgraphs. At large p the same alternation can be read as a coarse Trotter step of an adiabatic path from the mixer to the cost Hamiltonian. The paper uses that picture to explain why the approximation should improve as p grows. Growth in p is growth in depth. The improvement is not free, and it is not a polynomial-time claim for arbitrary p.

This is a variational quantum algorithm in the same broad sense as VQE: a quantum preparation, a classical parameter update, and a measurement that returns the objective. The cost function is a combinatorial objective rather than a molecular energy.

Complexity

The proved statement to quote is narrow, and it is the one the paper emphasizes.

For MaxCut on any connected 3-regular graph, QAOA at p = 1 produces a cut whose expected size is at least 0.6924 times the optimal cut. Farhi, Goldstone, and Gutmann obtain that number by minimizing a small trigonometric expression over the local subgraphs that can appear, and they note that the worst case is a tree-like neighborhood. They also write that this p = 1 result is not as good as classical algorithms already known for the same problem.

The classical comparison they are pointing at sits next to an older and more famous guarantee. Goemans and Williamson give a randomized polynomial-time algorithm for MaxCut, via a semidefinite program, with expected approximation ratio at least 0.878. That guarantee is not restricted to 3-regular graphs. A 0.6924 ratio on one regular case is a theorem about QAOA. It is a weaker theorem than the classical algorithm that predates it.

For fixed p, independent of the number of vertices, the paper uses classical preprocessing to choose angles, because the relevant expectation depends on a bounded-size neighborhood. Circuit depth grows linearly with p and, in the worst case they state, with the number of constraints. When p has to grow with the instance, that fixed-p preprocessing no longer supplies a polynomial-time parameter choice, and the adiabatic reading does not by itself cap the depth.

Grover's algorithm is the other quantum approach people reach for on hard search problems. It gives a quadratic reduction in unstructured queries and a matching lower bound. QAOA is not that algorithm. It does not come with an NP-hardness escape, and the 0.6924 ratio is an approximation guarantee, not a query lower bound.

Hadfield, Wang, O'Gorman, Rieffel, Venturelli, and Biswas extend the framework from cost and mixer Hamiltonians to more general alternating unitaries, under the name quantum alternating operator ansatz. The point of that paper is constrained problems, where the mixer should move inside a feasible subspace. It is a design framework. It does not replace the 0.6924 calculation with a better worst-case ratio.

Applications and limits

MaxCut is the problem with a number attached. Other combinatorial problems can be written with diagonal cost Hamiltonians and a mixer, and the Hadfield et al. framework is the reference for doing that carefully when constraints must stay satisfied. Writing the problem down is the start of an experiment or a proof. It is not evidence that the quantum circuit beats a classical solver.

The angles are part of the algorithm's cost. For the regular MaxCut cases Farhi, Goldstone, and Gutmann analyze at fixed p, the angles come from a classical calculation on a small graph. For a generic cost function they are the output of a heuristic search, with the same kind of optimizer trouble any non-convex landscape can present. Depth, noise, and the quality of those angles all sit between the ansatz and a sample you would trust over a classical heuristic.

Reading the source

The 2014 preprint is the source of the algorithm and of the 0.6924 ratio. Read the MaxCut section before quoting the constant, including the sentence that compares it with classical algorithms. Goemans and Williamson is the classical approximation algorithm to put beside that constant. Hadfield et al. is the reference when the mixer is no longer a transverse field, especially for constrained problems.