Quantum computers are getting better and better at factoring large numbers. How much time is left until the dreaded Q-Day?

It's the specter of all intelligence agencies: a successful attack on the RSA cryptosystem. Governments, banks, and the military use this method to encrypt secret information that should never fall into the wrong hands. The RSA cryptosystem cannot be cracked with conventional computers. But the rapid development of quantum computers is making experts nervous.

Companies and governments around the world have therefore begun implementing new encryption methods that even quantum computers cannot break . The big question is: How much time remains until Q-Day, when quantum computers will be able to crack the RSA algorithm?

The security of the RSA algorithm is based on the fact that it is incredibly difficult to factor a large number into its prime factors, i.e., to find two prime numbers that, when multiplied, yield the desired number. For small numbers, the solution is easy to guess (for example, 33 = 3 × 11). However, the RSA-2048 algorithm uses numbers with more than 600 decimal places for encryption (which corresponds to 2048 bits in binary notation). Even the best supercomputers fail at this. The largest number that has been factored using RSA so far has 250 decimal places. The calculation took several months. Since computing time increases exponentially with the size of the number, supercomputers pose no threat.

Today's quantum computers are even further away from being able to factor a 2048-bit number. The record is currently held by Chinese researchers . By combining a classical algorithm with a quantum one, they recently factored the 25-digit number 1,034,879,359,475,633,166,138,643 (the result is 1,001,721,172,891×1,033,101,213,673).

Such records regularly make headlines – especially when they come from China. This is because they raise fears that quantum computers could significantly accelerate the decomposition of large numbers. This fear is not entirely unfounded. However, it is not always appropriate. Whether a quantum computer can calculate faster than a supercomputer also depends on the algorithm used.

It has been known since 1994 that quantum computers can pose a potential threat to the RSA algorithm. At that time, mathematician Peter Shor presented a factorization algorithm that uses certain quantum effects.

Shor was able to demonstrate that computation can be accelerated enormously by skillfully choreographing quantum effects. While the computing time with the best classical algorithms grows exponentially with the size of the number, with Shor's algorithm it only scales with a small power of the number size. In concrete terms, this means that if a quantum computer is capable of factoring a 250-digit decimal number, factoring a number with more than 600 decimal places is not an intractable task for it.

When Shor published his algorithm, quantum computers didn't yet exist. And today's quantum computers don't pose a threat to the RSA algorithm either. The largest number that has been factored so far using Shor's algorithm on a quantum computer is 21=3×7 . You don't even need a calculator for that.

The reason for this modest performance is that today's quantum computers are error-prone. Even the smallest disturbance can cause the special states of the quantum bits with which a quantum computer computes to decay. The more calculations performed, the greater the probability of producing an incorrect result. And decomposing large numbers requires a very large number of calculations.

In principle, we know what to do about it. By combining enough faulty quantum bits into a single unit, the errors that occur during the calculation can be corrected. Such fault-tolerant quantum computers are currently being developed by companies like IBM and Google . However, it will still take years before quantum computers can be built large enough to solve complex problems.

A different type of quantum computer might achieve the goal more quickly. The algorithm developed by Peter Shor requires a digital quantum computer that processes information in binary form. However, there are also quantum computers that operate analogously, i.e., with continuously changing physical quantities.

Such analog quantum computers have been offered by the Canadian company D-Wave since 2011. While they are not as versatile as their digital counterparts, they are less error-prone.

"Initially, D-Wave's quantum computers were ridiculed by academics," says Dennis Willsch of the Jülich Supercomputing Centre. That has since changed. "D-Wave's analog quantum computers can solve certain optimization problems better and often more energy-efficiently than today's digital quantum computers."

The task of factoring a number can also be reformulated into an optimization problem (by defining a cost function that is minimized by the desired prime numbers). A year ago, Roberto Sebastiani's group at the University of Trento succeeded in factoring the number 8,219,999. The result is 32,749×251. This is the largest number ever factored without significant input from a classical computer, says Sebastiani. His group used a D-Wave quantum computer with more than 5,000 quantum bits.

Could D-Wave's analog quantum computers pose a threat to the RSA algorithm before fault-tolerant digital quantum computers become available? "That depends on how the computing time scales," says Willsch. So far, only the Shor algorithm has been proven to be faster than the best classical algorithm known to date.

Together with other researchers, Willsch investigated the computational time of three factorization methods developed specifically for analog quantum computers. Like Sebastiani's group, he used a quantum computer from D-Wave with more than 5,000 quantum bits. In all three cases, the results suggest an exponential increase in computational time. This would mean that factoring large numbers cannot be significantly accelerated.

What Willsch's group hasn't yet investigated is the scaling behavior of hybrid methods like those used by the Chinese researchers. They used a classical algorithm for factoring. D-Wave's quantum computer only took over a particularly computationally intensive subtask.

"There's nothing wrong with hybrid techniques," says Sebastiani. "They're an attempt to get the best of both worlds." But it's almost impossible to quantify the respective contributions of quantum and classical computing to solving the problem. The crucial question of whether the hybrid approach delivers an exponential speed advantage is therefore not easily answered.

Willsch considers it unlikely that today's hybrid methods pose a threat to the RSA cryptosystem. However, he doesn't want to rule out the possibility of finding algorithms that scale better. "The opportunity for hybrid methods is definitely there," he concludes.

As long as such algorithms don't exist, digital quantum computers remain the greatest threat to the RSA algorithm. Q-day may even arrive sooner than previously thought. The Shor algorithm is constantly being improved, reducing the need for quantum bits.

For example, Google researcher Craig Gidney recently demonstrated that a fault-tolerant quantum computer with fewer than one million quantum bits would be sufficient to factor a number with 2048 binary digits. Previously, it was assumed that at least 20 million quantum bits would be needed. Perhaps even one hundred thousand quantum bits would be sufficient using efficient error-correction methods, such as those recently introduced by IBM .

Such unforeseen developments make it difficult to predict how much time remains for the transition to quantum-safe encryption methods. Gidney recommends that vulnerable cryptosystems be abandoned after 2030 and no longer permitted after 2035. While he doesn't expect sufficiently large quantum computers to exist by 2030, he prefers not to make security dependent on the slow pace of development.