FYI -- Pretty readable description of the current (unclassified) state of the art. You can download this report for free after some negotiation (at least in the U.S.). http://nap.edu/25196 Quantum Computing: Progress and Prospects National Academy of Sciences 206 pages PDF file 9.3 MB 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 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 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