Adiabatic quantum computation

Tameem Albash and Daniel A. Lidar
Rev. Mod. Phys. 90, 015002 – Published 29 January 2018

Abstract

Adiabatic quantum computing (AQC) started as an approach to solving optimization problems and has evolved into an important universal alternative to the standard circuit model of quantum computing, with deep connections to both classical and quantum complexity theory and condensed matter physics. This review gives an account of the major theoretical developments in the field, while focusing on the closed-system setting. The review is organized around a series of topics that are essential to an understanding of the underlying principles of AQC, its algorithmic accomplishments and limitations, and its scope in the more general setting of computational complexity theory. Several variants are presented of the adiabatic theorem, the cornerstone of AQC, and examples are given of explicit AQC algorithms that exhibit a quantum speedup. An overview of several proofs of the universality of AQC and related Hamiltonian quantum complexity theory is given. Considerable space is devoted to stoquastic AQC, the setting of most AQC work to date, where obstructions to success and their possible resolutions are discussed.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
4 More
  • Received 27 November 2016
  • Corrected 29 April 2019

DOI:https://doi.org/10.1103/RevModPhys.90.015002

© 2018 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & Technology

Corrections

29 April 2019

Correction: A subset of references was improperly tagged, causing their disappearance in the PDF, and has been fixed.

Authors & Affiliations

Tameem Albash

  • Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA, Department of Physics and Astronomy, University of Southern California, Los Angeles, California 90089, USA, and Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA

Daniel A. Lidar

  • Department of Physics and Astronomy, University of Southern California, Los Angeles, California 90089, USA, Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA, Department of Electrical Engineering, University of Southern California, Los Angeles, California 90089, USA, and Department of Chemistry, University of Southern California, Los Angeles, California 90089, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 90, Iss. 1 — January - March 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 Reviews of Modern Physics

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×