What would happen if a fully error corrected quantum computer of several thousands of logical qubits started working today? Public key infrastructures would fall down. The secrets of the world would be discovered. There would be chaos.
How far or close that day is? How would it affect our cryptography? What to do to protect our sensitive information ahead of the forthcoming arrival of quantum computers?

Scientists, politicians and businessmen from all over the world are worried about these questions as well. Last December, the publication division of the U.S. National Academies of Sciences, Engineering, and Medicine issued the first draft of the report Quantum Computing: Progress and Prospects. This document of more than 200 pages contains the consensus of the Committee on Technical Assessment of the Feasibility and Implications of Quantum Computing, whose members are several scientists and experts of the field. The report provides a judicious and scientific evidence-based exploration on what progress can be expected in the coming years, the actual threat they will represent and what strategy will need to be undertaken to be prepared for the clear arrival of the first fully functional quantum computer with thousands of qubits.

However, the question is not if there would be quantum computers or not, but when they will arrive and if they will catch us off-guard.
In this article I will summarize the most relevant conclusions reached by the committee. Of course, I encourage you to read the whole report.

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. 

Classical Computing works with bits, while Quantum Computing works with qubits. A classic bit has a well-defined value —‘1’ or ‘0’—, while a qubit is in a quantum superposition of states, that is, in a combination of both ‘1’ and ‘0’ at once. To achieve this, all the qubits need to be ‘entangled’, isolated from external environment and under an extremely precise control: What an engineering challenge!

Noise management differs greatly from one computational model to the other one. Since a classical bit is either ‘1’ or ‘0’, it is very easy to remove the noise that may be produced on logic gates. Nevertheless, considering that a qubit can be in a combination of ‘1’ and ‘0’, removing noise from physical circuits is very hard. This way, one of the greatest design challenges is the error rate: in 2018, the error rates for 2-qubit operations on systems with 5 or more qubits were higher than 1%.

Consequently, quantum error correction (QEC) algorithms are required to emulate a noise-free quantum computer (i.e. a fully error corrected quantum computer). Without QEC, it is unlikely that a complex quantum program, such as one that implements Shor’s algorithm to compromise RSA, would ever run correctly. The problem with QEC is that it requires:

1. a higher number of physical qubits to emulate more robust and stable qubits, called “logical qubits” and…
2. a higher number of primitive qubit operations that must be performed on physical qubits to emulate quantum operations on these logical qubits. In the short term, QEC incurs significant overheads, so we will only see ‘noisy’ computers.

Furthermore, it is far from simple to convert a large amount of classical data to a qubits’ quantum state. For problems that require large data inputs, the amount of time required to create the quantum input might exceed the computational complexity of the algorithm itself, so greatly reducing (or even removing) the quantum advantage.

Another challenge they face involves code debugging. Debugging methods for classical computers usually rely on memory examination, and the reading of intermediate states. However, a quantum state cannot be copied (because of the no-cloning theorem) for later examination. What if it could be directly read? Then, any measurement of a quantum state would collapse it to a specific value of classical bits, bringing computation to a halt. In other words, we are far from developing new debugging methods.

In summary, to build a quantum computer capable of successfully running Shor’s algorithm in a 2048-bit RSA public key requires building a machine that is five orders of magnitude larger than current machines and has error rates about two orders of magnitude lower, as well as developing a software development environment to support this machine.

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.

Since quantum computing is on everyone’s lips, some of the most powerful companies all around the world have embarked on the development of the first high-powered quantum computer. However, the current enthusiasm might wane if commercial applications for the technologies under development are not found (beyond breaking RSA in the future). If disruptive breakthroughs enabling the development of more sophisticated computers are made, the expected financial returns will stimulate more major companies and more research on the field.

Nevertheless, if the first commercially useful applications required a very large number of qubits, interest would only be preserved by means of public funding. In such a case, there would be a risk to fall into the “valley of death”, as well as to see the departure of talent towards more favorable fields from both industry and academia.

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.

Given the overhead of QEC, the first quantum computers in the short term will certainly have errors: they will be noisy intermediate-scale quantum (NISQ) computers. Currently, there are no applications for NISQ computers. As long as commercial applications for NISQ computers are not developed, the virtuous cycle of investment will not start.

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. 

The committee suggests monitoring the progress in this competition by the following metrics: the error rates of the 1-qubit and 2-qubit operations, the interqubit connectivity, and the number of qubits contained within a single hardware module.

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.

In this regard, the committee proposes using several metrics and milestones to help monitor the development of quantum computing. These milestones are illustrated in the following figure. 

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 in this field could lead to transformative new knowledge and applications.

The work on the design of new quantum algorithms can help progress foundational research on computing. This way, we can expect that research on quantum computing will similarly lead to new advances in other fields, such as physics, chemistry, biochemistry, material science, etc. These advances may, in turn, enable future advances in technology.

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 Quantum Computer 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.

Quantum computing and information findings are believed to enhance other quantum technologies.

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.

In fact, the U.S. is losing this leadership position, as it can be observed in the following figure, based on R&D investment.

Key Finding 9: An open ecosystem that enables cross-pollination of ideas and groups will accelerate rapid technology advancement.

This competition for creating the first quantum computer could drive the field to be less open in publishing research results in scientific journals and forums. It is required to find a balance between the natural protection of intellectual property and the open flow of information to ensure further development in the field.

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. 

A quantum computer with around 2,500 logical qubits could potentially defeat 2048-bit RSA encryption in no more than a few hours. Cryptographers have been working for decades on algorithms that are (believed to be) quantum-resistant. However, the problem is not so much the lack of alternatives to the RSA and the elliptic curves, but the transition from the old algorithms to the new ones; not to mention what would happen with those secrets intended to be confidential for many years. Since this transition may need decades to be completed, starting it must be the main priority, before the threat becomes a reality.

In the next entry we will explain how quantum computing affects current cryptography, in particular: what would happen with RSA, elliptic curves, digital certificates, Bitcoin and hashes. We will also see the cryptographic alternatives that are being considered for the post-quantum age.