Algorithms · QAOA
QAOA MaxCut on a 5-node ring
A p=1 QAOA circuit with a classical MaxCut comparison and reproducible simulation evidence.
Strong empiricalUpdated
Open on the mapView frozen graph
A small worked example, computed in your browser. It is not a result from this record's papers.
QAOA, p=1, MaxCut on a 4-cycle
4 qubits on a 4-cycle (edges 0-1, 1-2, 2-3, 3-0), one QAOA layer with gamma=pi/8, beta=3*pi/8.
Step 1 of 2 · Hadamard layer(4)
Probability of each outcome after this step
- 00006%
- 00016%
- 00106%
- 00116%
- 01006%
- 01016%
- 01106%
- 01116%
- 8 more outcomes50%
Starts from the uniform superposition over all 16 possible cuts.
Probability spreads from 1 outcome to 16. All 16 are equally likely.
The cost layer (RZZ(2*gamma) on each of the 4 edges) rewards cuts that separate connected qubits, then the mixer (RX(2*beta) on every qubit) lets amplitude move between cuts.
Probability moves between the same 16 outcomes. Up: 0101 6.3% → 26.6%, 1010 6.3% → 26.6%. Down: 0001 6.3% → 1.6%. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
Readout 0101 and 1010 are the two optimal cuts of a 4-cycle (alternating around the ring); at these angles measuring the register returns one of them clearly more often than any other cut.
Open in Studio- Steps3
- Wires5
- Qubits5
- Depth14 gates
- Shots4096
- Papers2
This record moves from primitives to a small optimization workload: the objective, circuit, sampling boundary, and acceptance metric stay visible together.
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 →
QAOA at depth prepares , alternating a problem (cost) unitary and a mixer unitary. For MaxCut on a graph , the cost Hamiltonian is , whose expectation counts cut edges, and the mixer is , whose exponential is a product of independent -rotations letting the state explore bitstrings. For this record's 5-node ring, 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 against a threshold — evidence that the sampled circuit matches its own noiseless simulation, not a claim that finds the graph's true maximum cut.
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 →
- Qubits
- 5
- Depth
- 14 gates
- Shots
- 4096
- Graph
- 5-node ring
- QAOA depth
- p = 1
- Acceptance
- TVD ≤ 0.05
- Seed
- 42
H×5on q[0], q[1], q[2], q[3], q[4]Coston q[0], q[1]Mixeron q[0], q[1], q[2], q[3], q[4]
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.
Nobody has reviewed this record for gaps yet.
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 = qcThe public snippet keeps the graph structure readable; the verified run stores the full parameterized circuit.
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 over bits and clauses; given, for adiabatic evolution, as the final Hamiltonian of an interpolation whose starting point has an easily-constructed ground state. Neither method is told how the operator was built, or by which encoding. Returns A bit string 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.
Related entries
- Bell state measurement
Basic circuits
- QFT resource screen
Algorithms
References
- A Quantum Approximate Optimization Algorithm
Edward Farhi, Jeffrey Goldstone, Sam Gutmann · 2014
Introduces QAOA for approximate combinatorial optimization and analyzes MaxCut at fixed depth.
- The QAOA for MaxCut: a fermionic view
Wang, Hadfield, Jiang, Rieffel · 2018
Analyzes parameter setting and the ring-of-disagrees instance used by this record.