Quantum approximate optimisation algorithm (QAOA)
Algorithms and benchmarks / Optimisation
A variational method for combinatorial optimisation, such as finding a large cut in a graph or scheduling, with circuits that alternate between the cost function and a mixing step.
- Era
- Noisy intermediate-scale (NISQ)
- Problem class
- Optimisation
- Speedup
- None proven for practical problems; at p = 1 it always finds a cut of at least 0.6924 of the optimum on 3-regular graphs (Farhi et al. 2014).
How it works
p layers each apply the problem Hamiltonian and a mixer with tunable angles; a classical optimiser chooses the angles; quality can only improve as p grows.
Typical use cases
- Scheduling, routing and portfolio optimisation.
Documented use cases on related problems
From the use case directory; the sources of these cases may use other methods than this one.
- Hybrid quantum algorithm for rolling stock planning (Deutsche Bahn and IQM)
- Dynamic investment portfolio optimisation on quantum platforms (BBVA and Multiverse)
- Aircraft cargo loading optimisation in the Airbus Quantum Computing Challenge
Related pages
Resource estimates
No resource estimate with stated assumptions was verified for this family in this release.
Demonstrations
- 2021: QAOA on up to 23 qubits: on problems matching the hardware graph performance did not depend on size and improved with depth; on compiled problems it fell with size but stayed better than random guessing. (M. P. Harrigan et al. 2021)
Hardware platforms that fit
- Superconducting qubits: Ran on a planar superconducting processor with up to 23 qubits (Harrigan et al. 2021).
- Neutral atoms: Neutral-atom arrays run related optimisation natively (see analogue optimisation on Rydberg arrays).
What you need to run it
- Classical simulation
- A state-vector simulator holds 2^n complex amplitudes, so memory doubles with every qubit: about 30 qubits fit in 16 GiB at double precision. Circuits with little entanglement can go further with tensor-network methods. See the guide for the calculator.
- Noisy hardware (NISQ)
- Tens to a few hundred qubits; connectivity matching the problem graph matters more than raw qubit count; many shots and classical optimisation loops.
- Fault-tolerant machine
- Not applicable for this family.
- Annealer or analogue simulator
- Not applicable for this family.
Calculate the memory of a simulation
Where to run it in Europe
Superconducting qubits
- VLQ (Czechia; Inaugurated, per the EuroHPC JU): Superconducting; digital quantum computer. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones VLQ
- Euro-Q-Exa (Germany; Inaugurated, per the EuroHPC JU): Superconducting; digital quantum computer. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones Euro-Q-Exa
- EuroQCS-Spain (Spain; Inaugurated, per the EuroHPC JU): Superconducting annealing; analogue quantum computer. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones EuroQCS-Spain
- Quantum Inspire (Netherlands; In operation, per the source): Online platform with superconducting transmon QPUs, a neutral-atom emulator and simulators; a Spin-2+ electron spin QPU is listed as archived. Access: Quantum Inspire registration.
- LRZ Quantum Integration Centre (QIC) (Germany; In operation, per the source): Superconducting systems from IQM (54 qubits, up to 150 in future), a 20-qubit AQT ion-trap system, and a neutral-atom system being developed by planqc (MAQCS project). Access: LRZ quantum computing consulting.
- Finnish Quantum-Computing Infrastructure (FiQCI) (Finland; In operation, per the source): Hybrid HPC and quantum computing platform: VTT Q50 (53 qubits) and Aalto Q20 (20 qubits), superconducting systems made by IQM, used through the LUMI supercomputer environment. Access: FiQCI calls for academic projects.
- Quantum Spain quantum computer at BSC-CNS (Spain; In operation, per the source): Superconducting; digital quantum computer with a 35-qubit processor, integrated into the MareNostrum 5 supercomputer. Access: Spanish Supercomputing Network (RES) quantum access. Deployment milestones Quantum Spain quantum computer at BSC-CNS
Neutral atoms
- JADE (Germany; Inaugurated, per the EuroHPC JU): Neutral atoms; analogue/digital quantum simulator. No access route named in the catalogue. Deployment milestones JADE
- Ruby (France; Inaugurated, per the EuroHPC JU): Neutral atoms; analogue/digital quantum simulator. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones Ruby
- SOL (Italy; Planned, per the EuroHPC JU): Neutral atoms; analogue/digital quantum simulator. No access route named in the catalogue. Deployment milestones SOL
- LRZ Quantum Integration Centre (QIC) (Germany; In operation, per the source): Superconducting systems from IQM (54 qubits, up to 150 in future), a 20-qubit AQT ion-trap system, and a neutral-atom system being developed by planqc (MAQCS project). Access: LRZ quantum computing consulting.
- France Hybrid HPC Quantum Initiative (HQI) platform (France; In operation, per the source): Hybrid HPC–quantum platform coupled to the Joliot-Curie supercomputer: Ruby (analogue neutral-atom system controlling 100 rubidium atoms), Lucy (12-photon photonic QPU) and Qaptiva QPU emulation. Access: GENCI eDARI resource allocation requests. Deployment milestones France Hybrid HPC Quantum Initiative (HQI) platform
The full infrastructure catalogue · The infrastructure deployment tracker
Software
European tools in the software directory
Other open-source frameworks
- Qiskit (IBM (United States); non-European)
- PennyLane (Xanadu (Canada); non-European)
- Cirq (Google Quantum AI (United States); non-European)
A listing is not an endorsement; check each tool for the features you need.
Limitations and open questions
- Problems that do not match the hardware connectivity need compilation that degrades results as size grows (Harrigan et al. 2021).
- Classical heuristics are strong competitors; this release lists no verified advantage on a practical problem.
In the Quantum Algorithm Zoo
- Quantum Approximate Optimization (Quantum Algorithm Zoo, external site): Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Superpolynomial
Index: the Quantum Algorithm Zoo by Stephen P. Jordan, last updated 2026-09-10, checked 2026-10-23. The portal links to it and copies no description from it. Browse the full Quantum Algorithm Zoo (external site)
Named in European procurements
- Used in: EuroHPC procurement Euro-Q-Exa (Required in the benchmark suite (scored under the award criteria))
- Used in: EuroHPC procurement EuroQCS-France (now Lucy) (Required in the benchmark suite (scored under the award criteria))
- Used in: EuroHPC procurement LUMI-Q (now VLQ) (Required in the benchmark suite (scored under the award criteria))
- Used in: EuroHPC procurement EuroQCS-Italy (now SOL) (Required in the benchmark suite (scored under the award criteria))
- Used in: EuroHPC procurement EuroSSQ-HPC (Required in the benchmark suite (scored under the award criteria))
As the tender documents state; how a benchmark is weighted against others is described in each procurement.
Sources
- E. Farhi, J. Goldstone, S. Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 (2014). Read: abstract page, retrieved 2026-10-23.
- M. P. Harrigan et al. (2021). Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor. Nature Physics 17, 332 (2021); arXiv:2004.04197. Read: abstract page, retrieved 2026-10-23.