• Open Access

Combinatorial optimization via highly efficient quantum walks

S. Marsh and J. B. Wang
Phys. Rev. Research 2, 023302 – Published 8 June 2020

Abstract

We present a highly efficient quantum circuit for performing continuous time quantum walks (CTQWs) over an exponentially large set of combinatorial objects, provided that the objects can be indexed efficiently. CTQWs form the core mixing operation of a generalized version of the quantum approximate optimization algorithm, which works by “steering” the quantum amplitude into high-quality solutions. The efficient quantum circuit holds the promise of finding high-quality solutions to certain classes of NP-hard combinatorial problems such as the Travelling Salesman Problem, maximum set splitting, graph partitioning, and lattice path optimization.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
1 More
  • Received 6 February 2020
  • Accepted 22 April 2020

DOI:https://doi.org/10.1103/PhysRevResearch.2.023302

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & Technology

Authors & Affiliations

S. Marsh* and J. B. Wang

  • Department of Physics, The University of Western Australia, Perth, WA 6009, Australia

  • *samuel.marsh@research.uwa.edu.au
  • jingbo.wang@uwa.edu.au

Article Text

Click to Expand

References

Click to Expand
Issue

Vol. 2, Iss. 2 — June - August 2020

Subject Areas
Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Research

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×