Obstacles to Variational Quantum Optimization from Symmetry Protection

Sergey Bravyi, Alexander Kliesch, Robert Koenig, Eugene Tang

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

112 Zitate (Scopus)


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.

FachzeitschriftPhysical Review Letters
PublikationsstatusVeröffentlicht - 24 Dez. 2020


Untersuchen Sie die Forschungsthemen von „Obstacles to Variational Quantum Optimization from Symmetry Protection“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren