The heady, Bondesque combination of espionage and quantum computing proved irresistible to headline writers everywhere. “NSA racing to build quantum computer that would open the door to easily breaking the strongest encryption tools in the world” panted the Daily Mail in one example.
“I’d be amazed if they weren’t working on it,” said Professor Alan Woodward of Surrey University, listing a large number of organisations and research facilities where the world’s brightest minds are wrestling with the problem of harnessing the bizarre properties of subatomic particles to create a practical, working, general-purpose quantum computer.
“As Moore’s Law reaches its physical limits pretty much every university computer science department in the world has someone working on quantum computing,” Woodward went on. “And the majority of them are trying to factor prime numbers which lies behind key cryptography, as a proof of concept.”
In this context the NSA’s “doomsday weapon” against cryptography looks slightly less menacing, especially since it has to share a $80m budget with other computing projects under the umbrella of the “Penetrating Hard Targets” programme.
For the purpose of comparison, in December the UK government announced a £270m investment over the next five years in quantum computing research in recognition of its potential benefits to the economy.
Like nuclear fusion, universal quantum computers always seem to be five years away.
And as with that promised source of infinite free energy, the problems are to do with the engineering rather than the science. Current systems tend to be either very unstable or very large.
Which is not to say that no progress is being made. In fact a working quantum computer made by Canadian firm D-Wave already exists, with a 512-qubit processor that uses a process called quantum annealing. Investors include Google and NASA. However, this is a specialist device rather than a general-purpose one and is not suited to factorisation problems such as cracking public key encryption.
“The D-Wave computer is great for solving optimisation queries like the well-known ‘travelling salesman problem’,” said Woodward. “But it won’t run Shor’s algorithm with the speed advantage everyone wants.”
Shor’s algorithm, and others like it, make use of quantum computers’ ability to perform multiple calculations at the same time rather than having to follow a painstaking step-by-step process as digital machines do. It is used to factorise large numbers, something that classical computing finds very difficult.
The difficulty in factorising large numbers has long been exploited by public key encryption (PKE). PKE provides the underlying security for the entire internet, offering a secure means of transmitting encryption and decryption cyphers between trusted parties. It relies on one-way functions such as multiplying two large prime numbers to create a larger number.
This is simple to do, but to reverse the process, to crack the key to discover the constituent factors, can take many years with even the most powerful classical computers as they crunch through all the possibilities, one by one.
Qubits, superposition & entanglementIn classical computing a bit can be 0 or 1. However, at the subatomic level items such as photons as photons and electrons exhibit a number of disconcerting characteristics, such being able to exist in two states at the same time, only “deciding” which to adopt once they are observed.
While in this in-between state, called superposition, a subatomic object represents both 1 and 0 at the same time. So a qubit, the basic unit of information in quantum computing, can be 1, 0, both or neither.
In a quantum computer a qubit is entangled with one or more other qubits.
If the quantum state (represented by 1 or 0) of one qubit is known, then the quantum states of of the entangled qubits will be known too.
For two entangled qubits the number of possible superpositions is four (10, 11, 01, 00), for three it is eight and for 500 it is 2 to the power of 500 – an enormous number.
Running calculations across such systems using appropriate algorithms allows the computations to be done in parallel, rather than in the step-by-step linear processes followed by classical computers, allowing enormous increases in processing speed when solving certain types of problems.
But a quantum computer running something like Shor’s algorithm could do it in seconds.
And once these one-way functions become two-way functions, they are effectively useless for key transmission.
Scary stuff, but probably still some way off, even for a well-resourced organisation like the NSA.
The barriers to engineering a stable general-purpose quantum computer remain daunting. That said, progress is being made, and Professor Woodward has few doubts that sooner or later a tipping point will be reached, after which progress will be rapid.
“In the early 80s computers were huge mysterious things which sat in special chilled rooms that could only be entered by the high priests – the operators and technicians,” he said. “But look at how fast things changed. Quantum computers are at a similar stage now, but there have been some real advances in the last couple of years.”
Storing quantum data for meaningful periods of time is one of these advances. Given their extreme sensitivity to the external environment, very low temperatures (close to 0 K or -273 degrees C) are typically required to stabilise the quantum bits (qubits) of data for more than a few seconds. However, last year a Canadian-led group of of international researchers managed to preserve the quantum state of phosphorus atoms embedded in a silicon wafer for 39 minutes at room temperature, beating the previous record by 100 times.
The number of interacting qubits is increasing too. In 2012 a US-led team created a quantum simulator consisting of a supercooled two-dimensonal grid of beryllium ions that could engineer interactions among hundreds of qubits -10 times more than previous devices.
Once a stable quantum computer has been created there remains the small matter of programming it. Quantum computers and digital computers are very different beasts.
Although quantum computers can potentially run computations many orders of magnitude faster than even the quickest supercomputer, the results are probabilistic rather than definitive and algorithms to run on them must be designed accordingly.
So, perhaps of more pressing concern is the rumoured compromise by the NSA of the random number generators used by RSA key generation algorithms.
This is possible because they are not really random.
[If PKE’s days are numbered what will take its place? Turn to next page]