Sign in
← Atlas
Attested & literatureAlgorithmsQAOA

The Quantum Approximate Optimization Algorithm

A quantum algorithm that produces approximate solutions for combinatorial optimization problems, tunable by a positive integer p.

VariationalQAOAOptimization
qaoacombinatorial optimizationvariationalmaxcutapproximation ratio

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

QAOA is the algorithm the whole applied-optimisation half of the Classiq library runs on. Its 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.

Circuit & simulation
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)=∑α=1mCα(z)C(z) = \sum_{\alpha=1}^{m} C_\alpha(z) over nn bits and mm clauses; given, for adiabatic evolution, as the final Hamiltonian HPH_P of an interpolation whose starting point HBH_B has an easily-constructed ground state. Neither method is told how the operator was built, or by which encoding. Returns A bit string zz 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

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.

Implementation
Unsupported
qaoa-combinatorial-optimization.txt
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.

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.

Declared gaps

Nobody has reviewed this record for gaps yet.

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

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.

arxiv.org/abs/1411.4028 ↗

Related entries

AlgorithmsQAOA MaxCut on a 5-node ringAlgorithmsIsing formulations of NP-complete and NP-hard problemsOperatorsQUBO operator mappingAlgorithmsQuantum adiabatic evolution