Quantum computing
MIT and University of Innsbruck computer scientists have developed a quantum computing system that can factor numbers bigger than 15 in just five qubits, meaning RSA encryption could one day be crackediStock

Computer scientists from MIT and the University of Innsbruck in Austria have developed the first ever five-atom quantum computer, which could one day factor any number and enable it to easily break RSA encryption.

Computers today are coded using traditional bits, which is the small unit of data that usually has a single binary value of 0 or 1. When put together, the bits create code words like 00, 01, 10 or 11 that can be used to program the computer to perform specific commands.

However, in quantum computing, bits can be in superposition known as "qubits", so they can have the value of 1 and 0 at the same time, so code words could be much wider, for example code words like 00+11, 00-11, 01+10 or 01-10.

It typically takes around 12 qubits to factor the number 15, but researchers from MIT and the University of Innsbruck have managed to factor the same number in just five qubits with a quantum computer made from five single atoms, that each represent a single qubit.

Shor's factoring algorithm

The researchers wanted to perform an algorithm for factoring large numbers using quantum computing that was invented by an MIT mathematics professor named Peter Shor in 1994.

Unfortunately, in 1994, quantum computers didn't yet exist, but in 2001, an MIT physicist and electrical engineer called Isaac Chuang managed to use Shor's algorithm to factor the number 15. However, his quantum computer couldn't get past that number.

So the researchers wanted to build a quantum computer that could factor numbers higher than 15 using Shor's algorithm, and they figured that they needed four qubits to perform the algorithm and a fifth qubit to act as the output for the data, the new system was able to return the correct factors with 99% accuracy.

They developed a quantum computer prototype known as an "ion trap". A string of ions are held in place by an electrical field and then manipulated using laser pulses. Each atom can be held in a superposition of two different energy states simultaneously, while laser pulses are used to perform "logic gates," or components of Shor's algorithm, on four of the five atoms.

The results are then stored, forwarded, extracted and recycled by the fifth atom, thereby carrying out Shor's algorithm in parallel, with fewer qubits than are typically required.

Quantum computing will be able to crack RSA encryption

"We show that Shor's algorithm, the most complex quantum algorithm known to date, is realisable in a way where, yes, all you have to do is go in the lab, apply more technology and you should be able to make a bigger quantum computer," said Chuang, professor of physics and professor of electrical engineering and computer science at MIT.

"It might still cost an enormous amount of money to build — you won't be building a quantum computer and putting it on your desktop any time soon — but now it's much more an engineering effort, and not a basic physics question. In future generations, we foresee it being straightforwardly scalable, once the apparatus can trap more atoms and more laser beams can control the pulses."

Although it isn't currently an issue, in theory this means that in future the quantum computer will be able to factor absolutely any number, which means it will be able to crack factorisation-based encryption, such as the RSA public key and private key encryption method.

"We see no physical reason why that is not going to be in the cards," Chuang added.

"If you are a nation state, you probably don't want to publicly store your secrets using encryption that relies on factoring as a hard-to-invert problem," said Chuang. "Because when these quantum computers start coming out, [adversaries will] be able to go back and unencrypt all those old secrets."

The research, entitled "Realization of a scalable Shor algorithm", was published in the journal Science.