Quantum Approximate Optimization Algorithm
Quantum Approximate Optimization Algorithm (QAOA) · Also known as: QAOA, quantum alternating operator ansatz
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm designed to solve combinatorial optimization problems on near-term quantum devices. Introduced by Farhi, Goldstone, and Gutmann in 2014, QAOA encodes optimization problems into quantum circuits and uses classical optimization to tune circuit parameters, aiming to find approximately optimal solutions for problems like MaxCut, graph coloring, and scheduling.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
QAOA is suited for combinatorial optimization problems where finding the global optimum is computationally hard classically. It works well on MaxCut, MaxSAT, graph problems, and scheduling tasks. QAOA is preferred for near-term quantum devices (NISQ) when the problem size is moderate (20–100 qubits) and a good approximate solution is acceptable.
Strengths & limitations
- Directly addresses combinatorial optimization, a major application domain.
- Circuit depth grows with problem depth (p), allowing control over circuit length.
- Provably achieves better-than-random performance on certain problem instances.
- Scalable in principle to larger problems as quantum hardware improves.
- Flexible encoding of various optimization problems into the cost Hamiltonian.
- Approximation quality depends on circuit depth (p) and decreases for large p on noisy hardware.
- Convergence to good parameters can require many classical optimization iterations.
- Performance improvement over classical algorithms remains unproven for many problems.
- Noise and decoherence severely degrade performance on current NISQ devices.
- Parameter landscape can have barren plateaus, especially for large systems.
Frequently asked
What is the difference between QAOA and classical simulated annealing?
Simulated annealing probabilistically escapes local optima by thermal fluctuations. QAOA uses quantum superposition and interference, allowing exploration of many candidate solutions simultaneously. Whether QAOA provides a practical advantage depends on problem structure and circuit depth; for most current problems, classical heuristics remain competitive.
How do I choose the circuit depth (p) for my problem?
Start with p = 1 and gradually increase. Each additional layer adds two variational parameters and increases circuit depth exponentially. For small problems (< 20 qubits), p = 3–5 is typical. For larger problems on noisy hardware, keep p small (p ≤ 2) due to noise accumulation.
Can QAOA solve problems larger than what a classical computer can handle?
Not yet. Current QAOA implementations are limited to tens of qubits and must be simulated classically for verification. True quantum advantage remains an open question; the algorithm works well for problem classes where good classical approximations are also hard to find.
How sensitive is QAOA to noise and errors?
QAOA is sensitive to gate errors and decoherence; errors accumulate with circuit depth. Error mitigation techniques like zero-noise extrapolation can help, but they increase measurement overhead. For current devices, keeping p small is essential.
What is a good approximation ratio for QAOA?
The approximation ratio is the expected cost divided by the optimal cost. For MaxCut, QAOA achieves ratios of 0.677–0.706 depending on p and parameters. This matches or slightly exceeds classical polynomial-time approximations (e.g., 0.5 for random cut), offering modest advantage.
Sources
- Farhi, E., Goldstone, J., Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028. DOI: 10.48550/arXiv.1411.4028 ↗
- Zhou, L., Wang, S. T., Choi, S., et al. (2020). Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10, 021067. DOI: 10.1103/PhysRevX.10.021067 ↗
- Hadfield, S., Wang, Z., O'Gorman, B., et al. (2019). From the Ising model to QAOA: A quantum optimization algorithm from the physicist's perspective. Algorithms, 12, 34. link ↗
How to cite this page
ScholarGate. (2026, June 3). Quantum Approximate Optimization Algorithm (QAOA). ScholarGate. https://scholargate.app/en/quantum-computing/quantum-approximate-optimization-algorithm
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Grover's AlgorithmQuantum Computing↔ compare
- Quantum Monte CarloQuantum Computing↔ compare
- Quantum Phase EstimationQuantum Computing↔ compare
- Variational Quantum EigensolverQuantum Computing↔ compare