Obstacles to Variational Quantum Optimization from Symmetry Protection

Sergey Bravyi, Alexander Kliesch, Robert Koenig, Eugene Tang

Research output: Contribution to journalArticlepeer-review

110 Scopus citations


The quantum approximate optimization algorithm (QAOA) employs variational states generated by a parameterized quantum circuit to maximize the expected value of a Hamiltonian encoding a classical cost function. Whether or not the QAOA can outperform classical algorithms in some tasks is an actively debated question. Our work exposes fundamental limitations of the QAOA resulting from the symmetry and the locality of variational states. A surprising consequence of our results is that the classical Goemans-Williamson algorithm outperforms the QAOA for certain instances of MaxCut, at any constant level. To overcome these limitations, we propose a nonlocal version of the QAOA and give numerical evidence that it significantly outperforms the standard QAOA for frustrated Ising models.

Original languageEnglish
Article number260505
JournalPhysical Review Letters
Issue number26
StatePublished - 24 Dec 2020


Dive into the research topics of 'Obstacles to Variational Quantum Optimization from Symmetry Protection'. Together they form a unique fingerprint.

Cite this