Reachability Deficits in Quantum Approximate Optimization

V. Akshay, H. Philathong, M. E.S. Morales, J. D. Biamonte

    Research output: Contribution to journalArticlepeer-review

    51 Citations (Scopus)


    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 algorithm's 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 and are outside of the recently reported level-1 QAOA limitations. These findings are among the first to determine strong limitations on variational quantum approximate optimization.

    Original languageEnglish
    Article number090504
    JournalPhysical Review Letters
    Issue number9
    Publication statusPublished - 5 Mar 2020


    Dive into the research topics of 'Reachability Deficits in Quantum Approximate Optimization'. Together they form a unique fingerprint.

    Cite this