Are Quantum Computers a Real Threat?

A Question from a Concerned Client

Earlier this year, one of our clients, a major critical infrastructure provider, posed a forward-thinking question: “Do we need to worry about quantum computers breaking our security?” They were aware of Cyber Agency’s efforts on building cutting-edge security testbeds and have assumed we could build them a quantum computer to test this question. Quantum computing was a hot topic in academic circles and occasionally in the tech press, but it felt like science fiction to many of us in cybersecurity. Nonetheless, we embarked on a 9-month research project – consulting with physicists and cryptographers, visiting university labs, and pouring over the latest papers – to evaluate the real threat posed by quantum computers to our clients’ security.

With the client’s permission, I am able to share a few core lessons learned from that effort. Spoiler: we concluded that quantum computers are not a real threat anytime soon – on the order of 30 to 50 years out, if at all.

What Exactly Is a Quantum Computer?

First, a quick primer. A quantum computer isn’t just a super-fast classical computer; it’s a completely different model of computing based on quantum physics. Instead of bits (0 or 1), quantum computers use qubits that can exist in a superposition of 0 and 1 at the same time. In essence, a qubit can encode a combination of states simultaneously, and multiple qubits can exhibit entanglement – a mysterious quantum correlation that links their states. By exploiting superposition and entanglement, a quantum computer can process certain computations in parallel in ways a classical machine cannot.

The excitement (and fear) around quantum computing is that some problems which are practically impossible for classical computers might be solved exponentially faster on a quantum computer. However, it’s important to note that quantum computers are not magic speed machines for all tasks. Their advantage seems to apply only to specific problems with special structure. In fact, only a handful of quantum algorithms with major speedups are known; aside from a few cases like factoring numbers and unstructured search, no one expects quantum computers to accelerate arbitrary computations or replace classical PCs. So, while quantum hardware is (in theory) revolutionary, it won’t make every computation instantaneous – its threat (and promise) is very targeted.

Shor’s Algorithm

The biggest reason security folks worry about quantum computers is Shor’s algorithm. Back in 1994, mathematician Peter Shor stunned the world by discovering a quantum algorithm that can efficiently factor large integers. Why does that matter? Because the security of popular public-key encryption schemes like RSA and Diffie-Hellman relies on the fact that factoring huge numbers (hundreds or thousands of bits long) is virtually impossible with classical computers. Shor’s algorithm changes the game by solving the factoring problem in polynomial time on a quantum computer. In theory, a quantum computer running Shor’s algorithm could break RSA, DSA, and even elliptic-curve cryptography by cracking their underlying hard math problems.

To put it plainly: if a sufficiently powerful quantum computer existed today, it could find the secret keys for an RSA-encrypted message very quickly, defeating the encryption. Shor’s breakthrough was the “killer app” for quantum computing in the eyes of the NSA and cryptographers – it showed that our foundational public-key algorithms could collapse once quantum computing becomes practical. This realization in the late 90s kicked off serious interest in quantum computing research, much of it funded by governments worried about securing data against future quantum threats.

However, and this is critical, beating RSA with Shor’s algorithm requires a large, reliable, quantum computer. Shor’s algorithm is only a threat if we can build a machine capable of running it at scale. While many are trying, there is a question that everyone seems to be asking – would we ever be able to build something like that?

What About Symmetric Encryption? (Grover’s Algorithm)

Shor’s algorithm targets asymmetric crypto (RSA, Diffie-Hellman, ECC), but what about symmetric encryption and hashing (like AES or SHA)? Here, another quantum algorithm comes into play: Grover’s algorithm. Lov Grover discovered in 1996 that a quantum computer could brute-force search an unsorted list in roughly the square root of the number of steps a classical computer would need. Applied to cryptography, Grover’s algorithm can theoretically find a secret key by trying possibilities in √N time instead of N. This means it effectively halves the strength of symmetric keys. For example, a 128-bit AES key, which would take 2¹²⁸ tries to brute-force classically, could be broken in on the order of 2⁶⁴ operations on a quantum computer using Grover’s method.

Before we panic: 2⁶⁴ is still a huge number, so even with Grover’s speedup, 128-bit keys remain impractical to brute force (for now). And the obvious countermeasure is simply to use larger keys. So, while Grover’s algorithm means we need to bolster symmetric algorithms, it’s not an existential threat; it’s manageable by evolving our standards (unlike Shor’s algorithm, which outright breaks currently used public-key schemes).

The State of Quantum Computing

So quantum algorithms are a serious concern if we have quantum computers to run them. What is the reality of quantum hardware today? In short: it’s in the laboratory experiment phase, with only very small quantum processors achieved, and they are a far cry from breaking any real cryptography.

A landmark experiment occurred in 2001, when IBM researchers demonstrated Shor’s algorithm on a 7-qubit quantum computer, successfully factoring the number 15 (=3×5) . Yes, they cracked “15” – hardly a threat to RSA 2048-bit keys! This was done using an NMR (nuclear magnetic resonance) quantum computer, basically manipulating molecules in a test tube. While scientifically historic, the IBM experiment underscored how primitive and limited current quantum computers are. Seven qubits were used to factor a two-digit number, and even that worked only under pristine laboratory conditions. Each additional qubit is harder to control than the last; scaling from 7 qubits to even 20 or 30 is an enormous engineering challenge.

