QAOA MaxCut - Farhi, Goldstone, Gutmann (2014)

Overview

Faithful reproduction of the paper that introduced QAOA — the Quantum Approximate Optimization Algorithm, one of the most influential quantum algorithms for combinatorial optimization. This circuit implements QAOA applied to the MaxCut problem on small graphs, demonstrating how approximation quality improves with increasing circuit depth p.

Paper Context

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann introduced QAOA in November 2014 as a quantum algorithm designed for combinatorial optimization on near-term quantum devices. Unlike algorithms requiring fault-tolerant hardware (e.g., Shor's, Grover's), QAOA was explicitly designed as a shallow-circuit variational algorithm — making it one of the earliest proposals in the now-thriving field of variational quantum algorithms (VQAs).

The paper proved that even at minimal depth (p=1), QAOA achieves a guaranteed worst-case approximation ratio for MaxCut on bounded-degree graphs. This theoretical result established QAOA as more than a heuristic: it provides provable performance bounds that improve with depth, interpolating between a simple quantum heuristic and an exact quantum adiabatic algorithm.

The MaxCut Problem

Given an undirected graph G = (V, E), the MaxCut problem asks for a partition of the vertex set V into two disjoint subsets S and V\S that maximizes the number of edges crossing the partition. MaxCut is:

• NP-hard (Karp, 1972) — no known polynomial-time exact algorithm
• APX-hard — no polynomial-time approximation scheme (PTAS) exists unless P = NP
• The best classical polynomial-time algorithm (Goemans-Williamson, 1995) achieves ratio ~0.878

Example: Triangle Graph (K3)

CODECopy
    0
   / \
  1---2

Max cut = 2 (any 2-1 partition achieves this)

Example: Square Graph (C4)

CODECopy
  0---1
  |   |
  3---2

Max cut = 4 (alternating partition: {0,2} vs {1,3})

The QAOA Ansatz

The algorithm prepares a parametrized quantum state by alternating two unitaries p times:

|psi(gamma, beta)> = U_B(beta_p) U_C(gamma_p) ... U_B(beta_1) U_C(gamma_1) |+>^n

Cost Unitary U_C(gamma)

Encodes the MaxCut objective function into quantum phases:

CODECopy
C = sum_{(i,j) in E} (1 - Z_i Z_j) / 2

U_C(gamma) = exp(-i * gamma * C)
            = prod_{(i,j) in E} exp(-i * gamma * (1 - Z_i Z_j) / 2)

Each edge contributes a ZZ-interaction gate with angle proportional to gamma.

Mixer Unitary U_B(beta)

Drives transitions between computational basis states:

CODECopy
B = sum_i X_i

U_B(beta) = exp(-i * beta * B) = prod_i RX(2*beta)

Circuit Diagram (p=1, triangle graph)

CODECopy
         ┌───┐  ┌──────────┐                          ┌────────┐
  q_0:   ┤ H ├──┤ ZZ(g/pi) ├──ZZ(g/pi)───────────────┤ RX(2b) ├──
         ├───┤  └────┬─────┘  ┌──────────┐            ├────────┤
  q_1:   ┤ H ├───────┘────────┤ ZZ(g/pi) ├────────────┤ RX(2b) ├──
         ├───┤                 └────┬─────┘            ├────────┤
  q_2:   ┤ H ├──────────ZZ(g/pi)───┘──────────────────┤ RX(2b) ├──
         └───┘                                         └────────┘
                   ←── Cost unitary ──→  ←── Mixer ──→

Key Results from the Paper

Approximation Ratio by Depth

For 3-regular graphs, the paper establishes:

Theoretical Bounds

• Farhi et al. p=1 bound: For any graph, QAOA at p=1 cuts at least a (0.6924) fraction of the maximum cut on 3-regular graphs.
• Monotonicity: The expected cut value is non-decreasing in p — adding layers never hurts.
• Goemans-Williamson comparison: The classical SDP-based GW algorithm achieves ~0.878, establishing that moderate-depth QAOA is needed to compete classically.
• Guerreschi & Matsuura (2019): Demonstrated that QAOA requires hundreds of qubits to outperform GW on random 3-regular graphs, providing practical crossover estimates.

