Algorithms · QAOA
The Quantum Approximate Optimization Algorithm
A quantum algorithm that produces approximate solutions for combinatorial optimization problems, tunable by a positive integer p.
Attested & literatureUpdated
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
- Wires3
- Record typeLiterature reference
- Tunable parameterA positive integer p
- Circuit depthLinear in p times (at worst) the number of constraints
- Papers1
The QAOA paper introduces a quantum algorithm that produces approximate solutions for combinatorial optimization problems, depending on a positive integer p, with the quality of the approximation improving as p is increased.
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 →
The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought, and the depth of the circuit grows linearly with p times, at worst, the number of constraints. The authors give two regimes: if p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing, and if p grows with the input size a different strategy is proposed. They study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p; for p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal 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 →
- Record type
- Literature reference
- Tunable parameter
- A positive integer p
- Circuit depth
- Linear in p times (at worst) the number of constraints
- Gate locality
- At most the locality of the objective function
- Problem studied in the paper
- MaxCut on 2-regular and 3-regular graphs
- Stated guarantee
- p = 1, 3-regular: cut at least 0.6924 of optimal
- Speedup claimed by the abstract
- None; no classical comparison is made
- Circuit
- Not supplied
prepareon objectivecost(γ)on objective, ansatzmixer(β)on ansatz, readout
Quantum vs classical
Classical baseline
Compare QAOA with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: The Quantum Approximate Optimization Algorithm
PROBLEM: Produce approximate solutions for combinatorial optimization problems.
PARAMETER: a positive integer p; the quality of the approximation improves as p is increased.
CIRCUIT: unitary gates whose locality is at most the locality of the objective function
whose optimum is sought; depth grows linearly with p times (at worst) the number
of constraints.
REGIMES: p fixed and independent of the input size -> efficient classical preprocessing;
p growing with the input size -> a different strategy is proposed.
STUDIED ON: MaxCut on regular graphs; performance analyzed on 2-regular and 3-regular
graphs for fixed p.
STATED GUARANTEE: for p = 1, on 3-regular graphs the algorithm always finds a cut that is
at least 0.6924 times the size of the optimal cut.
NOT IN THE PAPER: any problem other than MaxCut; the QUBO modelling layer; penalty weights;
the classical outer optimiser; the CVaR objective; any comparison with a classical
algorithm; any running time.
PRIMARY SOURCE: Edward Farhi, Jeffrey Goldstone, Sam Gutmann (2014),
A Quantum Approximate Optimization Algorithm — https://arxiv.org/abs/1411.4028
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a 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
- QAOA MaxCut on a 5-node ring
Algorithms
- Ising formulations of NP-complete and NP-hard problems
Algorithms
- QUBO operator mapping
Operators
- Quantum adiabatic evolution
Algorithms
References
- A Quantum Approximate Optimization Algorithm
Edward Farhi, Jeffrey Goldstone, Sam Gutmann · 2014
Primary source, and the only source read for this record. It introduces the algorithm, fixes the meaning of p, states the locality bound on the gates and the linear growth of circuit depth, separates the fixed-p and growing-p regimes, and proves the 0.6924 ratio for p = 1 on 3-regular graphs. Consult it for the form of the cost and mixer operators, for how the fixed-p classical preprocessing selects the angles, for the strategy proposed when p grows with the input size, and for the 2-regular analysis — none of which the abstract states. It formulates MaxCut and no other problem.