QUANTUM COMPUTING
Progress and Prospects
Emily Grumbling and Mark Horowitz, Editors
Committee on Technical Assessment of the Feasibility and Implications of Quantum Computing
Computer Science and Telecommunications Board
Intelligence Community Studies Board
Division on Engineering and Physical Sciences
A Consensus Study Report of
THE NATIONAL ACADEMIES PRESS
Washington, DC
www.nap.edu
THE NATIONAL ACADEMIES PRESS 500 Fifth Street, NW Washington, DC 20001
This activity was supported by the Office of the Director of National Intelligence. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of any organization or agency that provided support for the project.
International Standard Book Number-13: 978-0-309-47969-1
International Standard Book Number-10: 0-309-47969-X
Digital Object Identifier: https://doi.org/10.17226/25196
Additional copies of this publication are available for sale from the National Academies Press, 500 Fifth Street, NW, Keck 360, Washington, DC 20001; (800) 624-6242 or (202) 334-3313; http://www.nap.edu.
Copyright 2019 by the National Academy of Sciences. All rights reserved.
Printed in the United States of America
Suggested citation: National Academies of Sciences, Engineering, and Medicine. 2019. Quantum Computing: Progress and Prospects. The National Academies Press, Washington, DC. doi: https://doi.org/10.17226/25196.
The National Academy of Sciences was established in 1863 by an Act of Congress, signed by President Lincoln, as a private, nongovernmental institution to advise the nation on issues related to science and technology. Members are elected by their peers for outstanding contributions to research. Dr. Marcia McNutt is president.
The National Academy of Engineering was established in 1964 under the charter of the National Academy of Sciences to bring the practices of engineering to advising the nation. Members are elected by their peers for extraordinary contributions to engineering. Dr. C. D. Mote, Jr., is president.
The National Academy of Medicine (formerly the Institute of Medicine) was established in 1970 under the charter of the National Academy of Sciences to advise the nation on medical and health issues. Members are elected by their peers for distinguished contributions to medicine and health. Dr. Victor J. Dzau is president.
The three Academies work together as the National Academies of Sciences, Engineering, and Medicine to provide independent, objective analysis and advice to the nation and conduct other activities to solve complex problems and inform public policy decisions. The National Academies also encourage education and research, recognize outstanding contributions to knowledge, and increase public understanding in matters of science, engineering, and medicine.
Learn more about the National Academies of Sciences, Engineering, and Medicine at www.nationalacademies.org.
Consensus Study Reports published by the National Academies of Sciences, Engineering, and Medicine document the evidence-based consensus on the study’s statement of task by an authoring committee of experts. Reports typically include findings, conclusions, and recommendations based on information gathered by the committee and the committee’s deliberations. Each report has been subjected to a rigorous and independent peer-review process and it represents the position of the National Academies on the statement of task.
Proceedings published by the National Academies of Sciences, Engineering, and Medicine chronicle the presentations and discussions at a workshop, symposium, or other event convened by the National Academies. The statements and opinions contained in proceedings are those of the participants and are not endorsed by other participants, the planning committee, or the National Academies.
For information about other products and activities of the National Academies, please visit www.nationalacademies.org/about/whatwedo.
COMMITTEE ON TECHNICAL ASSESSMENT OF THE FEASIBILITY AND IMPLICATIONS OF QUANTUM COMPUTING
MARK A. HOROWITZ, NAE,1 Stanford University, Chair
ALÁN ASPURU-GUZIK, University of Toronto
DAVID D. AWSCHALOM, NAS2/NAE, University of Chicago
BOB BLAKLEY, Citigroup
DAN BONEH, NAE, Stanford University
SUSAN N. COPPERSMITH, NAS, University of Wisconsin, Madison
JUNGSANG KIM, Duke University
JOHN M. MARTINIS, Google, Inc.
MARGARET MARTONOSI, Princeton University
MICHELE MOSCA, University of Waterloo
WILLIAM D. OLIVER, Massachusetts Institute of Technology
KRYSTA SVORE, Microsoft Research
UMESH V. VAZIRANI, NAS, University of California, Berkeley
Staff
EMILY GRUMBLING, Study Director, Computer Science and Telecommunications Board (CSTB)
SHENAE BRADLEY, Administrative Assistant, CSTB
JON EISENBERG, Senior Director, CSTB
KATIRIA ORTIZ, Associate Program Officer, CSTB
JANKI PATEL, Senior Program Assistant, CSTB
___________________
1 Member, National Academy of Engineering.
2 Member, National Academy of Sciences.
COMPUTER SCIENCE AND TELECOMMUNICATIONS BOARD
FARNAM JAHANIAN, Carnegie Mellon University, Chair
LUIZ BARROSO, Google, Inc.
STEVE M. BELLOVIN, NAE,1 Columbia University
ROBERT F. BRAMMER, Brammer Technology, LLC
DAVID CULLER, NAE, University of California, Berkeley
EDWARD FRANK, Cloud Parity, Inc.
LAURA HAAS, NAE, University of Massachusetts, Amherst
MARK HOROWITZ, NAE, Stanford University
ERIC HORVITZ, NAE, Microsoft Corporation
VIJAY KUMAR, NAE, University of Pennsylvania
BETH MYNATT, Georgia Institute of Technology
CRAIG PARTRIDGE, Colorado State University
DANIELA RUS, NAE, Massachusetts Institute of Technology
FRED B. SCHNEIDER, NAE, Cornell University
MARGO SELTZER, University of British Columbia
MOSHE VARDI, NAS2/NAE, Rice University
Staff
JON EISENBERG, Senior Director
LYNETTE I. MILLETT, Associate Director
SHENAE BRADLEY, Administrative Assistant
EMILY GRUMBLING, Program Officer
RENEE HAWKINS, Financial and Administrative Manager
KATIRIA ORTIZ, Associate Program Officer
JANKI PATEL, Senior Program Assistant
For more information on the CSTB, see its website at http://www.cstb.org, write to CSTB, National Academies of Sciences, Engineering, and Medicine, 500 Fifth Street, NW, Washington, DC 20001, call (202) 334-2605, or e-mail the CSTB at cstb@nas.edu.
___________________
1 Member, National Academy of Engineering.
2 Member, National Academy of Sciences.
INTELLIGENCE COMMUNITY STUDIES BOARD
FREDERICK CHANG, NAE,1 Southern Methodist University, Co-Chair
ROBERT C. DYNES, NAS,2 University of California, San Diego, Co-Chair
JULIE BRILL, Microsoft Corporation
TOMÁS DÍAZ DE LA RUBIA, Purdue University Discovery Park
ROBERT FEIN, McLean Hospital/Harvard Medical School
MIRIAM JOHN, Independent Consultant
ANITA JONES, NAE, University of Virginia
DONALD M. KERR, Independent Consultant
ROBERT H. LATIFF, R. Latiff Associates
MARK LOWENTHAL, Intelligence & Security Academy, LLC
MICHAEL MARLETTA, NAS/NAM,3 University of California, Berkeley
L. ROGER MASON, JR., Peraton
ELIZABETH RINDSKOPF PARKER, Retired, State Bar of California
WILLIAM H. PRESS, NAS, University of Texas, Austin
DAVID A. RELMAN, NAM, Stanford University
SAMUEL VISNER, The MITRE Corporation
Staff
ALAN SHAW, Director
CARYN LESLIE, Senior Program Officer
CHRIS JONES, Financial Manager
MARGUERITE SCHNEIDER, Administrative Coordinator
DIONNA ALI, Research Associate
ADRIANNA HARGROVE, Financial Assistant
NATHANIEL DEBEVOISE, Senior Program Assistant
___________________
1 Member, National Academy of Engineering.
2 Member, National Academy of Sciences.
3 Member, National Academy of Medicine.
This page intentionally left blank.
Acknowledgment of Reviewers
This Consensus Study Report was reviewed in draft form by individuals chosen for their diverse perspectives and technical expertise. The purpose of this independent review is to provide candid and critical comments that will assist the National Academies of Sciences, Engineering, and Medicine in making each published report as sound as possible and to ensure that it meets the institutional standards for quality, objectivity, evidence, and responsiveness to the study charge. The review comments and draft manuscript remain confidential to protect the integrity of the deliberative process.
We thank the following individuals for their review of this report:
___________________
1 Member, National Academy of Engineering.
2 Member, National Academy of Sciences.
Although the reviewers listed above provided many constructive comments and suggestions, they were not asked to endorse the conclusions or recommendations of this report nor did they see the final draft before its release. The review of this report was overseen by Samuel H. Fuller, NAE, Analog Devices, Inc. He was responsible for making certain that an independent examination of this report was carried out in accordance with the standards of the National Academies and that all review comments were carefully considered. Responsibility for the final content rests entirely with the authoring committee and the National Academies.
Preface
Quantum computing, a topic unknown to most of the population a decade ago, has burst into the public’s imagination over the past few years. Part of this interest can be attributed to concerns about the slowing of technology scaling, also known as Moore’s law, which has driven computing performance for over half a century, increasing interest in alternative computing technology. But most of the excitement comes from the unique computational power of a quantum computer and recent progress in creating the underlying hardware, software, and algorithms necessary to make it work.
Before quantum computers, all known realistic computing devices satisfied the extended Church-Turing thesis,1,2 which said that the power of any computing device built could be only polynomially faster than a regular “universal” computer—that is, any relative speedup would scale only according to a power law. Designers of these “classical”3 computing devices increased computing performance by many orders of magnitude by making the operations faster (increasing the clock frequency) and increasing the number of operations completed during each clock cycle.
___________________
1 M.A. Nielsen and I. Chuang, 2016, Quantum Computation and Quantum Information, Cambridge University Press, U.K.
2 P. Kaye, R. Laflamme, and M. Mosca, 2007, An Introduction to Quantum Computing, Oxford University Press, Oxford, UK.
3 In the field of quantum computing, and throughout this report, computers that process information according to classical laws of physics are referred to as “classical computers,” in order to distinguish them from “quantum computers,” which rely upon quantum effects in the processing of information.
While these changes have increased computing performance by many orders of magnitude, the result is just a (large) constant factor faster than the universal computing device. Bernstein et al. showed in 1993 that quantum computers could violate the extended Church-Turing thesis,4 and in 1994 Peter Shor showed a practical example of this power in factoring a large number: a quantum computer could solve this problem exponentially faster than a classical computer. While this result was exciting, at that time no one knew how to build even the most basic element of a quantum computer, a quantum bit, or “qubit,” let alone a full quantum computer. But that situation has recently changed.
Two technologies, one using trapped ionized atoms (trapped ions) and the other using miniature superconducting circuits, have advanced to the point where research groups are able to build small demonstration quantum computing systems, and some groups are making these available to the research community. These recent advances have led to an explosion of interest in quantum computing worldwide; however, with this interest also comes hype and confusion about both the potential of quantum computing and its current status. It is not uncommon to read articles about how quantum computing will enable continued computer performance scaling (it will not) or change the computer industry (its short-term effects will be small, and its long-term effects are unknown).
The Committee on Technical Assessment of the Feasibility and Implications of Quantum Computing was assembled to explore this area to help bring clarity about the current state of the art, likely progress toward, and ramifications of, a general-purpose quantum computer. In responding to its charge, the committee also saw an opportunity to clarify the theoretical characteristics and limitations of quantum computing and to correct some common public misperceptions about the field.
The committee conducted its work through three in-person meetings, a series of teleconferences, and remote collaboration. In order to respond to its charge, the committee focused on understanding the current state of quantum computing hardware, software, and algorithms, and what advances would be needed to create a scalable, gate-based quantum computer capable of deploying Shor’s algorithm. Early in this process, it became clear that the current engineering approaches could not directly scale to the size needed to create this scalable, fully error corrected quantum computer. As a result, the group focused on finding intermediate milestones and metrics to track the progress toward this goal. Throughout this work, the committee endeavored to integrate multiple disciplinary
___________________
4 E. Bernstein and U. Vazirani, 1993, “Quantum Complexity Theory,” in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC ’93), ACM, New York, 11-20, http://dx.doi.org.stanford.idm.oclc.org/10.1145/167088.167097.
perspectives and to think about progress toward building a practical quantum computer from a systems perspective, rather than in terms of a single component or a single discipline.
This work was conducted in its entirety on an unclassified basis. As a result, the committee’s assessments of progress, feasibility, and implications of quantum computing were made using only committee members’ expertise and experience, data gathered in open meetings, one-on-one conversations with outside experts, and information broadly available in the public sphere. No information regarding any nation-state’s classified activities was made available to the committee. As a result, while the committee believes its assessment to be accurate, it recognizes that the assessment is necessarily based upon incomplete information, and it does not preclude the possibility that knowledge of research outside the arena of open science (either privately held or classified by a nation-state) might have altered its assessment.
READING THIS REPORT
This report presents the results of the committee’s study. The reader is encouraged to start with the Summary to get a quick sense of the main findings of this report. The Summary also provides pointers to the sections in the report that describe each of these topics in more detail, to enable the reader to dive into the details of specific topics of interest.
A brief description of each chapter is given below:
- Chapter 1 provides background and context on the field of computing, introducing the computational advantage of a quantum computer. It takes a careful look at why and how classical computing technologies scaled in performance for over half a century. This scaling was mostly the result of a virtuous cycle, where products using new technology allowed the industry to make more money, which it then used to create newer technology. For quantum computing to be similarly successful, it must either create a virtuous cycle to fund the development of increasingly useful quantum computers (with government funding required to support this effort until this stage is reached) or be pursued by an organization committed to providing the necessary investment in order to achieve a practically useful machine even in the absence of intermediate returns or utility (although the total investment is likely to be prohibitively large).
- Chapter 2 introduces the principles of quantum mechanics that make quantum computing different, exciting, and challenging to implement, and compares them with operations of the computers
-
deployed today, which process information according to classical laws of physics—known in the quantum computing community as “classical computers.” This chapter explains why adding one additional qubit to a quantum computer doubles the size of the problem the quantum computer can represent. This increased computational ability comes with the limitations of noisy gates (qubit gate operations have significant error rates), a general inability to read in data efficiently, and limited ability to measure the system, which makes creating effective quantum algorithms difficult. It introduces the three different types of quantum computing studied in this report: analog quantum, digital noisy intermediate-scale quantum (digital NISQ), and fully error corrected quantum computers.
- Recognizing the difficulty of harnessing the power of quantum computing, Chapter 3 looks at quantum algorithms in more depth. The chapter starts with known foundational algorithms for fully error corrected machines but then shows that the overhead for error correction is quite large—that is, it takes many physical qubits and physical gate operations to emulate an error-free, so-called logical qubit that can be used in complex algorithms. Such machines are therefore unlikely to exist for a number of years. It then examines potential algorithms for both analog and digital NISQ computers that would enable practical utility and shows that more work is needed in this area.
- Because Shor’s algorithm breaks currently deployed asymmetric ciphers—that is, it would enable them to be decrypted without a priori knowledge of the secret key—Chapter 4 discusses the classical cryptographic ciphers currently used to protect electronic data and communications, how a large quantum computer could defeat these systems, and what the cryptography community should do now (and has begun to do) to address these vulnerabilities.
- Chapters 5 and 6 discuss general architectures and progress to date in building the necessary hardware and software components, respectively, required for quantum computing.
- Chapter 7 provides the committee’s assessment of the technical progress and other factors required to make significant progress in quantum computing, tools for assessing and reassessing the possible time frames and implications of such developments, and an outlook for the future of the field.
While the committee has tried to make the report accessible to non-experts, a few of the chapters do become a little (or more than a little)
technical in order to describe some of the issues at play more precisely. Feel free to skip over these sections when you find them—the key points of these sections are either highlighted as chapter-level findings or are summarized either at the end of the section or chapter.
ACKNOWLEDGMENTS
This work would not have been possible without the contributions of a host of individuals to whom the committee and the National Academies extend our sincere thanks. Jake Farinholt at the U.S. Dahlgren Naval Surface Warfare Research Center provided a bibliometric analysis of research in quantum computing and related areas, which provided a helpful illustration of global engagement in these fields. Dr. Mary Kavanagh, minister counsellor at the European Commission’s Delegation to the United States, and Mr. Anthony Murfett, minister counsellor at the Australian Embassy in Washington, D.C., helpfully provided information about EU and Australian research efforts in quantum science and technology.
In addition to all of the speakers who presented technical input at committee meetings, the committee would also like to acknowledge Mark Saffman, Jonathan Dowling, Pete Shadbolt, Jelena Vuckovic, Helmut Katzgraber, Robert Colwell, and Eddie Farhi for helpful conversations or correspondence with individual committee members over the course of this activity that helped to clarify technical issues of relevance to this report.
We would also like to thank the sponsor of this research, the Office of the Director of National Intelligence of the United States of America, for financial support of this study, and Jon Eisenberg, senior director of the Computer Science and Telecommunications Board, for his guidance.
I am deeply grateful to the members of the committee who generously spent their valuable time creating this report and educating a chair who was not an expert in quantum computing. I would especially like to thank Emily Grumbling, study director, who put in long hours to create the report in front of you. It would not exist without her help. While it might not be rare for a committee chair to say that he enjoyed chairing the study group, in this case it actually is true. I had a wonderful time learning about the power, progress, and problems of quantum computing. I hope that this report is helpful in your exploration of the subject as well.
Mark Horowitz, Chair
Committee on Technical Assessment of the Feasibility and Implications of Quantum Computing
This page intentionally left blank.
Contents
1.1 Origins of Contemporary Computing
1.3 Historical Progress in Computing: Moore’s Law
1.4 Converting Transistors to Cheap Computers
1.6 Quantum: A New Approach to Computing
2 QUANTUM COMPUTING: A NEW PARADIGM
2.1 The Nonintuitive Physics of the Quantum World
2.2 The Landscape of Quantum Technology
2.5 Quantum Computer Design Constraints
2.6 The Potential for Functional Quantum Computers
3 QUANTUM ALGORITHMS AND APPLICATIONS
3.1 Quantum Algorithms for an Ideal Gate-Based Quantum Computer
3.4 Applications of a Quantum Computer
3.5 The Potential Role of Quantum Computers in the Computing Ecosystem
4 QUANTUM COMPUTING’S IMPLICATIONS FOR CRYPTOGRAPHY
4.1 Cryptographic Algorithms in Current Use
4.4 Practical Deployment Challenges
5 ESSENTIAL HARDWARE COMPONENTS OF A QUANTUM COMPUTER
5.1 Hardware Structure of a Quantum Computer
6 ESSENTIAL SOFTWARE COMPONENTS OF A SCALABLE QUANTUM COMPUTER
6.1 Challenges and Opportunities
6.2 Quantum Programming Languages
6.4 Specification, Verification, and Debugging
6.5 Compiling from a High-Level Program to Hardware
7 FEASIBILITY AND TIME FRAMES OF QUANTUM COMPUTING
7.1 The Current State of Progress
7.2 A Framework for Assessing Progress in Quantum Computing
7.3 Milestones and Time Estimates