In fact, as of today the record for quantum computing is on the order of 5-7 qubits entangled in a controllable way. Researchers have tried different physical implementations – NMR in liquids, trapped ions, superconducting Josephson junctions, quantum dots – but all are struggling to maintain coherence as the system grows. Just this year, a team at Oxford/York demonstrated an NMR quantum computer using parahydrogen that realized a pure state with a handful of qubits. And a group in Austria teleported quantum states between trapped ions – a cool result that might help with quantum networks, but again involving only a pair of ions.

The bottom line: we are nowhere near the scale needed to run Shor’s algorithm on meaningful numbers. The quantum hardware we can build in 2004 can maybe factor 15 – toy problems. Going from these few-qubit systems to the thousands or millions of qubits required to threaten RSA is a gigantic leap. Quantum bits are extremely fragile – any interaction with the environment (even a stray electromagnetic wave or a slight temperature fluctuation) can cause decoherence, essentially scrambling the qubits and ruining the computation. To do lengthy calculations, a quantum computer must continually correct errors. Some experts estimate that beating classical cryptography might require on the order of millions of qubits once you account for error-correction overhead. Building and controlling such a complex machine is a monumental task – arguably one of the hardest engineering challenges ever. Going to the moon is child’s game in comparison.

Our Findings from Research and Expert Opinions

Over the past 9 months, we spoke with leading academics in quantum computing and cryptography. We visited a physics institute where a primitive ion-trap quantum computer was being tested, and we also talked to researchers working on superconducting qubits. The consensus we heard was reassuring: quantum computers are real and promising, but a practical, cryptographically relevant quantum computer is decades away.

One senior quantum physicist told us, half-jokingly, “Ask me again in 50 years.” Others admitted that, while there’s been steady progress in demonstrating basic principles, there are no known breakthroughs on the horizon that would suddenly jump us from 7 qubits to 1000 qubits. Progress in quantum computing seems to be incremental – adding a few qubits per decade, solving more small demonstration problems, but with many hurdles to scale. The general feeling in the community is that a working, large-scale quantum computer capable of running Shor’s algorithm on RSA-sized numbers is at least 20-30 years away, if not more. In fact, when quantum research at major labs began some years ago, the standard answer to “how long until a real quantum computer?” was “at least 30 to 50 years“.

It’s also worth noting that quantum computing is not the only quantum tech in town. Quantum cryptography (specifically Quantum Key Distribution, QKD) is a different application of quantum physics that actually enhances security rather than breaks it. Interestingly, this year saw the world’s first bank transfer secured by quantum key distribution in Vienna, Austria (a ~500 m fiber link protected by quantum-encrypted keys) – a reminder that quantum advances can help the good guys too. However, QKD addresses key exchange; it doesn’t mitigate the risk of quantum computers breaking algorithms like RSA in the future. For that, the long-term solution being discussed in academic circles is developing post-quantum cryptography – new encryption algorithms that even a quantum computer couldn’t easily solve. Those techniques are still mostly experimental, but it’s a budding field spurred by the knowledge of Shor’s algorithm.

So, Are Quantum Computers a Threat Now?

Our conclusion, in 2004, is that quantum computers are not an imminent threat to cybersecurity. They are a fascinating technology and potential threat in the long term, but certainly not something that keeps me awake at night today. For our clients such as governments and critical infrastructure operators, the prudent advice is to stay informed and begin long-range planning, but there’s no need to panic or overhaul cryptographic systems yet.

Based on what we learned:

• Timeline: We estimate it will likely take on the order of 30 to 50 years for quantum computers to advance to the point of threatening common cryptography. It could happen sooner or later (predicting technological breakthroughs is tricky), but all signs indicate a multi-decade timeline. As of now, commercial quantum computers are still many years away and confined to labs.
• Current Vulnerabilities: There is zero evidence that any government or adversary has a quantum computer capable of breaking RSA or AES today. If such a machine existed (even a small one), we’d see telltale publications or at least rumor mill chatter. Instead, what we see are papers factoring 15 – nothing close to real crypto. The largest integers factored by a quantum computer are trivial (two digits), and even optimistic researchers concede that huge improvements are needed to factor, say, a 1024-bit RSA key.
• Preparation: That said, being proactive is wise. We recommend our clients start migrating to longer key lengths in the coming years, which buys extra safety margin. Fortunately, doubling an RSA key size or using larger elliptic curves has negligible downside today and guards against both classical and future quantum attacks. Likewise, using AES-256 instead of AES-128 ensures confidentiality even under Grover’s algorithm (which would reduce AES-256 to ~128-bit strength). These measures are cheap insurance. We’re also keeping an eye on the development of quantum-resistant algorithms. While not urgent for deployment yet, within the next decade or two the industry will likely start standardizing post-quantum cryptography – long before quantum computers exist that could force a sudden scramble.

In summary, quantum computing is an exciting field and one day it will change the landscape of cryptography. But as of 2004, it remains a nascent technology with enormous practical challenges to overcome. The threat is real but long-term. Our clients do not need to lose sleep over quantum attacks right now; there are far more pressing threats (like malware, software exploits, and poor key management) to worry about in day-to-day security.