Google Achieves Quantum Supremacy. Is Encryption Safe?

In a research paper first seen by the Financial Times, Google seems to claim that it achieved its long-proposed goal of “quantum supremacy.” This marks a major milestone in quantum computing, and it begins the era in which quantum computers can start out-performing classical supercomputers for various applications.

Quantum Supremacy Is Here

When Google set up its quantum computing lab in 2014, it was also when it told the public that it would attempt to achieve quantum supremacy with roughly 50-qubits. At the time, the world’s most powerful supercomputers could only simulate 45 qubits, so Google believed that 50-qubits should just about do it. 

However, in 2017, the same year in which Google promised it would achieve quantum supremacy, IBM showed in one of its research papers on quantum computing that even 56-qubits wouldn’t be enough to achieve quantum supremacy. Coincidentally, a year later, Google started talking about its new 72-qubit quantum computer, but quantum supremacy eluded the company.

Since then, Google seems to have scaled back the number of qubits in a new version of its quantum computer that has only 53-qubits. As IBM has been saying for some time, it’s not just the number of qubits that matters but the “quantum volume,” which is a metric that describes a combination of the number of qubits and the error rate of those qubits. 

As such, the number of physical qubits alone might not tell us too much about the capabilities of a quantum computer. For instance, D-Wave’s quantum annealing computer claims 5,000 qubits, but the company hasn’t even attempted to hint at achieving quantum supremacy or anything similar anytime soon.

Google’s quantum computer achieved quantum supremacy by being able to run a quantum algorithm that classical supercomputers wouldn’t be able to run in a reasonable time frame. It’s the first time a quantum computer can beat a classical supercomputer at anything. 

According to the paper that FT saw, the Google researchers wrote:

“This dramatic speed-up relative to all known classical algorithms provides an experimental realization of quantum supremacy on a computational task and heralds the advent of a much-anticipated computing paradigm. To our knowledge, this experiment marks the first computation that can only be performed on a quantum processor.”

Although this first real quantum computing "win" may not seem like much, one could imagine the first transistor didn’t look like it would do much either. From here we can expect that the rate of improvement -- which Google researchers claim in their paper to be double exponential -- will eventually get quantum computers to a point where they can run many more applications or simulations (such as chemical simulations) on which classical supercomputers would choke.

How Long Until Quantum Computers Break Encryption?

There has been a discussion about quantum computers being able to break encryption almost since the beginning of their history. One of the very first “quantum algorithms” that were developed for quantum computers many years before anyone even started building a quantum computer was actually encryption-breaking algorithms.

One algorithm, called Shor’s algorithm, quantum can completely break RSA and elliptic curve cryptography as soon as the quantum computer has enough (logical) qubits to do that. The other, called Grover’s algorithm, can drastically reduce AES encryption from 128-bits to 64-bits, which can then be broken by run-of-the-mill PCs.

You can attempt to increase the bits on each encryption algorithm and try to defend yourself that way against quantum computers, but once quantum computers can break the lowest levels of encryption, we should be only years away before they break the strongest versions of these encryption algorithms, too.

The good news is that thousands of logical qubits will be needed to achieve break what are currently the most common encryption algorithms in use. Researchers from Canadian company Krypterra believe that we’d need 2,953 logical qubits to break AES-128 and 6,681 logical qubits to break AES-256. Similarly, we’d need 4096 logical qubits to break RSA-2048.

But what are logical qubits anyway? Here comes the even “better” news in regards to encryption -- Krypterra researchers say that to get thousands of logical qubits we’d need millions of physical qubits, or the same type of qubits Google, IBM, Intel, and others currently claim to have. Google itself has said before that quantum computers get truly interesting when we reach somewhere between 100,000 and 1 million qubits.

That said, we shouldn’t get too optimistic. First off, this is an assumption about the future utilizing existing conditions, such as existing error rates. If we discover some breakthrough technologies along the way that allow us to drastically lower error rates for qubits, then eventually we may need only hundreds, tens or even only several qubits to create a single logical qubit. That would move to encryption-breaking goalpost much closer to our current time.

Quantum-Resistant Algorithms To The Rescue

All of this doesn’t necessarily mean we’ll eventually have to move to a pre-Snowden era, where everything is as good as unencrypted, and all of our private communications and online transactions are up for grabs by cybercriminals as well as spy agencies. There are several classes of quantum-resistant encryption algorithms that may protect us against the quantum encryption apocalypse.

The National Institute of Standards and Technology (NIST) is already working on standardizing some of these quantum-resistant algorithms. The downside to these algorithms is that for one, they will be unproven for many years to come. They also tend to have slower performance compared to the classical algorithms, but this is what makes them more resilient against the quantum computers’ encryption-cracking ability. 

All of this means that even if quantum computers will be able to break standard encryption algorithms two or three decades from now, it’s not too early to start designing and experimenting with the new algorithms. This way, we can be sure they work the moment we implement them on everyone’s websites when we discover that classical encryption is no longer safe from quantum computers.