The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples

Built on

On the independence number of random graphs
A. Frieze · 1990
Earlier work this paper cites.
Random max sat, random max cut, and their phase transitions
Don Coppersmith, David Gamarnik, Mohammad Hajiaghayi, and Gregory B Sorkin · 2004
Earlier work this paper cites.
Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
Original
Frantisek Kardos, Daniel Kral, and Jan Volec · 2011
Earlier work this paper cites.

A quantum approximate optimization algorithm
Original
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Cited alongside, same era.
A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem
Original
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Cited alongside, same era.
Extremal cuts of sparse random graphs
Amir Dembo, Andrea Montanari, and Subhabrata Sen · 2017
Cited alongside, same era.
Short cycles in random regular graphs
Brendan D. McKay, Nicholas C. Wormald, and Beata Wysocka
Cited in the paper.

Cubic graphs with small independence ratio
Original
József Balogh, Alexandr Kostochka, and Xujun Liu · 2017
Later among the works it cites.
Obstacles to state preparation and variational optimization from symmetry protection
Original
Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang · 2019
Later among the works it cites.
The quantum approximate optimization algorithm needs to see the whole graph: A typical case
Original
Edward Farhi, David Gamarnik, and Sam Gutmann · 2020
Closest in time.