Finding the prime factors or multipliers of large numbers if Herculean task and as result this “factoring problem” is the backbone of which many encryption schemes are based. In a paper published in the journal Science today, researchers announced that they have built a quantum computer for factoring, that is for the first time, scalable.
Quantum computers and Shor’s algorithm
Factoring 15 is pretty easy, you’re probably already there. The answer is a resounding — 3 and 5, but this hardly makes you a cryptographer. As numbers get bigger the task becomes massive. For example a number with 232 digits once took scientist nearly two years to factor and they were using hundreds of (classical) computers working in parallel to finally find the answer which is far to long to give you here.
This “factoring problem” is likely how your credit cards, banking information, and your nation’s secrets are kept safe. Cryptographers have flipped the problem into a solution. However, a single quantum computer could make child’s play out of this encryption if only it was scalable.
In 1994, Peter Shor, the Morss Professor of Applied Mathematics at MIT worked out a (quantum) algorithm that could do the factoring much quicker than a trove of classical computers. But, in order for his algorithm to work at peak efficiency you need a computer with a bunch of quantum bits. While scientists and researchers have implemented Shor’s algorithm in a quantum scheme, they have not achieved more than a handful of quantum bits and never in a scalable manner.
However, the paper today suggest this could soon change after researchers from MIT and the University of Innsbruck in Austria reported that they successfully built a computer for five atoms held in an ion trap. This quantum computer uses pulses of laser energy to carry out the famed algorithm to do the factoring work on each atom. In this case the number 15 was used as it’s the lowest number that makes Shor’s algorithm function efficiently.
Bigger quantum computers won’t be cheap or easy but it could work
“We show that Shor’s algorithm, the most complex quantum algorithm known to date, is realizable 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.”
From past experience Chuang knows its about the engineering, not the physics.
Really quickly, classic computers use 0s and 1s to represent numbers and transform an input into an output but manipulate the 0s and 1s according to an algorithm’s, for lack of a better word, instructions. Quantum computing uses “qubits”, which are atomic-scale units that through a state known as superposition can be a 0 and 1 at the same time. This superposition allows a qubit to carry out to streams of calculations separately, yet, parallel increasing its efficiency dramatically.
Chuang was the first to realize Shor’s algorithm in practice by designing a quantum computer based on a single molecule in superposition that could be made to factor the number 15 through the use of magnetic resonance. However, it was far from scalable.
“Once you had too many atoms, it was like a big forest — it was very hard to control one atom from the next one,” Chuang reflected. “The difficulty is to implement [the algorithm] in a system that’s sufficiently isolated that it can stay quantum mechanical for long enough that you can actually have a chance to do the whole algorithm.”
The new design
Now, it generally takes 12 qubits to factor 15, Chang’s team did it in five atoms each representing a qubit. They were able to hold each atom is superposition by two energy streams at the same time. Using lasers they performed “logic gates” (part’s of Shor’s algorithm) on four of the five atoms. The fifth atom was responsible for storing, forwarding, extracting and recycling consequently working through Shor’s algorithm in parallel with only the five atoms.
An ion trap was used for stability, with the trap they were able to charge each atom by removing and electron from each, they then used an electric field to hold each in place. (My brain hurts, I’ll hand it back to Chuang)
“That way, we know exactly where that atom is in space,” Chuang explains. “Then we do that with another atom, a few microns away — [a distance] about 100th the width of a human hair. 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 realize 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.”
That was MIT‘s role in the find, they then passed their design to the University of Innsbruck where his colleagues built the quantum computer. And voila, 15 factored with Shor’s algorithm using only 5 “qubits.”
“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.”
And that doesn’t bode well for encrypted information.
“Well, one thing is that 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,” Chuang says. “Because when these quantum computers start coming out, you’ll be able to go back and unencrypt all those old secrets.”
