Quantum computing could break the internet. This is how
The next generation of quantum computers will open a new world of possibilities, but also pose enormous risks to our online security
They call it Q-day. That is the day when a robust quantum computer, like this one, will be able to crack the most common encryption method used to secure our digital data.
Q-day will have massive implications for all internet companies, banks and governments — as well as our own personal privacy.
We know that this will happen one day. The only question is when.
For the moment, quantum computers, which exploit the spooky physics of subatomic particles, remain too unstable to perform sophisticated operations for long. IBM’s Osprey computer, thought to be the most powerful quantum computer yet developed, only has 433 qubits (or quantum bits) when most computer scientists consider it would take 1mn to realise the technology’s potential. That may still be a decade away.
But in 1994 the American mathematician Peter Shor wrote an algorithm that could theoretically run on a powerful quantum computer to crack the RSA encryption protocol most commonly used to secure online transactions. The RSA algorithm exploits the fact that while it is very easy to multiply two large prime numbers, no one has yet discovered an efficient way for a classical computer to perform the calculation in reverse. Shor showed how a quantum computer could do so relatively easily. A recent research paper published in China explored the possibility that a hybrid classical-quantum computing approach might be able to pull Q-day forward.
Excited by the possibilities of building the first robust quantum computer, and terrified by the prospect of coming second, the world’s leading powers are now in a race to develop the technology. Not only can quantum computers be used to crack existing encryption methods, they can also be used to secure communications in a quantum world — and governments, corporations and venture capitals have been investing heavily with a view to commercialising the technology.
But how does quantum computing actually work? To understand the answer, first you need to understand how a classical computer functions.
Our quantum journey includes animations that loop. Toggle this if you want to turn those off
Currently enabled
The basic unit of classical computing is a bit. It can sit in one of two binary states: off or on, often described as 0 or 1.
A sequence of eight bits is known as a “byte”, which can store much more data than a bit.
While each individual bit contains just two values, a full byte has 256 unique combinations.
That is enough combinations to encode every character in the Latin alphabet, using a system called ASCII.
A more modern encoding, called “unicode”, uses groups of up to four bytes — enough to cover everything from emojis to Tamil characters and many other character-based languages with just a fraction of its more than 1mn usable combinations.
Just one unreliable bit can completely change the value of a letter, password, or calculation.
For the complex computer systems built on top of these bits to work, reliability is prioritised above all else.
We can use bits to solve tangible problems too.
For example, imagine a labyrinth where the goal is to get to the centre using the shortest possible path.
Using a classical computer, each intersection along the way becomes a binary decision corresponding with a bit, with 1 and 0 representing opposite turns.
In this way, we can think of each combination of bits as a set of directions through the maze.
Some of these paths will overlap, and others might hit dead ends, but by working through each combination of turns we can eventually find the shortest path to the centre.
There’s a key feature of a problem like this, though: to be certain of an answer, we have to work through each possible combination of turns, and we can only check one at a time (remember that these eight bits have 256 combinations).
And while our simple maze may not take modern computers long to work through, imagine if our labyrinth was much larger, each new turn doubling the number of combinations.
And since it will almost always be simpler to add more turns to a maze, or digits to a number, than to build a more powerful computer, if you want to design a problem to slow down or “stump” a computer, you usually can.
This is the kind of puzzle quantum machines could solve in a radically more effective way.
Relative to classical computers, they excel at problems where finding all of the potential answers is difficult (all 256 routes and turns in the maze), but checking correctness is easy (comparing the lengths of all these paths).
In a quantum computer, our bits are replaced with quantum bits, or qubits. These exist in what’s called a quantum state, where until they are measured they can be considered both “on” and “off” at the same time.
If our bits were coins, think of qubits as those same coins but mid-coin flip. At some point they will land on heads or tails but, while in the air, they have some probability of being one or the other. In quantum computing, this “mid-coin flip” state is called “superposition”.
While each qubit is in this state, the quantum computer can be thought of as following each path in the maze simultaneously, rather than one at a time.
As soon as the qubits are measured we’ll be left with one path, but this is no more likely to be correct than one chosen at random.
However, while the computer is in this quantum state, the qubits can be arranged in ways that maximise the possibility of finding the correct answer. The maths behind these arrangements is referred to as “quantum algorithms”, and they are the complicated magic at the heart of quantum computing.
The normally time-consuming task of finding every possible path is no longer a problem on a quantum machine — and given all of them, checking which is shortest is relatively easy with the right algorithm.
Having nudged the machine towards the correct answer, we can now return the quickest route to the centre when we do eventually measure the state of the machine.
That’s how it should work, at least.
In reality, there are a number of issues separating today’s quantum computers from future versions that could dependably solve problems classical computers struggle with.
The biggest challenge is keeping the qubits in a stable position long enough for them to be usable. Qubits are made of notoriously fragile sub-atomic particles in delicate quantum states that are easily disrupted.
Any interaction with the surrounding environment — small amounts of heat, electronic signals, magnetic fields and even cosmic rays — can impact the state of qubits.
Timothy Spiller, director of the Quantum Communications Hub at the Engineering and Physical Sciences Research Council, explains that this “outside noise” masks what is going on in the quantum machine — and makes measuring the correct answer extremely difficult. “If you’ve got a signal and the noise becomes comparable with that, you simply lose the signal. It just gets swamped in the background noise. And that’s true in the quantum case . . . it loses the refinement.”
Some interaction with the environment is necessary, as we eventually need to measure the qubits to return an answer. But this outside engagement creates issues of reliability. That is why most prototype quantum computers operate in a cryogenic chamber just above absolute zero. At minus 273C, the chamber is colder than deep space.
This loss of quantum coherence, known as decoherence, has been likened to the difficulty of controlling a long line of distracted kittens and stopping them from wandering off in every direction.
And remember, just a small reliability issue can completely change the value of a full byte or introduce errors into a system.
Noise from the surrounding environment severely limits how long quantum computers can stay in a quantum state. And this period — often measured in microseconds — may not be long enough to run a quantum algorithm.
Which is why these loud and extremely sophisticated machines — about the size of an oil barrel — are needed to house just a few hundred qubits.
Even though the processor itself is just a small part of it.
The vast majority of the machine is dedicated to keeping the qubits as insulated as possible, to maintain a quantum state as long as possible and minimise errors.
Even the rudimentary quantum technologies we have today can help companies optimise their logistics operations or enable doctors to monitor brain activity in sick children, as they are in the Port of Los Angeles and a Toronto hospital respectively. But a whole new world of possibilities will open up if researchers can succeed in developing robust, error-free quantum computers.
The race to develop the technology is driven both by the prospect of commercial gain and geopolitical rivalry between the great powers. Several of the world’s biggest tech companies, including Google, IBM, Microsoft and Honeywell, have been investing heavily in quantum — as well as a small army of start-ups.
In spite of a broader tech sector downturn, investors poured a record $2.35bn into quantum start-ups last year, according to data compiled by management consultants McKinsey. Much of the investors’ focus was on quantum computing, communications and sensing.
Many governments view quantum technology as a strategic imperative and have been increasing spending on research and development. Last year, the US committed an additional $1.8bn while the EU pledged another $1.2bn. In March, the UK launched a 10-year programme to invest £2.5bn. But these efforts are dwarfed by China, which has announced total investments of $15.3bn to date.
The first company to develop a reliable quantum computer could generate billions in revenues. McKinsey estimates the four industries most impacted by the development of quantum computing — automotive, chemicals, financial services, and life sciences — could potentially gain $1.3trn in value by 2035.
Quantum technology might help us invent new materials and drugs, develop smarter financial trading strategies and create secure new methods of communication. “The prospect of quantum computing opens up entirely new areas of technology,” says David Cowan, a partner at Bessemer Venture Partners, a San Francisco-based venture capital firm. “We can unlock solutions that we just couldn’t even dream of achieving in the past.”
As well as being enticed by the economic possibilities, governments are concerned about the security implications of developing quantum computers. At present, the most common method used to secure all our digital data relies on the RSA algorithm, which is vulnerable to being cracked by a quantum machine.
The RSA encryption method relies on the immense difficulty of factoring the product of two large prime numbers.
Imagine you’re given two buckets of paint, one a shade of red and the other a shade of blue.
If you were asked what exact shade of purple they would produce when mixed evenly, it might not be very difficult to work out.
But what if you started with the purple and were asked to come up with the exact shades of red and blue that were used to create it? Much more difficult.
This kind of problem is what’s known as a “trapdoor function” — easy to compute in one direction, very difficult to do in reverse.
Now imagine if instead of paint colours, we were working with very large prime numbers — much bigger and more headache-inducing than the ones used here. It’s easy to multiply two numbers together . . .
. . . but it turns out that finding the original numbers given only the result is very difficult to do, even for powerful computers. This tricky reverse operation is known as prime factorisation and it underpins a system of encryption, called RSA, used across the internet.
In 1991, RSA Laboratories, a security company whose founders created this widely used method of encryption, offered cash rewards to anyone able to efficiently factor very large semiprime numbers, meaning they have exactly two prime factors.
The smallest of them looked like this.
That number, called RSA-100 for its 100 decimal digits, was factored in a few days in 1991.
Others, up to 250 digits long, were factored in subsequent years, but more than half of the numbers put forward for the challenge have never been solved.
Just like our maze, this is a problem that grows harder for traditional computers as the number of turns (or digits, in this case) grows larger.
But also like our maze, with the right quantum algorithm, it no longer matters if you add more turns or more digits. And for the problem of prime factorisation, that’s where Shor’s algorithm comes in.
Shor says that the “toy” quantum computers we have today are not reliable enough to run his algorithm. It will take several conceptual breakthroughs and a huge engineering effort before we can scale quantum computers to the necessary 1mn qubits.
His best guess as to when this might happen? “I would predict between 20 and 40 years,” he says. But he does not rule out the possibility that the physics challenges will prove too hard and we will never build workable quantum computers. Shor, who has worked as a maths professor at MIT for 20 years, has also published poetry on quantum computing.
“The best quantum computers today, produced in countries like China and at Google, can do on the order of 100 operations before failure”, explains Steve Brierley, founder and chief executive of Riverlane — a company building operating systems for quantum computers. “To implement Shor’s algorithm you need something like a trillion quantum operations before failure.”
But researchers are employing all kinds of ingenious techniques to overcome these challenges. “Scientific breakthroughs don’t always come on a predictable time. But we’re looking at years and not decades for this level of innovation,” says Julie Love, product leader for quantum computing at Microsoft.
For several years, the US government has been planning for a quantum world and has been running competitions to find the most secure communication protocols of the future that would forestall the threat of Q-day. The US National Institute of Standards and Technology is in the process of approving new cryptography systems — based on problems other than factorisation — that are secure against both quantum and classical computers. “It’s really a race between quantum computers and the fix — which is to stop using RSA”, says Brierley.
But whatever new security protocols are finally approved, it will take years for governments, banks and internet companies to implement them. That is why many security experts argue every company with sensitive data should be preparing for Q-day today.
However, the obstacles to developing 1mn-qubit quantum computers remain daunting, with some private sector investors predicting a “quantum winter” as they lose faith in how quickly a quantum advantage can be achieved.
Even if private sector investment slows, the escalating geopolitical rivalry between the US and China will provide added impetus to develop the world’s first robust quantum computer. Neither Washington nor Beijing wants to come second in that particular race.
This story is free to read so you can share it with family and friends who don’t have an FT subscription yet.
