National Academies Press: OpenBook

Quantum Computing: Progress and Prospects (2018)

Chapter: Front Matter

Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R1
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R2
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R3
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R4
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R5
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R6
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R7
Page viii Cite
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R8
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R9
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R10
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R11
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R12
Page xiii Cite
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R13
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R14
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R15
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R16
Page xvii Cite
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R17
Page xviii Cite
Suggested Citation:"Front Matter." National Academies of Sciences, Engineering, and Medicine. 2018. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. doi: 10.17226/25196.
×
Page R18

Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION 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 PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION

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 author(s) and do not necessarily reflect the views of any organization or agency that provided support for the project. International Standard Book Number-13: International Standard Book Number-10: 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 2018 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. 2018. Quantum Computing: Progress and Prospects. The National Academies Press, Washington, DC. DOI: https://doi.org/10.17226/25196. PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION

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. PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION

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. PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION

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, NAS/NAE,2 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 and National Academy of Engineering. PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION v

COMPUTER SCIENCE AND TELECOMMUNICATIONS BOARD FARNAM JAHANIAN, Carnegie Mellon University, CSTB Chair LUIZ ANDRÉ BARROSO, Google, Inc. STEVE M. BELLOVIN, NAE,3 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 Colombia MOSHE VARDI, NAS/NAE,4 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 Research Council, 500 Fifth Street, NW, Washington, DC 20001, call (202) 334-2605, or e-mail the CSTB at cstb@nas.edu. 3 Member, National Academy of Engineering. 4 Member, National Academy of Sciences and National Academy of Engineering. PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION vi

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,4 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 Sciences and National Academy of Medicine. 4 Member, National Academy of Medicine. PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION vii

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: Scott Aaronson, University of Texas at Austin, Kenneth R. Brown, Duke University, Jerry M. Chow, IBM Thomas J. Watson Research Center, William J. Dally, NAE, NVIDIA Corporation, Sean Hallgren, Pennsylvania State University, John P. Hayes, University of Michigan, Daniel Lidar, University of Southern California, John Manferdelli, Northeastern University, Anne Matsuura, Intel Labs, William H. Press, NAS, University of Texas at Austin, and Steven J. Wallach, NAE, Micron Technologies. 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. 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. PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION ix

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. 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. 1 M.A. Nielsen and I. Chuang, 2002, Quantum computation and quantum information 558-559. 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. 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. PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION xi

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 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 quickly get a 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 the 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. PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION xii

 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 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 (CSTB), 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 PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION xiii

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 PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION xiv

Contents SUMMARY ............................................................................................................................................. S-1  1 PROGRESS IN COMPUTING ........................................................................................................... 1-1  1.1  Origins of Contemporary Computing .......................................................................................................... 1-1  1.2  Quantum Computing ................................................................................................................................... 1-2  1.3  Historical Progress in Computing: Moore’s Law ........................................................................................ 1-3  1.4  Converting Transistors to Cheap Computers............................................................................................... 1-5  1.5  A Slow Down in Scaling ............................................................................................................................. 1-6  1.6  Quantum: A New Approach to Computing ................................................................................................. 1-7  2 QUANTUM COMPUTING: A NEW PARADIGM .......................................................................... 2-1  2.1  The Nonintuitive Physics of the Quantum World ....................................................................................... 2-1  2.2  The Landscape of Quantum Technology..................................................................................................... 2-3  2.3  Bits and Qubits ............................................................................................................................................ 2-5  2.3.1 Classical Computing: From Analog Signals to Bits and Digital Gates .............................................. 2-5  2.3.2 The Quantum Bit, or “Qubit” ............................................................................................................. 2-8  2.3.3 Multiqubit Systems........................................................................................................................... 2-10  2.4  Computing With Qubits ............................................................................................................................ 2-11  2.4.1 Quantum Simulation, Quantum Annealing, and Adiabatic Quantum Computation ......................... 2-13  2.4.2 Gate-Based Quantum Computing..................................................................................................... 2-13  2.5  Quantum Computer Design Constraints .................................................................................................... 2-18  2.6  The Potential for Functional Quantum Computers.................................................................................... 2-20  3 QUANTUM ALGORITHMS AND APPLICATIONS ...................................................................... 3-1  3.1  Quantum Algorithms for an Ideal Gate-Based Quantum Computer ........................................................... 3-2  3.1.1 The Quantum Fourier Transform and Quantum Fourier Sampling .................................................... 3-3  3.1.2 Quantum Factoring and Finding Hidden Structures ........................................................................... 3-5  3.1.3 Grover’s Algorithm and Quantum Random Walks ............................................................................ 3-6  3.1.4 Hamiltonian Simulation Algorithms .................................................................................................. 3-7  3.1.5 Quantum Algorithms for Linear Algebra ........................................................................................... 3-9  3.1.6 Required Machine Quality ............................................................................................................... 3-10  3.2  Quantum Error Correction and Mitigation ................................................................................................ 3-10  3.2.1 Quantum Error Mitigation Strategies ............................................................................................... 3-11  3.2.2 Quantum Error Correction Codes ..................................................................................................... 3-11  3.2.3 Quantum Error Correction Overhead ............................................................................................... 3-13  3.3  Quantum Approximation Algorithms........................................................................................................ 3-15  3.3.1 Variational Quantum Algorithms ..................................................................................................... 3-16  3.3.2 Analog Quantum Algorithms ........................................................................................................... 3-16  3.4  applications of a Quantum Computer ........................................................................................................ 3-17  3.4.1 Near-Term Applications of a Quantum Computer ........................................................................... 3-18  3.4.2 Quantum Supremacy ........................................................................................................................ 3-18  3.4.3 Applications for an Ideal Quantum Computer.................................................................................. 3-20  3.5  The Potential Role of Quantum Computers in the Computing Ecosystem ............................................... 3-20  PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION xv