Prerequisites

Before studying this advanced research reproduction, ensure familiarity with:

• QAOA fundamentals: See QAOA MaxCut (intermediate) for the introductory version
• Variational circuits: Understanding of parametrized quantum circuits and hybrid classical-quantum optimization loops
• Graph theory basics: Vertices, edges, partitions, NP-hardness

Running the Circuit

Basic Usage

PYTHONCopy
from circuit import run_circuit

# Test on triangle graph with QAOA depths 1, 2, 3
result = run_circuit(
    graph_type='triangle',  # or 'square', 'butterfly'
    p_values=[1, 2, 3],
    n_iter=30
)

for p, data in result['p_analysis'].items():
    print(f"p={p}: ratio = {data['approximation_ratio']:.3f}")

Verification

PYTHONCopy
from circuit import verify_reproduction

verification = verify_reproduction()
for check in verification['checks']:
    status = "PASS" if check['passed'] else "FAIL"
    print(f"[{status}] {check['name']}: {check['actual']}")

QubitHub CLI

BASHCopy
qubithub execute qaoa-maxcut-farhi --params '{"graph_type": "square", "p_values": [1, 2]}'

Available Test Graphs

Implementation Notes

Cost Hamiltonian Encoding

The MaxCut cost function in the Pauli-Z basis:

C = sum_{(i,j) in E} (1 - Z_i Z_j) / 2

Each edge contributes a ZZ-interaction. The constant term (1/2 per edge) shifts the energy but does not affect the optimization landscape.

Parameter Optimization Strategy

The parameter symmetries gamma -> gamma + 2*pi and beta -> beta + pi reduce the search space. For production use, gradient-based optimizers (COBYLA, L-BFGS-B) or parameter-transfer strategies (Zhou et al., 2020) are recommended for p > 1.

Cirq-Specific Details

• ZZPowGate: Cirq's ZZPowGate(exponent=t) implements exp(i * pi * t * Z Z). We set t = gamma / pi to encode exp(i * gamma * Z Z).
• RX gate: cirq.rx(theta) implements exp(-i * theta/2 * X). Setting theta = 2*beta gives the desired exp(-i * beta * X).

Verification Checks

The verify_reproduction() function runs four automated checks:

Historical Significance

This 2014 paper is a cornerstone of near-term quantum computing:

1. Introduced QAOA as a general-purpose quantum optimization framework, applicable to any combinatorial problem encodable as an Ising Hamiltonian
2. Proved approximation bounds — the first provable performance guarantee for a variational quantum algorithm
3. Established the depth-quality tradeoff — more layers monotonically improve the approximation ratio, interpolating to the exact quantum adiabatic solution
4. Spawned a research subfield — QAOA variants include QAOA+ (Hadfield et al., 2019), ADAPT-QAOA (Zhu et al., 2022), Recursive QAOA (Bravyi et al., 2020), and warm-start QAOA (Egger et al., 2021)
5. Inspired practical benchmarks — QAOA MaxCut is now a standard benchmark for quantum hardware and compilers

References

Primary Paper

BIBTEXCopy
@article{farhi2014quantum,
  title   = {A Quantum Approximate Optimization Algorithm},
  author  = {Farhi, Edward and Goldstone, Jeffrey and Gutmann, Sam},
  journal = {arXiv preprint arXiv:1411.4028},
  year    = {2014},
  url     = {https://arxiv.org/abs/1411.4028},
  doi     = {10.48550/arXiv.1411.4028}
}

Key Follow-Up Papers

Learn More

• Original Paper (arXiv)
• QAOA MaxCut — Introductory Version (recommended prerequisite)
• QAOA Review — Blekos et al. 2024
• Cirq QAOA Tutorial
• Guerreschi & Matsuura 2019