Every so often for the past several years now, the tech infosphere spawns another warning that internet security is about to be trashed by quantum computing. The encryption methods that protect all our digital transactions, from online shopping to medical records, are, according to these reports, about to become crackable and therefore useless, thanks to the awesome power that quantum computers can yield. Such alarmism is probably unwarranted, but only if the IT industry gets on with implementing available alternatives.
The problem comes down to something called the Shor algorithm, which was devised in 1994 by computer scientist Peter Shor of Bell Laboratories in New Jersey. It was one of the first examples of something genuinely useful that quantum computers could do and today’s conventional computers can’t.
Shor’s algorithm would, if conducted on a powerful enough quantum computer, make light work of the data encryption methods routinely used today to keep digital information from prying eyes.
Suggested Reading
There is a word for this, and that word is ‘eugenics’
These encryption algorithms rely on the extreme difficulty of factorizing large numbers – that is, finding smaller numbers by which they are exactly divisible. It’s easy to see that the two factors of 33 are 3 and 11. Both are prime numbers, so can’t be factorized any further. But finding all the prime factors of a number like 683,727 (if it has any) isn’t so trivial.
In fact, in general the time taken by a computer to find prime factors increases exponentially with the size of the number. You don’t have to get to very large numbers before the factorization problem gets impossible on any reasonable timescale (a human lifetime, say) even for the biggest, fastest supercomputers today.
For this reason, numbers that are the product of two large primes can be used as a “key” to encrypt data. In one of the most widely used algorithms, unlocking the data requires one to know the two prime factors. The key can be openly shared, because no one stands a chance of working out what these two prime factors are from scratch. But once you’re told them, decryption is easy.
Although there are some handy tricks for finding factors in certain cases, in general you just have to use trial and error. This kind of search is precisely the sort of problem that quantum computing excels at. Quantum computers leverage the laws of quantum physics to manipulate information – encoded in “quantum bits” (qubits), which could be made from individual atoms, light beams, or tiny superconducting circuits – in ways beyond the means of classical computers.
In this way, a mere handful of qubits can carry out some calculations that would stretch the capabilities of billions of normal bits made from silicon transistors.
In 1994, quantum computing was just a gleam in the eye of physicists and computer scientists. But the principles were clear enough, and Shor used these to concoct an algorithm for fast factorization. It became one of just a handful of examples where quantum computers could be clearly demonstrated, in theory, to have the upper hand over classical devices.
Today the landscape has changed completely. Genuine quantum computers – real physical devices that could do simple computational tasks – began to appear in the early 2000s, developed by major information-technology companies such as IBM and Google.
Suggested Reading
Why have scientists created a mouse with a human brain?
They have been getting rapidly bigger and better in the past two decades, and quantum computing is now a multi-billion-dollar global industry in which dozens of companies are making and selling these machines. IBM’s latest quantum chips have more than a thousand qubits each.
Even so, we’re not yet quite at the stage when a quantum computer running Shor’s algorithm could hack the current factorization-based encryption schemes. But we’re not far off. These machines “are still toys, but they’ll stop being toys very soon”, Shor told New Scientist in the summer.
Some forecasts suggest that new, quantum-proof encryption algorithms will be needed as soon as 2029. The good news is that these already exist in theory. The catch is that switching all the computers in banks, hospitals and governments onto these new protocols could take years. There’s no need to panic, but neither is there any time to lose.