4 QUANTUM COMPUTING’S IMPLICATIONS FOR CRYPTOGRAPHY .................................. 4-1  4.1  Cryptographic Algorithms in Current Use .................................................................................................. 4-1  4.1.1 Key Exchange and Asymmetric Encryption....................................................................................... 4-2  4.1.2 Symmetric Encryption ........................................................................................................................ 4-2  4.1.3 Certificates and Digital Signatures ..................................................................................................... 4-3  4.1.4 Cryptographic Hash Functions and Password Hashing ...................................................................... 4-4  4.2  Sizing Estimates .......................................................................................................................................... 4-5  4.3  Post-quantum Cryptography........................................................................................................................ 4-6  4.3.1 Symmetric Encryption and Hashing ................................................................................................... 4-7  4.3.2 Key Exchange and Signatures ............................................................................................................ 4-7  4.4  Practical Deployment Challenges................................................................................................................ 4-9  5 ESSENTIAL HARDWARE COMPONENTS OF A QUANTUM COMPUTER ........................... 5-1  5.1 Hardware Structure of a Quantum Computer ............................................................................................... 5-1  5.1.1 Quantum Data Plane ........................................................................................................................... 5-2  5.1.2 Control and Measurement Plane ........................................................................................................ 5-2  5.1.3 Control Processor Plane and Host Processor ...................................................................................... 5-3  5.1.4 Qubit Technologies ............................................................................................................................ 5-4  5.2 Trapped Ion Qubits ....................................................................................................................................... 5-4  5.2.1 Current Trapped Ion Quantum “Computers” ..................................................................................... 5-5  5.2.2 Challenges and Opportunities for Creating a Scalable Ion Trap Quantum Computer ........................ 5-5  5.3 Superconducting Qubits ............................................................................................................................... 5-7  5.3.1 Current Superconducting Quantum “Computers” .............................................................................. 5-7  5.3.2 Challenges and Opportunities for Creating a Scalable Quantum Computer ...................................... 5-8  5.4 Other Technologies .................................................................................................................................... 5-10  5.5 Future Outlook ........................................................................................................................................... 5-11  6 ESSENTIAL SOFTWARE COMPONENTS OF A SCALABLE QUANTUM COMPUTER...... 6-1  6.1 Challenges and Opportunities ....................................................................................................................... 6-1  6.2 Quantum Programming Languages .............................................................................................................. 6-2  6.2.1 Programmer-Facing (High-Level) Programming Languages ............................................................. 6-3  6.2.2 Control Processing (Low-Level) Languages ...................................................................................... 6-4  6.2.3 Software Library Support ................................................................................................................... 6-6  6.2.4 Algorithm Resource Analysis............................................................................................................. 6-6  6.3 Simulation .................................................................................................................................................... 6-7  6.4 Specification, Verification, and Debugging ................................................................................................. 6-8  6.5 Compiling from a High-Level Program to Hardware ................................................................................... 6-9  6.5.1 Gate Synthesis .................................................................................................................................. 6-11  6.5.2 Quantum Error Correction ................................................................................................................ 6-11  6.6 Summary .................................................................................................................................................... 6-12  7 FEASIBILITY AND TIME FRAMES OF QUANTUM COMPUTING ......................................... 7-1  7.1  The Current State of Progress ..................................................................................................................... 7-1  7.1.1 Creating a Virtuous Cycle .................................................................................................................. 7-2  7.1.2 Criticality of Applications for a Near-Term Quantum Computer ...................................................... 7-3  7.2 A Framework for Assessing Progress in Quantum Computing .................................................................... 7-4  7.2.1 How to Track Physical and Logical Qubit Scaling ............................................................................ 7-4  7.2.2 Current Status of Qubit Technologies ................................................................................................ 7-7  7.3 Milestones and Time Estimates .................................................................................................................... 7-9  7.3.1 Small (Tens of Qubits) Computer (G1) ............................................................................................ 7-11  7.3.2 Gate-Based Quantum Supremacy (G2a) .......................................................................................... 7-11  7.3.3 Annealer-Based Quantum Supremacy (A2) ..................................................................................... 7-12  7.3.4 Running QEC Successfully at Scale (G2b) ...................................................................................... 7-12  7.3.5 Commercially Useful Quantum Computer (A3/G3) ........................................................................ 7-13  PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION xvi

