ARTICLE A question of when

Quantum computers are coming. Such devices will famously facilitate algorithms that solve certain specialized number-theoretic problems, and it just so happens that the hardness of solving these very problems lie at the heart of the cryptography that has enabled our modern online infrastructur. And so, a quantum apocalypse seems imminent for our digital world, although it is one that can be staved off by transitioning to quantum-safe cryptographic algorithms.

But when will the quantum apocalypse arrive? The answer to this question depends a lot on who you ask: The CEO of a venture-funded quantum technologies startup might answer «Within five years!», while a skeptical physics professor might insist «Not in our lifetime». The honest answer, of course, is «We don’t know!» But can we come up with a more useful one?

Well, we can make some educated guesses. To break RSA 2048—a «military-grade» secure encryption algorithm—one needs roughly 6000 qubits, that is «quantum bits», on which to implement the algorithm. In classical terms, this corresponds to less than a kilobyte of working memory.

Remembering that IBM’s largest quantum computer already has more than a thousand qubits might then leave the impression that RSA 2048 is doomed to fall, and soon.

However, these qubits are not stable, nor are they guaranteed to give the right output. Indeed, protecting the fragile quantum effects exploited by quantum algorithms is a tremendous engineering challenge, with the lifetime stability of a single qubit typically measured in milliseconds. For an algorithm expected to take hours to perform, this will not do.

This is where quantum error-correction comes to the rescue. These procedures encode the information of a single qubit across several qubits, and uses quantum effects such as superposition and entanglement to protect the information encoded in the qubits from interference from the surrounding environment. But to keep an algorithm stable through several hours of execution, a lot of extra qubits is needed per protected qubit. The best estimates for breaking modern cryptography requires on the order of 10 million qubits, translating to roughly 10,000 physical qubits per protected qubit.

But now we have a current status (quantum computers with one thousand imperfect qubits) and a starting point for the quantum apocalypse (10 million imperfect qubits), which means that we can start to make predictions. Moore’s law for classical computers say that the number of bits (meaning transistors) on a chip double roughly every two years—an exponential development. And quantum computers have so far followed a similar law:

In this figure, the x-axis shows linear time, and the y-axis shows an exponentially increasing number of qubits, so that straight lines equate to exponential growth. The stars (slightly outdated) represent quantum devices that have been built, and the green ring represents our current status: A device with one thousand imperfect qubits in 2024. From this, one can draw two lines, one «optimistic» and one «pessimistic» extrapolation (or «pessimistic» and «optimistic», depending on whose team you are on), and ask the question: When will we hit that crucial 10 million qubits? And from the figure we get two answers: In twenty years, and in forty years. So, «RSA 2048 will be broken sometime between twenty and forty years from now» appears to be a reasonable guess.

However, this estimate is making a lot of assumptions. In what ways could it be wrong? Well, first, the number «10 million qubits» could (and likely will) go down, as theoretical developments in quantum error correction make the overhead needed to protect qubits smaller, and algorithmic developments continue to make the quantum algorithms themselves more efficient (which again leads to smaller overhead in error correction). As an example of the latter, a variant of the factoring algorithm was discovered last year that decreases the number of quantum resources needed to factor composite numbers, which breaks RSA. This increased efficiency is achieved by running the algorithm multiple times in parallel, instead of only once in sequence, and off-loading parts of the computation to classical supercomputers, which have no such stability issues. If developments like this were to decrease the necessary number of qubits needed from 10 million to, say, one million, then our estimates for when RSA 2048 will be broken suddenly reduces by roughly ten years, to ten years from now «optimistically», and thirty years  from now «pessimistically».

Second, technological developments might yield unexpected breakthroughs. As an example, the superconducting qubits pioneered by companies such as IBM and Google, which have until now been leading the charge, seem to have recently been overtaken by an unexpected «underdog» technology, namely neutral atoms, on which the first convincing demonstrations of quantum error correction in action were displayed late last year.

Finally, a theoretical possibility, yet to be achieved in the lab, come in the form of topological qubits, which through exotic material properties would be able to error-correct themselves, doing away with the need for the massive error-correction overhead. This means that six thousand topological qubits really would suffice to break RSA 2048. If such a topological qubit were demonstrated in the lab tomorrow, a lot of prognoses would have to be revised overnight, and suddenly the (oft-repeated) claim that the quantum apocalypse is only five years away might sound a lot less unconvincing.

Regardless of whether large-scale quantum computers are five, twenty, or fifty years away, there are good reasons to transition to quantum-safe cryptography now. There is little that is certain about the future of quantum computing, but one thing seems clear: Quantum computers will arrive, and our current cryptography will be broken. It is not a question of if—just a question of when.