[Crossposting from https://blog.jessriedel.com/2020/09/15/quantum-computing-timelines/ ]

IN SHORT: We attempt to forecast when quantum computers will be able to crack the common cryptographic scheme RSA2048, and develop a model that predicts less than 5% confidence that this capability will be reached before 2039. You can read the full article at https://arxiv.org/abs/2009.05045

Advanced quantum computing comes with some new applications as well as a few risks, most notably threatening the foundations of modern online security.

In light of the recent experimental crossing of the "quantum supremacy" milestone, it is of great interest to estimate when devices capable of attacking typical encrypted communication will be constructed, and whether the development of communication protocols that are secure against quantum computers is progressing at an adequate pace.

Beyond its intrinsic interest, quantum computing is also fertile ground for quantified forecasting. Exercises on forecasting technological progress have generally been sparse — with some notable exceptions — but it is of great importance: technological progress dictates a large part of human progress.

To date, most systematic predictions about development timelines for quantum computing have been based on expert surveys, in part because quantitative data about realistic architectures has been limited to a small number of idiosyncratic prototypes. However, in the last few years the number of device has been rapidly increasing and it is now possible to squint through the fog of research and make some tentative extrapolations. We emphasize that our quantitative model should be considered to at most augment, not replace, expert predictions. Indeed, as we discuss in our preprint, this early data is noisy, and we necessarily must make strong assumptions to say anything concrete.

Our first step was to compile an imperfect dataset of quantum computing devices developed so far, spanning 2003-2020. This dataset is freely available, and we encourage others to build on it in the future as the data continues to roll in.

To quantify progress, we developed our own index - the generalized logical qubit - that combines two important metrics of performance for quantum computers: the number of physical qubits and the error rate for two-qubit gates. Roughly speaking, the generalized logical qubit is the number of noiseless qubits that could be simulated with quantum error correction using a given number of physical qubits with a given gate error. Importantly, the metric can be extended to fractional values, allowing us to consider contemporary systems that are unable to simulate even a single qubit noiselessly.

To forecast historical progress into the future, we focus on superconducting-qubit devices. We make our key assumption of exponential progress on the two main metrics and use statistical bootstrapping to build confidence intervals around when our index metric will cross the frontier where it will be able to threaten the popular cryptographic protocol RSA 2048.

Note that since we are modelling progress on each metric separately we are ignoring the interplay between the two metrics. But a simple statistical check shows that the metrics are likely negatively correlated within each system - that is, quantum computer designers face a trade off between increasing the number of qubits and the gate quality. Ignoring this coupling between the metrics results in an optimistic model.

Our main result: the 5%, median and 95% confidence extrapolation for the generalized logical qubit metric using a bootstrapping procedure. The 4100 threshold is where we estimate quantum computing will be able to solve the popular cryptographic scheme RSA-2048. Past recorded values of the metric are shown as purple icons on the graph.

As a point of comparison, last year Piani and Mosca surveyed quantum computing experts and found that 22.7% think it is likely or highly likely that quantum computers will be able to crack RSA-2048 keys by 2030, and 50% think that is likely or highly likely that we will be able to crack RSA-2048 keys by 2035.

Will this be enough time to deploy adequate countermeasures? I discuss this in depth in this other article about quantum cryptanalysis. Given the current rate of progress on the standardization of quantum-resistant cryptography there seems to be little reason for concern (though it should be considered that the yearly base rate for discontinuous breakthroughs for any given technology is about 0.1%).

A plausible timeline of development and deployment of a quantum-resistant cryptography standard, for illustrative purposes. Also shown a summary of expert prediction on attack capabilities. As comparison, our statistical prediction assigns <5% confidence to having quantum computing hardware capable of breaking RSA 2048 before 2039. This figure originally appeared on Assessing the impact of quantum cryptanalysis. The figure is based on an interview with the leader of NIST's Cryptographic Technology Group Lily Chen and educated guesswork.

If you are interested in better understanding our model and assumptions, I encourage you to check out our preprint on the arXiv.