# Quantum computing gets a bit more real: implications for encryption

The prime factors of the ‘minimal case’ of the number 15 are obvious; 3 and 5. A larger number, say, below 100, may take some pen and paper. An even larger number, with hundreds of digits, can take years to factor, using hundreds of classical computers operating in parallel.

The difficulty of finding the prime factors of a large number underpins the key-based, secure encryption in universal use today. It has long been realised that in principle, a quantum computer has the potential to attack the problem. A computer that could manipulate the states of hundreds of atoms simultaneously might quickly factor very large numbers.

In 1994, Peter Shor, the Morss Professor of Applied Mathematics at MIT, came up with a quantum algorithm that calculates the prime factors of a large number, vastly more efficiently than a classical computer. However, the algorithm’s success depends on a computer with a large number of quantum bits. While others have attempted to implement Shor’s algorithm in various quantum systems, none have been able to do so with more than a few quantum bits, in a scalable way.

Now, in a paper published in the journal Science, the researchers report that they have designed and built a quantum computer from five atoms in an ion trap. The computer uses laser pulses to carry out Shor’s algorithm on each atom, to correctly factor the number 15. In slightly more detail they present, “… the realisation of a scalable Shor algorithm, as proposed by Kitaev…[to]… factor the number 15 by effectively employing and controlling seven qubits and four “cache qubits” and by implementing generalised arithmetic operations, known as modular multipliers.” The system is designed in such a way that more atoms and lasers can be added to build a bigger and faster quantum computer, able to factor much larger numbers. The results, they say, represent the first scalable implementation of Shor’s algorithm.

“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,” says Isaac 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 anytime soon — but now it’s much more an engineering effort, and not a basic physics question.”

While it typically takes about 12 qubits to factor the number 15, they found a way to shave the system down to five qubits, each represented by a single atom. Each atom can be held in a superposition of two different energy states simultaneously. The researchers use laser pulses 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 via the fifth atom, thereby carrying out Shor’s algorithm in parallel, with fewer qubits than is typically required.

The team was able to keep the quantum system stable by holding the atoms in an ion trap, where they removed an electron from each atom, thereby charging it. They then held each atom in place with an electric field.

“That way, we know exactly where that atom is in space,” Chuang explains. “Then we do that with another atom, a few microns away. By having a number of these atoms together, they can still interact with each other, because they’re charged. That interaction lets us perform logic gates, which allow us to realise the primitives of the Shor factoring algorithm. The gates we perform can work on any of these kinds of atoms, no matter how large we make the system.”

Chuang’s team first worked out the quantum design in principle. His colleagues at the University of Innsbruck then built an experimental apparatus based on his methodology. They directed the quantum system to factor the number 15 — the smallest number that can meaningfully demonstrate Shor’s algorithm. Without any prior knowledge of the answers, the system returned the correct factors, with a confidence exceeding 99 percent.

“In future generations, we foresee it being straightforwardly scalable, once the apparatus can trap more atoms and more laser beams can control the pulses,” Chuang says. “We see no physical reason why that is not going to be in the cards.”

This research was supported, in part, by the Intelligence Advanced Research Project Activity (IARPA), and the MIT-Harvard Center for Ultracold Atoms, a National Science Foundation Physics Frontier Center [all of the USA].

The full MIT public statement on the work is here

MIT; www.mit.edu