Quantum approximate optimization algorithm for MaxCut: A fermionic view

Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel
Phys. Rev. A 97, 022304 – Published 5 February 2018

Abstract

Farhi et al. recently proposed a class of quantum algorithms, the quantum approximate optimization algorithm (QAOA), for approximately solving combinatorial optimization problems (E. Farhi et al., arXiv:1411.4028; arXiv:1412.6062; arXiv:1602.07674). A level-p QAOA circuit consists of p steps; in each step a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The 2p times for which these two Hamiltonians are applied are the parameters of the algorithm, which are to be optimized classically for the best performance. As p increases, parameter optimization becomes inefficient due to the curse of dimensionality. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here we analytically and numerically study parameter setting for the QAOA applied to MaxCut. For the level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher p could be derived, but the number of terms quickly becomes prohibitive. For a special case of MaxCut, the “ring of disagrees,” or the one-dimensional antiferromagnetic ring, we provide an analysis for an arbitrarily high level. Using a fermionic representation, the evolution of the system under the QAOA translates into quantum control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of the QAOA for any p. It also greatly simplifies the numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional submanifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 3 October 2017
  • Corrected 30 November 2020

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

©2018 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & Technology

Corrections

30 November 2020

Correction: A missing factor of 2 in Eq. (14) has been inserted and a sign error in Eq. (A11) has been fixed.

Authors & Affiliations

Zhihui Wang1,2, Stuart Hadfield3, Zhang Jiang1,4, and Eleanor G. Rieffel1

  • 1Quantum Artificial Intelligence Laboratory, NASA Ames Research Center, California 94035, USA
  • 2Universities Space Research Association, Columbia, Maryland 21046, USA
  • 3Department of Computer Science, Columbia University, New York, New York 10027, USA
  • 4Stinger Ghaffarian Technologies, Inc., Greenbelt, Maryland 20770, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 97, Iss. 2 — February 2018

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
×