Q-day is coming, ready or not!

We have known for a decade that quantum computers, someday, will be able to break the world’s encryption. Someday is closer than the world thinks.

Quantum computers hovering malevolently over a datascape. Image AI-generated by the autor.

**Non-members: read for free here.**

I’m sure you’ve heard about quantum computers. How they’re the most powerful computers the world has ever seen; how they’re going to make all other computers obsolete; how they’re going to crack all the world’s encryption and lay all our secrets bare.

I’m sure you’ve also heard the other side of the story: that they’ll never do anything useful, that they can’t be made to work reliably, and they’re inflating a hype bubble even bigger that AI.

The truth is: none of these statements is entirely true. Oh, except that one about breaking encryption. That bit is true. Actually, it’s just around the corner.

The first thing you need to understand about a quantum computer is: it’s not simply a very powerful computer. Actually, it’s nothing like anything you’d probably conceive a computer to be. Not only is it made of fundamentally different stuff to a normal, digital computer (which works by electricity); what it does is completely different as well. Check out this video if you’re interested:

[embed]

It might help you to know that normal digital computers are actually not very good at computation. Most of what they do is simply moving data from place to place. From time to time they do a little arithmetic. Occasionally, they do some proper computation, but in general they’re so bad at it that we have to build specialist devices to help them out, like GPUs and TPMs.

But even these specialist chips are still bound by the fundamental principles of digital computation. Impressive and awe-inspiring as these machines are, there are some things they just can’t do. It’s not that we haven’t yet built machines big enough or fast enough: these tasks are absolutely, theoretically, unavoidably impossible.

This is what makes computer cryptography possible. The basic idea is: you wrap up your secret message inside a problem which is impossible to solve unless you already have part of the solution. The part you have (and that someone else doesn’t have) is the key.

There are lots of different cryptographic tasks, but here are two examples:

• You can decrypt a message only if you have the exact key that was used to encrypt it.
• You can use a public key to check someone’s signature, but you can forge the signature only if you have the corresponding private key.

Quantum computers, not being digital things at all, aren’t constrained by the same rules. You won’t be surprised to learn that quantum computers are rubbbish at most of the things digital computers do well (and always will be). But some “impossible” tasks can be solved by a quantum computer easily. Those are the tasks that make all that quantum computer research worthwhile.

Honestly: it’s not hype. We’ve built quantum computers. They work. Not perfectly, and there are still technical problem to solve, but they work well enough that they’re starting to solve real problems. There are companies out there making them and selling them to real customers.

[embed]BBC Inside Science - Is quantum computing having its moment? - BBC Sounds Catch up on your favourite BBC radio show from your favourite DJ right here, whenever you like. Listen without limits…www.bbc.co.uk

It turns out that some of these “impossible” cryptographic tasks aren’t impossible at all when you’ve got a quantum computer. Actually they’re borderline-easy — and (as we will see) getting easier all the time.

To be clear: not all of our cryptography is quantum-crackable. Most of today’s hashing (the tamperproof seals on messages, the “chain” in blockchain) are probably going to be fine. There’s good reason to believe that symmetric key ciphers (how your web pages are encrypted, how databases are kept secure) are quantum-safe. (There are quantum algorithms for both, but they use unfeasibly large machines to deliver results in mere quadrillions of years.)

But there are two common and crucial cryptographic tasks which are considered highly vulnerable:

• Asymmetric key ciphers (the things that give us signatures and authentication).
• Key-exchanges (which is how two computers can secretly agree on a completely random symmetric key).

Does it even matter if our cryptography gets cracked? After all, you only care about secrecy if you’ve got something to hide, right? The internet worked just fine back in the day before browsers grew those little padlocks.

Umm, no. In the old days of (what we now call) Web 1.0, the internet was a simple affair, a sort of electronic print shop. Websites were like brochures, offering the most minimal of interactivity. Some businesses offered an email address, and some customers could even use it. But we all know how well email has aged, don’t we?

Web 2.0, today’s internet, is much more complicated. Now we have personal (and highly compromising) information flying in all directions. Today we buy and sell on the internet, we do our banking on the internet, we interact with health services on the internet, and we even engage with government services over the internet. And that’s just the consumer-level stuff. We use the internet to control physical supply lines, energy distribution, factories and hospitals. The internet controls everything from emergency response services and air traffic control down to the individual light bulbs in your house.

It is absolutely essential that the people (and machines) we’re speaking to really are who we think they are (and not some villainous intermediary); it’s absolutely essential that they can believe the same of us; and it’s absolutely essential that the contents of the conversations are kept both confidential and unaltered. Without those guarantees, the modern world couldn’t possibly continue to exist. (Incidentally that’s why the demands of the world’s authoritarian, autocratic, and insecure governments to “weaken” the internet’s security — in the name of catching criminals— is so wrong-headed. Weaken it here, you weaken it everywhere. If the police can crack the codes, so can anyone else).

