Powerful quantum computers move a step closer to reality

A research team from Australia has pushed quantum computers closer to fruition, but a former NSA director warns that the technology could break encryption

Researchers at the University of New South Wales have pushed quantum computers a step closer to reality, which one former NSA technical director says calls for a rethink in how the whole security of the internet is managed.

The Australian researchers claim to have developed two new types of quantum bits, or “qubits”, that can perform operations with accuracy above 99%.
Where traditional computers perform their calculations in binary – using 1s and 0s – quantum computers exploit the odd characteristics of the quantum state of particles at the atomic scale.
At their heart, they put the qubits into a state of “superposition” where, like Schrödinger’s famous cat, their value isn’t definitely 1 nor 0, but both at the same time. To “solve” a calculation, the quantum state is ended, so that the qubits take a classic 1 or 0 value. Setting the quantum states and superposition up correctly should mean a quantum computer will reach the same answer as a normal one.

The difference is that once the problem has been set up, a quantum computer can reach its final answer almost instantaneously because the qubits will “collapse” to the correct answer, rather than having to work through a sequence of calculations like a normal digital computer.

In theory that lets them perform certain types of calculations much faster than a typical computer. So far though they’re hindered by more practical concerns like such as the accuracy issue, which has been tackled by the University of New South Wales team.

“For quantum computing to become a reality we need to operate the bits with very low error rates,” said Scientia Professor Andrew Dzurak. Error correction can only do so much, and without accurate hardware, getting millions of calculations slightly off soon adds up.

“Even though methods to correct errors do exist, their effectiveness is only guaranteed if the errors occur less than 1% of the time,” Dzurak continued. “Our experiments are among the first in solid-state, and the first-ever in silicon, to fulfill this requirement.”

The steady progress of quantum computing is a scientific marvel, and some of the problems the technology can be used to tackle, such as puzzling out how proteins fold, will bring positive outcomes. But there are other aspects of it which could be damaging if the world is not prepared.
Quantum computers should in theory be capable of breaking public key encryption, which protects almost all private communication online. Public key systems use two “keys” – one public, and one private – which are derived from pairs of prime numbers. The strength of the encryption relies on the fact that it is far harder to work out the prime factors of such a number (like 323) than it is to generate the number by multiplying the primes together (17x19).

Public-key systems use prime numbers so large that calculating the private key from the public key would take longer than the expected lifespan of the solar system.

But quantum computers can effectively do the same calculations billions of times faster because they would effectively jump directly to the correct answer. “Quantum computers can be very very effective against public key,” says former NSA technical director Brian Snow. Using such a system, “you don’t have to pay much cost for recovering public key crypto keys. They just fall all to pieces.”

What’s worse, it’s not possible to simply make the keys more complex to beat the quantum hackers. “Making the key size bigger does not buy you the exponential build up” that it does against traditional code breakers, Snow says. “For normal cryptography, each bit you add makes the problem twice as hard for the decryptor. Quantum computers going against public keys don’t pay that price.”

With developments like UNSW’s and the recent detection for the first time of Majorana fermions, a type of sub-atomic particle which could be used to build a quantum computer, Snow warns that “within ten to twenty years from now, you could have a quantum computer at scale, large enough and healthy enough, to attack the trust mechanisms of the web.”

“If such a machine exists and if it is going after people on the net, trying to get to their goodies, you have lost all the trust mechanisms the web has.”

One possible solution is going back to an older form of cryptography, using an older form of code-based public key cryptography, mediated by a trusted intermediary. Snow is an adviser at one such firm, PQ Solutions.

The advantage quantum computers have is greatly lessened when breaking traditional encryption. They can still break encryption millions of times faster than traditional computers, but increasing the key size has an effect.

The problem is that trying to enforce any change online makes herding cats look trivial. And trying to agree on who, exactly, should hold the keys to the internet would be borderline impossible. “The web does not exist as one monolithic society with one boss that says ‘March’ and everyone does,” says Snow. But soon enough, the pressure will be on.