“Q-Day” is the term some experts use to describe when large-scale quantum computers are able to factorize the large prime numbers that underlie our public encryption systems, such as the ones that are supposed to protect our bank accounts, financial markets, and most vital infrastructure. That’s a feat that’s all but impossible for even the fastest supercomputers but which the unique features of quantum computers, using the physics of superpositioning and entanglement, will be able to deliver.
There’s a growing consensus that this quantum threat is real; there’s no agreement how long it will take before a quantum computer has the 4000 or so stable qubits it will need to meet the requirements of Shor’s algorithm for cracking those encryption systems.
For example, it would take a classical computer 300 trillion years to crack an RSA-2048 bit encryption key. A quantum computer can do the same job in just ten seconds with 4099 stable qubits—but getting to that number is the main problem quantum computer engineers face since the stability or coherence of qubits lasts only for microseconds. Today’s most entangled computer, Google’s Bristlecone, has just 72 stable qubits.
Nonetheless, I have been arguing for the past four years, including in this column, that Q-Day is likely to come sooner than even quantum scientists can predict, and that the time to get ready to protect our vulnerable data and networks is now. Others prefer to procrastinate, citing other experts who say such a threat is at least a decade or more away. The fact that the National Institute of Standards and Technology won’t have its quantum-resistant algorithm standards ready until 2024, and to space out for another five to fifteen years, has helped to encourage complacency disguised as confidence.
But new developments in quantum science suggest that this complacency is misplaced. If the large-scale quantum computer is the ultimate thermonuclear device in cyberwarfare, the dirty bomb is the quantum annealer—and it’s probably going to be here sooner than even experts thought.
So-called quantum annealers like the one Canada-based D-Wave Systems, Inc. uses, are able to calculate the lowest energy level between the qubits’ different states of entanglement, which equals the optimal solution. These machines have proven their worth in solving optimization problems that usually stump classical computers, as I explained
Not surprisingly, scientists have been quietly finding ways to turn factorization—the decryption process that leads to Q-Day—into an optimization problem instead of relying Shor’s algorithm, the paradigm for discussing quantum decryption since the 1990’s. In 2019 scientific papers emerged that showed how to do this, including factorizing integers using “noisy” qubits, i.e. swarms of quantum bits that aren’t perfectly entangled the way a large-scale computer requires.
One was authored by Chinese scientists who found a way to factor a large number using only 89 noisy qubits. it’s possible to factorize a RSA-768 encryption number—the current factorization record using classical computers—with 147,454 noisy qubits. That’s a tiny fraction of the millions of qubits a large quantum computer would need to reach the 4000 stable qubit threshold, and within reach of the architecture of an annealer like D-Wave Systems.
That same year a pair of researchers from Google and the Royal Institute of Technology at Stockholm showing how to crack 2028-bit RSA integers in 8 hours using 20 million noisy qubits. Given the fact that in 2012 scientists speculated that it would take 1 billion qubits to perform this feat, it won’t be long before researchers show they can get there with a lot fewer than 20 million qubits.
Sure enough, in 2020 three Chinese researchers found a way to use the D-Wave quantum computer to factorize large integers, that completely bypasses Shor’s algorithm. “Thus,” , “post-quantum cryptography should consider further the potential of the D-Wave quantum computer for deciphering the RSA cryptosystem in future.”
In effect, these researchers found a way to turn decryption using quantum technology into a straightforward process on a timeline much shorter than ten years: perhaps four to five years is more likely.
This was what Chinese scientists are openly publishing. We don’t know what’s happening behind the scenes, but we can bet if there’s a short cut to achieve what a large-scale quantum computer can do using annealing technology, their military and intelligence services will want to find out.
All this changes the timetable for Q-Day significantly, and our strategic calculations. Not only is quantum-based decryption coming our way sooner, but thanks to annealing that code-breaking feature will be more accessible to other machines than the hugely expensive large-scale computers Google, Microsoft, and others are working on—which puts the threat within reach of small-state or even non-state actors.
That’s why the dirty bomb analogy is so apt. Why gamble with the quantum future? Annealing technology makes getting quantum ready more important, and getting started now, more imperative than ever.
Read in