Imagine what the world would be like without effective encryption. How would our hospitals and factories and airports and supermarkets and everything else work if there were no locked doors anywhere? What kind of a world would it be if anybody could impersonate anybody else, without any possibility of detection? Think about this for a moment, because, unless we all start to take the quantum threat seriously, that’s what’s going to happen.

The $64,000 question is, of course: when is this going to happen? I’m afraid, nobody really knows, but we can make some educated guesses.

There are two converging forces at work. On the one hand, quantum computing hardware is improving all the time. We measure the power of a quantum computer by asking how many qubits it has, multiplied by how long they can stay stable. Some technologies can deliver only a few very stable bits, others deliver loads of short-lived qubits. But they are more-or-less equivalent: we can group physical bits together into error-correcting logical qubits which together remain stable for longer. That is, we can trade width for stability. Generally we compare algorithmic power by counting equivalent short-lived qubits.

Since the first one was switched on in 2001, on average quantum computers doubled in size every eighteen months. In 2022, the industry switched from increasing width to improving stability, and the rate of improvement is now doubling every ten months. IBM now has a roadmap to a million-qubit-equivalent superconducting machine by 2030: their physics is reasonable and all the signs are that they’re on target. But even if their strategy doesn’t work, there are other kinds of machine that are on more-or-less the same trajectory.

The other force is the constant improvement in algorithms. The milestone is RSA2048. When we can crack that efficiently, we will have just cracked, or will be very close to cracking, almost everything else in our current ecosystem. Cracking RSA2048 is colloquially known as Q-day.

This is the story so far:

• In 2003, Beauregarde showed that a classic foundational algorithm, Shor’s, could be used to crack RSA2048 using (in modern terms) 170 million qubits, taking about a month. In 2018, Peter Shor (yes, same chap) bet his colleague Gil Kalil even money that RSA2048 would be cracked by 2048. This wasn’t really a difference of opinion: it was a fun bet: 50:50 either way. It more or less matched the hardware trajectory we’ve already mentioned.
• Then, in 2019, Gidney and Ekera published an algorithm that reduced that to about 20 million qubits — a 90% reduction in demand — and requiring a mere 8 hours of runtime, which suggested a Q-day of around 2035. President Biden signed a National Security Memorandum in 2022 mandating that quantum-insecure cryptography be withdrawn from use by then, and NIST began their search for replacement, quantum-secure algorithms.
• Gidney was back in 2025, with a new algorithm that reduced the demand to 1 million qubits — another 95% reduction in demand — but it put the runtime up to a week. That brought Q-day forward to 2030.
• Then, in February this year, Webster et al published a refinement which reduced the demand by another 90%, to around 100,000 qubits. Even more interesting, this was tuneable: more bits, 1 day of runtime: fewer bits, 1 month of runtime.

Webster’s indicates that Q-day might come as early as 2027, but will almost certainly be here in a practical form by 2028, with industrial-scale decryption available by 2029.

On the drawing below, each dot is a major announcement by a quantum computer company or research facility. You can clearly see the constant increases in power. I’ve sketched in a trend line that shows where the industry chaged its goals from width to stability. I’ve been conservative with this: you can see I’ve under-estimated the last few years of achievements, and taken IBMs projection (the green dot at upper right) at face value.

I’ve also shown in red the major algorithm announcements. Thicker lines mean faster execution. Where the red lines cross the grey trend line: that’s Q-day. You can see it’s getting closer and closer.

Graph showing algorithmic demand for cracking RSA2048, compared with the incresing supply of quantum computer power. Most likely, Q-day is sometime in 2028, but could be much earlier. Image by the author.

Most likely Q-day is sometime in 2028. There will inevitably be wide-ranging data leaks within 6–12 months after that, and (unless we urgently apply defences) there will also be wide-ranging and serious disruption to the internet.

We have the antidote. Over the last 7 years, NIST has been coordinating a worldwide effort to design and evaluate replacement algorithms that aren’t vulnerable to quantum codebreaking. Although they’re not exactly drop-in replacements for the old ones, they’re enough to keep the internet working. Based on the estimates above, we have only a couple of years to deploy them, and (as I know, from my day job leading the post-quantum cryptography transformation at a UK bank) that’s a very tight schedule indeed.

But that’s a story for another day.

Thanks for reading! If you liked the ideas in this article, you might want to clap the article, and consider following me. You might also be interested in my book: Extreme Reliability.

To find out more about reliability and security, take a look at julesmay.co.uk