Noisy intermediate-scale quantum algorithms

Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik
Rev. Mod. Phys. 94, 015004 – Published 15 February 2022
PDFHTMLExport Citation

Abstract

A universal fault-tolerant quantum computer that can efficiently solve problems such as integer factorization and unstructured database search requires millions of qubits with low error rates and long coherence times. While the experimental advancement toward realizing such devices will potentially take decades of research, noisy intermediate-scale quantum (NISQ) computers already exist. These computers are composed of hundreds of noisy qubits, i.e., qubits that are not error corrected, and therefore perform imperfect operations within a limited coherence time. In the search for achieving quantum advantage with these devices, algorithms have been proposed for applications in various disciplines spanning physics, machine learning, quantum chemistry, and combinatorial optimization. The overarching goal of such algorithms is to leverage the limited available resources to perform classically challenging tasks. In this review, a thorough summary of NISQ computational paradigms and algorithms is provided. The key structure of these algorithms and their limitations and advantages are discussed. A comprehensive overview of various benchmarking and software tools useful for programming and testing NISQ devices is additionally provided.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 26 March 2021

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

© 2022 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & Technology

Authors & Affiliations

Kishor Bharti*

  • Centre for Quantum Technologies, National University of Singapore, 117543 Singapore

Alba Cervera-Lierta and Thi Ha Kyaw

  • Department of Computer Science, University of Toronto, Toronto, Ontario M5S 2E4, Canada and Chemical Physics Theory Group, Department of Chemistry, University of Toronto, Toronto, Ontario M5G 1Z8, Canada

Tobias Haug

  • QOLS, Blackett Laboratory, Imperial College London SW7 2AZ, United Kingdom

Sumner Alperin-Lea and Abhinav Anand

  • Chemical Physics Theory Group, Department of Chemistry, University of Toronto, Toronto, Ontario M5G 1Z8, Canada

Matthias Degroote§

  • Department of Computer Science, University of Toronto, Toronto, Ontario M5S 2E4, Canada and Chemical Physics Theory Group, Department of Chemistry, University of Toronto, Toronto, Ontario M5G 1Z8, Canada

Hermanni Heimonen

  • Centre for Quantum Technologies, National University of Singapore, 117543 Singapore

Jakob S. Kottmann

  • Department of Computer Science, University of Toronto, Toronto, Ontario M5S 2E4, Canada and Chemical Physics Theory Group, Department of Chemistry, University of Toronto, Toronto, Ontario M5G 1Z8, Canada

Tim Menke

  • Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA, Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA, and Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA

Wai-Keong Mok

  • Centre for Quantum Technologies, National University of Singapore, 117543 Singapore

Sukin Sim

  • Department of Chemistry and Chemical Biology, Harvard University, Cambridge, Massachusetts 02138, USA

Leong-Chuan Kwek

  • Centre for Quantum Technologies, National University of Singapore 117543, Singapore, MajuLab, CNRS-UNS-NUS-NTU International Joint Research Unit UMI 3654, Singapore, and National Institute of Education and Institute of Advanced Studies, Nanyang Technological University, 637616 Singapore

Alán Aspuru-Guzik**

  • Department of Computer Science, University of Toronto, Toronto, Ontario M5S 2E4, Canada, Chemical Physics Theory Group, Department of Chemistry, University of Toronto, Toronto, Ontario M5G 1Z8, Canada, Vector Institute for Artificial Intelligence, Toronto, Ontario M5S 1M1, Canada, and Canadian Institute forthat Advanced Research, Toronto, Ontario M5G 1Z8, Canada

  • *Present address: Joint Center for Quantum Information and Computer Science and Joint Quantum Institute, NIST/University of Maryland, College Park, Maryland 20742, USA. kishor.bharti1@gmail.com
  • a.cervera.lierta@gmail.com
  • thihakyaw.phy@gmail.com
  • §Present address: Quantum Lab, Boehringer Ingelheim, 55218 Ingelheim am Rhein, Germany.
  • cqtklc@gmail.com
  • **alan@aspuru.com

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 94, Iss. 1 — January - March 2022

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
×