7.3.6 Large Modular Quantum Computer (G4) ......................................................................................... 7-14  7.3.7 Milestone Summary ......................................................................................................................... 7-15  7.4 Quantum Computing R&D ......................................................................................................................... 7-16  7.4.1 The Global Research Landscape ...................................................................................................... 7-16  7.4.2 Importance of Quantum Computing R&D ....................................................................................... 7-18  7.4.3 An Open Ecosystem ......................................................................................................................... 7-21  7.5 Targeting A Successful Future ................................................................................................................... 7-22  7.5.1 Cybersecurity Implications of Building a Quantum Computer ........................................................ 7-22  7.5.2 Future Outlook for Quantum Computing ......................................................................................... 7-22  APPENDIXES  A Statement of Task.................................................................................................................................. A-1  B Trapped Ion Quantum Computers ......................................................................................................... B-1  C Superconducting Quantum Computer ................................................................................................... C-1  D Other Approaches to Building Qubits ................................................................................................... D-1  E Global R&D Investment ........................................................................................................................ E-1  F Committee and Staff Biographical Information .................................................................................... F-1  G Briefers to the Committee ..................................................................................................................... G-1  H Acronyms and Abbreviations................................................................................................................ H-1  I Glossary ................................................................................................................................................... I-1  PREPUBLICATION COPY – SUBJECT TO FURTHER EDITORIAL CORRECTION xvii

Next: Summary »
Quantum Computing: Progress and Prospects Get This Book
×
Buy Paperback | $55.00
MyNAP members save 10% online.
Login or Register to save!
Download Free PDF

Quantum mechanics, the subfield of physics that describes the behavior of very small (quantum) particles, provides the basis for a new paradigm of computing. First proposed in the 1980s as a way to improve computational modeling of quantum systems, the field of quantum computing has recently garnered significant attention due to progress in building small-scale devices. However, significant technical advances will be required before a large-scale, practical quantum computer can be achieved.

Quantum Computing: Progress and Prospects provides an introduction to the field, including the unique characteristics and constraints of the technology, and assesses the feasibility and implications of creating a functional quantum computer capable of addressing real-world problems. This report considers hardware and software requirements, quantum algorithms, drivers of advances in quantum computing and quantum devices, benchmarks associated with relevant use cases, the time and resources required, and how to assess the probability of success.

  1. ×

    Welcome to OpenBook!

    You're looking at OpenBook, NAP.edu's online reading room since 1999. Based on feedback from you, our users, we've made some improvements that make it easier than ever to read thousands of publications on our website.

    Do you want to take a quick tour of the OpenBook's features?

    No Thanks Take a Tour »
  2. ×

    Show this book's table of contents, where you can jump to any chapter by name.

    « Back Next »
  3. ×

    ...or use these buttons to go back to the previous chapter or skip to the next one.

    « Back Next »
  4. ×

    Jump up to the previous page or down to the next one. Also, you can type in a page number and press Enter to go directly to that page in the book.

    « Back Next »
  5. ×

    To search the entire text of this book, type in your search term here and press Enter.

    « Back Next »
  6. ×

    Share a link to this book page on your preferred social network or via email.

    « Back Next »
  7. ×

    View our suggested citation for this chapter.

    « Back Next »
  8. ×

    Ready to take your reading offline? Click here to buy this book in print or download it as a free PDF, if available.

    « Back Next »
Stay Connected!