MaxCut quantum approximate optimization algorithm performance guarantees for p>1

Jonathan Wurtz and Peter Love
Phys. Rev. A 103, 042612 – Published 27 April 2021
PDFHTMLExport Citation

Abstract

We obtain worst-case performance guarantees for p=2 and 3 QAOA for MaxCut on uniform 3-regular graphs. Previous work by Farhi et al. obtained a lower bound on the approximation ratio of 0.692 for p=1. We find a lower bound of 0.7559 for p=2, where worst-case graphs are those with no cycles 5. This bound holds for any 3-regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all p, where worst-case graphs have with no cycles 2p+1. Under this conjecture, the approximation ratio is at least 0.7924 for all 3-regular graphs and p=3. In addition, using an indistinguishable argument we find an upper bound on the worst-case approximation ratio for all p, which indicates classes of graphs for which there can be no quantum advantage for at least p<6.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
6 More
  • Received 4 February 2021
  • Accepted 14 April 2021

DOI:https://doi.org/10.1103/PhysRevA.103.042612

©2021 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & Technology

Authors & Affiliations

Jonathan Wurtz* and Peter Love

  • Department of Physics and Astronomy, Tufts University, Medford, Massachusetts 02155, USA

  • *Corresponding author: jonathan.wurtz@tufts.edu

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 103, Iss. 4 — April 2021

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×