Strong empiricalAlgorithmsQAOA2026-07-12

QAOA MaxCut on a 5-node ring

A p=1 QAOA circuit with a classical MaxCut comparison and reproducible simulation evidence.

optimizationmaxcutqaoasimulation

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

This record moves from primitives to a small optimization workload: the objective, circuit, sampling boundary, and acceptance metric stay visible together.

Circuit & simulation

q[0]

H×5CostMixer

q[1]

H×5CostMixer

q[2]

H×5Mixer

q[3]

H×5Mixer

q[4]

H×5Mixer

Best cut family72%

Other bitstrings28%

What this takes and returns

TakesNothingWhat joins here

No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

ReturnsNothingWhat joins here

No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →

Where this sits

This record is named by the layer graph at:

Alternate a cost unitary with a mixer, p times Method
Takes An Ising or QUBO operator, diagonal in the computational basis, whose extremal eigenvector encodes the problem's solution — given, for QAOA, as a sum of clause terms $C(z) = \sum_{\alpha=1}^{m} C_\alpha(z)$ over $n$ bits and $m$ clauses; given, for adiabatic evolution, as the final Hamiltonian $H_P$ of an interpolation whose starting point $H_B$ has an easily-constructed ground state. Neither method is told how the operator was built, or by which encoding. Returns A bit string $z$ read off the computational basis — the assignment — together with the objective value it achieves, or, for the adiabatic route, the stated promise that this string is (with fidelity approaching 1, for a long enough evolution time) the true minimiser. Neither route returns an energy with an error bar; both return a string.

How it works

QAOA at depth $p=1$ prepares $|\gamma,\beta\rangle = e^{-i\beta H_M}e^{-i\gamma H_C}H^{\otimes n}|0\rangle^{\otimes n}$ , alternating a problem (cost) unitary and a mixer unitary. For MaxCut on a graph $G=(V,E)$ , the cost Hamiltonian is $H_C=\sum_{(j,k)\in E}\frac{1}{2}(I-Z_jZ_k)$ , whose expectation counts cut edges, and the mixer is $H_M=\sum_j X_j$ , whose exponential is a product of independent $X$ -rotations letting the state explore bitstrings. For this record's 5-node ring, $H_C$ sums five such terms around the cycle. The reported acceptance is empirical, not a matrix identity: the sampled 4096-shot distribution (seed 42) is compared with the reference simulator using total variation distance, giving $\mathrm{TVD}=0.0088$ against a $\delta\le0.05$ threshold — evidence that the sampled circuit matches its own noiseless simulation, not a claim that $p=1$ finds the graph's true maximum cut.

Implementation

FrameworkNative

qaoa_maxcut_ring.py

from qiskit import QuantumCircuit

qc = QuantumCircuit(5, 5)
qc.h(range(5))
# p=1 cost and mixer layers
for edge in ((0, 1), (1, 2), (2, 3), (3, 4), (4, 0)):
    qc.cx(*edge)
qc.measure(range(5), range(5))

FINAL_CIRCUIT = qc

The public snippet keeps the graph structure readable; the verified run stores the full parameterized circuit.

Quantum vs classical

Classical baseline

Exact enumeration for the five-node fixture; Goemans–Williamson or MILP for larger MaxCut instances.

Quantum claim

The circuit samples candidate cuts; it does not replace the classical optimizer or certify a global optimum by itself.

How to compare

Report approximation ratio, success probability, optimizer cost, shots, and wall-clock time against the same instance and budget.

Declared gaps

Nobody has reviewed this record for gaps yet.

Literature & references

A Quantum Approximate Optimization Algorithm2014 · Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Introduces QAOA for approximate combinatorial optimization and analyzes MaxCut at fixed depth.

arxiv.org/abs/1411.4028 ↗

The QAOA for MaxCut: a fermionic view2018 · Wang, Hadfield, Jiang, Rieffel

Analyzes parameter setting and the ring-of-disagrees instance used by this record.

doi.org/10.1103/physreva.97.022304 ↗