Projecting Qubit Realizations to the Cryptopocalpyse Date
RSA 2048 is predicted to fail by 2042-01-15 at 02:01:28.
Plan your bank withdrawals accordingly.
Way back in the ancient era of 2001, long before the days of iPhones, back when TV was in black and white and dinosaurs still roamed the earth, I delivered a talk on quantum computing at DEF CON 9.0. In the conclusion I offered some projections about the growth of quantum computing based on reported growth of qubits to date. Between the first qubit in 1995 and the 8 qubit system announced before my talk in 2001, qubits were doubling about every 2 years.
I drew a comparison with Moore’s law that computers double in power every 18 months, or as 2(years/1.5). A feature of quantum computers is that the power of a quantum computer increases as the power of the number of qubits, which is itself doubling at some rate, then two years, or as 22(years/2), or, in ASCII: Moore’s law is 2^(Y/1.5) and Gessel’s law is 2^2^(Y/2).
As far as I know, nobody has taken up my formulation of quantum computing power as a time series double exponential function of the number of qubits in a parallel structure to Moore’s law. It seems compelling, despite obviously having a few (minor) flaws. A strong counter argument to my predictions is that useful quantum computers require stable, actionable qubits, not noisy ones that might or might not be in a useful state when measured. Data on stable qubit systems is still too limited to extrapolate meaningfully, though a variety of error correction techniques have been developed in the past two decades to enable working, reliable quantum computers. Those error correction techniques work by combining many “raw” qubits into a single “logical” qubit at around a 10:1 ratio, which certainly changes the regression substantially, though not the formulation of my “law.”
I generated a regression of qubit growth along the full useful quantum computer history, 1998–2023, and performed a least-squares fit to an exponential doubling period and got 3.376 years, quite a bit slower than the heady early years’ 2.0 doubling rate. On the other hand, fitting an exponential curve to all announcements in the modern 2016–2023 period yields a doubling period of only 1.074 years. The qubit doubling period is only 0.820 years if we fit to just the most powerful quantum computers released, ignoring various projects’ lower-than-maximum qubit count announcements; I can see arguments for either though selected the former as somewhat less aggressive.
From this data, I offer a formulation of what I really hope someone else somewhere will call, at least once, “Gessel’s Law,” P = 22(y/1.1) or, more generally given that we still don’t have enough data for a meaningful regression, P = 22(y/d); quantum computational power will grow as 2 to the power 2 to the power years over a doubling period which will become more stable as the physics advance.
Gidney & Ekra (of Google) published How to factor 2048-bit RSA integers in 8 hours using 20 million noisy qubits, 2021-04-13. So far for the most efficient known (as in not hidden behind classification, should such classified devices exist) explicit algorithm for cracking RSA. The qubit requirement, 2×10⁷, is certainly daunting, but with a doubling time of 1.074 years, we can expect to have a 20,000,000 qubit computer by 2042. Variations will also crack Diffie-Hellman and even elliptic curves, creating some very serious security problems for the world not just from the failure of encryption but the exposure of all so-far encrypted data to unauthorized decryption.
Based on the 2016–2023 all announcements regression and Gidney & Ekra, we predict RSA 2048 will fall on 2042-01-15 at 2am., a prediction not caveated by the error correction requirement for stable qubits as they count noisy, raw, cubits as I do. As a validity check, my regression predicts “Quantum Supremacy” right at Google’s 2022 announcement.
