Quantum mechanics, the subfield of physics that describes the behavior of very small particles, provides the basis for a new paradigm of computing. Quantum computing (QC) was first proposed in the 1980s as a way to improve computational modeling of the behavior of very small (“quantum”) physical systems. Interest in the field grew in the 1990s with the introduction of Shor’s algorithm, which, if implemented on a quantum computer, would exponentially speed up an important class of cryptanalysis and potentially threaten some of the cryptographic methods used to protect government and civilian communications and stored data. In fact, quantum computers are the only known model for computing that could offer exponential speedup over today’s computers.1
While these results were very exciting in the 1990s, they were only of theoretical interest: no one knew of a method to build a computer out of quantum systems. Today, nearly 25 years later, progress in creating and controlling bits of quantum information, or “qubits,” has advanced to the point that a number of research groups have demonstrated small
1 These early theoretical results demonstrated the unique potential power of quantum computers. The performance of all other known computing devices can be only polynomially faster than a very simple “universal” computer, a probabilistic Turing machine, according to the extended Church-Turing thesis. Quantum computers are the only known computing technology that violates this thesis. Nielsen, Michael A., and Isaac Chuang. “Quantum computation and quantum information.” (2002): 558-559. Kaye, Phillip, Raymond Laflamme, and Michele Mosca. An introduction to quantum computing. Oxford University Press, 2007.
proof-of-principle quantum computers. This work has reinvigorated the field and led to significant private sector investment.
WHY BUILDING AND USING A QUANTUM COMPUTER IS CHALLENGING
A classical computer uses bits to represent the values it is operating on; a quantum computer uses quantum bits, or qubits. A bit can either be 0 or 1, while a qubit can represent the values 0 or 1, or some combination of both at the same time (known as a “superposition”). While the state of a classical computer is determined by the binary values of a collection of bits, at any single point in time the state of a quantum computer with the same number of quantum bits can span all possible states of the corresponding classical computer, and thus works in an exponentially larger problem space. However, the ability to make use of this space requires that all of the qubits be intrinsically interconnected (“entangled”), well-isolated from the outside environment, and very precisely controlled.
Many innovations over the past 25 years have enabled researchers to build physical systems that are starting to provide the needed isolation and control for quantum computing. In 2018, two technologies are used in most quantum computers (trapped ions and artificial “atoms” generated by superconducting circuits), but many different technologies are currently being explored for the basic physical implementation of qubits, or “physical qubits.” Given the rapid progress in the field, and the large improvements still needed, it is too early to “bet” on one technology for quantum computing (see Chapter 5).
Even if one is able to make very high quality qubits, creating and making use of these quantum computers (QCs) brings a new set of challenges. They use a different set of operations than those of classical computers, requiring new algorithms, software, control technologies, and hardware abstractions.
Qubits Cannot Intrinsically Reject Noise
One of the major differences between a classical computer and a quantum computer is in how it handles small unwanted variations, or noise, in the system. Since a classical bit is either one or zero, even if the value is slightly off (some noise in the system) it is easy for the operations on that signal to remove that noise. In fact, today’s classical gates, which operate on bits and are used to create computers, have very large noise margins—they can reject large variations in their inputs and still produce
clean, noise-free outputs. Because a qubit can be any combination of one and zero, qubits and quantum gates cannot readily reject small errors (noise) that occur in physical circuits. As a result, small errors in creating the desired quantum operations, or any stray signals that couple into the physical system, can eventually lead to wrong outputs appearing in the computation. Thus, one of the most important design parameters for systems that operate on physical qubits is their error rate. Low error rates have been difficult to achieve; even in mid-2018, the error rates for 2-qubit operations on systems with 5 or more qubits are more than a few percent. Better error rates have been demonstrated in smaller systems, and this improved operation fidelity needs to move to larger qubit systems for quantum computing to be successful (see Section 2.3).
Error-Free QC Requires Quantum Error Correction
Although the physical qubit operations are sensitive to noise, it is possible to run a quantum error correction (QEC) algorithm on a physical quantum computer to emulate a noise-free, or “fully error corrected,” quantum computer. Without QEC, it is unlikely that a complex quantum program, such as one that implements Shor’s algorithm, would ever run correctly on a quantum computer. However, QEC incurs significant overheads in terms of both the number of physical qubits required to emulate a more robust and stable qubit, called a “logical qubit,” and the number of primitive qubit operations that must be performed on physical qubits to emulate a quantum operation on this logical qubit. While QECs will be essential to create error-free quantum computers in the future, they are too resource intensive to be used in the short term: quantum computers in the near term are likely to have errors. This class of machines is referred to as noisy intermediate-scale quantum (NISQ) computers (see Section 3.2).
Large Data Inputs Cannot Be Loaded into a QC Efficiently
While a quantum computer can use a small number of qubits to represent an exponentially larger amount of data, there is not currently a method to rapidly convert a large amount of classical data to a quantum state2 (this does not apply if the data can be generated algorithmically). For problems that require large inputs, the amount of time needed to create the input quantum state would typically dominate the computation time, and greatly reduce the quantum advantage.
2 While there are proposals for quantum random access memory (QRAM) that can perform this function, at the time of this report, there aren’t any practical implementation technologies.
Quantum Algorithm Design Is Challenging
Measuring the state of a quantum computer “collapses” the large quantum state to a single classical result. This means that one can extract only the same amount of data from a quantum computer that one could from a classical computer of the same size. To reap the benefit of a quantum computer, quantum algorithms must leverage uniquely quantum features such as interference and entanglement to arrive at the final classical result. Thus, achieving quantum speedup requires totally new kinds of algorithm design principles and very clever algorithm design. Quantum algorithm development is a critical aspect of the field (see Chapter 3).
Quantum Computers Will Need a New Software Stack
As with all computers, building a useful device is much more complex than just creating the hardware—tools are needed to create and debug QC-specific software. Since quantum programs are different from programs for classical computers, research and development is needed to further develop the software tool stack. Because these software tools drive the hardware, contemporaneous development of the hardware and software tool chain will shorten the development time for a useful quantum computer. In fact, using early tools to complete the end-to-end design (application design to final results) helps elucidate hidden issues and drives toward designs with the best chance for overall success, an approach used in classical computer design (see Section 6.1).
The Intermediate State of a Quantum Computer Cannot Be Measured Directly
Methods to debug quantum hardware and software are of critical importance. Current debugging methods for classical computers rely on memory, and the reading of intermediate machine states. Neither is possible in a quantum computer. A quantum state cannot simply be copied (per the so-called no-cloning theorem) for later examination, and any measurement of a quantum state collapses it to a set of classical bits, bringing computation to a halt. New approaches to debugging are essential for the development of large-scale quantum computers (see Section 6.4).
TIME FRAMES FOR ACHIEVING QUANTUM COMPUTING
Predicting the future is always risky, but it can be attempted when the product of interest is an extrapolation of current devices that does not span too many orders of magnitude. However, to create a quantum computer that can run Shor’s algorithm to find the private key in a 1024-bit
RSA encrypted message requires building a machine that is more than five orders of magnitude larger and has error rates that are about two orders of magnitude better than current machines, as well as developing the software development environment to support this machine.
The progress required to bridge this gap makes it impossible to project the time frame for a large error-corrected quantum computer, and while significant progress in these areas continues, there is no guarantee that all of these challenges will be overcome. The process of bridging this gap might expose unanticipated challenges, require techniques that are not yet invented, or shift owing to new results of foundational scientific research that change our understanding of the quantum world. Rather than speculating on a specific time frame, the committee identified factors that will affect the rate of technology innovation and proposed two metrics and several milestones for monitoring progress in the field moving forward (see Section 7.2).
Given the unique characteristics and challenges of quantum computers, they are unlikely to be useful as a direct replacement for classical computers. In fact, they require a number of classical computers to control their operations and carry out computations needed to implement quantum error correction. Thus, they are currently being designed as special-purpose devices operating in a complementary fashion with classical processors, analogous to a co-processor or an accelerator (see Section 5.1).
In rapidly advancing fields, where there are many unknowns and hard problems, the rate of overall development is set by the ability of the whole community to take advantage of new approaches and insights. Fields where research results are kept secret or proprietary progress much more slowly. Fortunately, many quantum computing researchers have been open about sharing advances to date, and the field will benefit greatly by continuing with this philosophy (see Section 7.4.3).
Key Finding 9: An open ecosystem that enables cross-pollination of ideas and groups will accelerate rapid technology advancement. (Chapter 7)
It is also clear that a technology’s progress depends on the resources, both human and capital, devoted to it. Although many people think that there will be a Moore’s law-type scaling for the number of qubits in a system, it is important to remember that Moore’s law resulted from a virtuous cycle, where improved technology generated exponentially increasing revenue, enabling reinvestment in research and development (R&D) and attracting new talent and industries to help innovate and scale the technology to the next level. As with silicon technology, a Moore’s law-type of sustained exponential growth for qubits requires an exponentially growing investment, sustaining this investment will likely require a similar
virtuous cycle for quantum computers, where smaller machines are commercially successful enough to grow investment in the overall area. In the absence of intermediate successes yielding commercial revenue, progress will depend on governmental agencies continuing to increase funding of this effort. Even in this scenario, successful completion of intermediate milestones is likely to be essential (see Section 1.3).
Given the overhead of QEC, near-term machines will almost certainly be noisy intermediate-scale quantum (NISQ) computers. While many interesting applications exist for large error-corrected quantum computers, practical applications for NISQ computers do not currently exist. Creating practical applications for NISQ computers is a relatively new area of research and will require work on new types of quantum algorithms. Developing commercial NISQ computer applications by the early 2020s will be essential to starting this virtuous cycle of investment (see Section 3.4.1).
Key Finding 3: Research and development into practical commercial applications of noisy intermediate-scale quantum (NISQ) computers is an issue of immediate urgency for the field. The results of this work will have a profound impact on the rate of development of large-scale quantum computers and on the size and robustness of a commercial market for quantum computers. (Chapter 7)
Quantum computers can be divided into three general categories or types. “Analog quantum computers” directly manipulate the interactions between qubits without breaking these actions into primitive gate operations. Examples of analog machines include quantum annealers, adiabatic quantum computers, and direct quantum simulators. “Digital NISQ computers” operate by carrying out an algorithm of interest using primitive gate operations on physical qubits. Noise is present in both of these types of machine, which means that the quality (measured by error rates and qubit coherence times) will limit the complexity of the problems that these machines can solve. “Fully error-corrected quantum computers” are a version of gate-based QCs made more robust through deployment of quantum error correction (QEC), which enables noisy physical qubits to emulate stable logical qubits so that the computer behaves reliably for any computation (see Section 2.6).
The first milestones of progress in QC were the demonstration of simple proof-of-principle analog and digital systems. Small digital NISQ computers became available in 2017, with tens of qubits with errors too
high to be corrected. Work in quantum annealing began approximately a decade earlier using qubits built with a technology that had lower coherence times but that allowed them to scale more rapidly. Thus, by 2017 experimental quantum annealers had grown to machines with around 2,000 qubits. From this starting point, progress can be identified with the achievement of one of several possible milestones. Demonstration of “quantum supremacy”—that is, completing a task that is intractable on a classical computer, whether or not the task has practical utility—is one. While several teams have been focused on this goal, it has not yet been demonstrated (as of mid-2018). Another major milestone is creating a commercially useful quantum computer, which would require a QC that carries out at least one practical task more efficiently than any classical computer. While this milestone is in theory harder than achieving quantum supremacy—since the application in question must be better and more useful than available classical approaches—proving quantum supremacy could be difficult, especially for analog QC. Thus, it is possible that a useful application could arise before quantum supremacy is demonstrated. Deployment of QEC on a QC to create a logical qubit with a significant reduction in error rate is another major milestone and is the first step to creating fully error-corrected machines (see Section 7.3).
Progress in gate-based quantum computing can be monitored by tracking the key properties that define the quality of a quantum processor: the effective error rates of the single-qubit and two-qubit operations, the interqubit connectivity, and the number of qubits contained within a single hardware module.
Key Finding 4: Given the information available to the committee, it is still too early to be able to predict the time horizon for a scalable quantum computer. Instead, progress can be tracked in the near term by monitoring the scaling rate of physical qubits at constant average gate error rate, as evaluated using randomized benchmarking, and in the long term by monitoring the effective number of logical (error-corrected) qubits that a system represents. (Chapter 7)
Tracking the size and scaling rate for logical qubits will provide a better estimate on the timing of future milestones.
Key Finding 5: The state of the field would be much easier to monitor if the research community adopted clear reporting conventions to enable comparison between devices and translation into metrics such as those
proposed in this report. A set of benchmarking applications that enable comparison between different machines would help drive improvements in the efficiency of quantum software and the architecture of the underlying quantum hardware. (Chapter 7)
Players Working to Build and Use a Quantum Computer
It is clear that efforts to develop quantum computers and other quantum technologies are under way around the world. It is expected that large, concerted research efforts entailing both foundational scientific advances and new strategies in engineering—spanning multiple traditional disciplines—will be required to build a successful QC.
Key Finding 8: While the United States has historically played a leading role in developing quantum technologies, quantum information science and technology is now a global field. Given the large resource commitment several non-U.S. nations have recently made, continued U.S. support is critical if the United States wants to maintain its leadership position. (Chapter 7)
Furthermore, the private sector currently plays a large role in the U.S. quantum computing R&D ecosystem.
Key Finding 2: If near-term quantum computers are not commercially successful, government funding may be essential to prevent a significant decline in quantum computing research and development. (Chapter 7)
QUANTUM COMPUTERS AND CRYPTOGRAPHY
Quantum computing will have a major impact on cryptography, which relies upon hard-to-compute problems to protect data. Shor’s algorithm running on a large quantum computer will greatly reduce the required computation (the workfactor) to extract the private key from the asymmetric ciphers used to protect almost all Internet traffic and stored encrypted data. There is strong commercial interest in deploying post-quantum cryptography well before such a quantum computer has been built. Companies and governments cannot afford to have their now-private communications decrypted in the future, even if that future is 30 years away. For this reason, there is a need to begin the transition to post-quantum cryptography as soon as possible, especially since it takes over a decade to make existing Web standards obsolete (see Section 4.4).
Key Finding 1: Given the current state of quantum computing and recent rates of progress, it is highly unexpected that a quantum computer that can compromise RSA 2048 or comparable discrete logarithm-based public key cryptosystems will be built within the next decade. (Chapter 7)
Key Finding 10: Even if a quantum computer that can decrypt current cryptographic ciphers is more than a decade off, the hazard of such a machine is high enough—and the time frame for transitioning to a new security protocol is sufficiently long and uncertain—that prioritization of the development, standardization, and deployment of post-quantum cryptography is critical for minimizing the chance of a potential security and privacy disaster. (Chapter 7)
Given the large risk a quantum computer poses to current protocols, there is an active effort to develop post-quantum cryptography, asymmetric ciphers that a quantum computer cannot defeat. These are likely to be standardized in the 2020s. While the potential utility of Shor’s algorithm for cracking deployed cryptography was a major driver of early enthusiasm in quantum computing research, the existence of cryptographic algorithms that are believed to be quantum-resistant will reduce the usefulness of a quantum computer for cryptanalysis and thus will reduce the extent to which this application will drive quantum computing R&D in the long term (see Section 4.3).
RISKS AND BENEFITS OF PURSUING QUANTUM COMPUTING
Significant technical barriers remain before a practical QC can be achieved, and there is no guarantee that they will be overcome. Building and using QCs will require not only device engineering but also fundamental progress at the convergence of a host of scientific disciplines—from computer science and mathematics to physics, chemistry, and materials science. Yet these efforts also offer potential benefits. For example, results from QC R&D have already helped to advance progress in physics—for example, in the area of quantum gravity—and in classical computer science by motivating or informing improvements in classical algorithms.
Key Finding 6: Quantum computing is valuable for driving foundational research that will help advance humanity’s understanding of the universe. As with all foundational scientific research, discoveries from this field could lead to transformative new knowledge and applications. (Chapter 7)
The challenges to creating a large, error-corrected quantum computer are significant. Successful quantum computation will require unprecedented control of quantum coherence, pushing the boundaries of what is possible by refining existing tools and techniques—or perhaps even by developing new ones. Related technologies, such as quantum sensing and quantum communication, that also rely upon quantum coherence control may also leverage these advances (see Section 2.2).
Key Finding 7: Although the feasibility of a large-scale quantum computer is not yet certain, the benefits of the effort to develop a practical QC are likely to be large, and they may continue to spill over to other nearer-term applications of quantum information technology, such as qubit-based sensing. (Chapter 7)
In addition to the intellectual and potential societal benefits of quantum computing, this field has implications for national security. Any entity in possession of a large-scale, practical quantum computer could break today’s asymmetric cryptosystems—a significant signals intelligence advantage. Awareness of this risk has launched efforts to create and deploy cryptographic-systems that are robust to quantum cryptanalysis, for which there are several candidates currently believed to be quantum safe. However, while deploying post-quantum cryptography in government and civilian systems may protect subsequent communications, it will not remove the security risk to prequantum encrypted data that has already been intercepted by an adversary, although the magnitude of this risk decreases as the arrival time of a QC capable of deploying Shor’s algorithm increases and the data becomes less relevant. Furthermore, new quantum algorithms or implementations could lead to new quantum cryptanalytic techniques; as with cybersecurity in general, post-quantum resilience will require ongoing security research.
But the national security issues transcend cryptography. The larger strategic question is about future economic and technological leadership. Historically, classical computing has had a transformative impact across society. While the potential for applying quantum algorithms to industrial and research applications has only begun to be explored, it is clear that quantum computing has the potential to transcend current computational boundaries. The potential to improve efficiency in many areas of computation suggests that supporting a robust QC research community in the United States is of strategic value.
Based on evaluation of publicly available information regarding progress to date in the field of quantum computing, the committee saw no fundamental reason why a large, fault-tolerant quantum computer could not be built in principle. However, significant technical challenges remain on the path to building such a system, and to deploying it to practical advantage for a valuable task. Furthermore, future decisions on funding levels, likely dependent on near-term successes and commercial applications, as well as the strength and openness of the research community both in the United States and abroad, will influence the timeline for achieving a practical computer in the public domain. Progress in the field can be tracked using the metrics proposed in Key Finding 3. Regardless of when—or whether—a large, error-corrected quantum computer is built, continued R&D in quantum computing and quantum technologies will expand the boundaries of humanity’s scientific knowledge, and the results yet to be gleaned could transform our understanding of the universe.