# Reachability Deficits in Quantum Approximate Optimization

arXiv: https://arxiv.org/abs/1906.11259 · HTML: https://mlsanity.com/paper/1906.11259/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2019.

## Built on by (most cited first, 9 of 9)

- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [Graph neural network initialisation of quantum approximate optimisation](https://mlsanity.com/paper/2111.03016/) (2021)
- [Training Saturation in Layerwise Quantum Approximate Optimisation](https://mlsanity.com/paper/2106.13814/) (2021)
- [Quantum Deep Dreaming: A Novel Approach for Quantum Circuit Design](https://mlsanity.com/paper/2211.04343/) (2022)
- [Breaking Through Barren Plateaus: Reinforcement Learning Initializations for Deep Variational Quantum Circuits](https://mlsanity.com/paper/2508.18514/) (2025)
- [On Circuit Depth Scaling For Quantum Approximate Optimization](https://mlsanity.com/paper/2205.01698/) (2022)
- [Solving the Traveling Salesman Problem via Different Quantum Computing Architectures](https://mlsanity.com/paper/2502.17725/) (2025)
- [Quantum King-Ring Domination in Chess: A QAOA Approach](https://mlsanity.com/paper/2601.00318/) (2026)
- [Extractive summarization on a CMOS Ising machine](https://mlsanity.com/paper/2601.11491/) (2026)

## Abstract (arXiv)

The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithms ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio-this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability~deficits persist even in the absence of barren plateaus [McClean et al., 2018] and are outside of the recently reported level-1 QAOA limitations [Hastings 2019]. These findings are among the first to determine strong limitations on variational quantum approximate optimization.