New implementation of Shor’s Algorithm Brings Quantum Hacking Closer
According to a paper, published Friday in the journal Science, Physicists at MIT and the University of Innsbruck in Austria have created a quantum computer out of just five atoms in an ion trap that uses laser pulses to carry out Shor’s algorithm on each atom to correctly factor the number 15. It is the first implementation of Shor’s algorithm in which prior knowledge of the factors was not used to simplify the computational procedure.
It is very time consuming problem to find the integer factors of a large odd number. While some numbers are easier to factor than others, there is no known algorithm that can factor all numbers efficiently. As a result, large numbers and their factors are used in some cryptography systems – and this makes such systems vulnerable to anyone who can come up with an efficient factoring algorithm.
In 1994, Peter Shor, the Morss Professor of Applied Mathematics at MIT realized that a quantum computer could be much more efficient at factoring large numbers than a conventional computer. He worked out 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. And 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.
Crucially, and for the first time, this technology is scalable – can be expanded to incorporate more atoms and factor more complex numbers – which is important because many encryption schemes are based upon this “factoring problem.”
“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,” co-author Isaac Chuang, professor of physics and professor of electrical engineering and computer science at the Massachusetts Institute of Technology, explains in a press release.
“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.”
Factoring the number 15, the smallest number that can meaningfully demonstrate Shor’s algorithm, is an easy task, something children learn early in their mathematics curriculum. The prime factors, or multipliers, are three and five.
However, larger numbers prove to be more complex, and when you reach the realm of numbers consisting of hundreds of digits, it takes years and considerable computing power to find the answers.
“Certain algorithms for quantum computers are able to outperform their classical counterparts,” reads the paper’s abstract.
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 relies on atomic-scale units, or “qubits,” that can be simultaneously 0 and 1 – a state known as a superposition. In this state, a single qubit can essentially carry out two separate streams of calculations in parallel, making computations far more efficient than a classical computer.
Study co-author Isaac Chuang, a professor of physics and professor of electrical engineering and computer science at MIT 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.”
Factoring the number 15 with Shor’s algorithm normally takes about 12 qubits, so you can see how quickly the number of qubits required by said algorithm to operate can very quickly explode as the number to be factored grows. (Note that the lower limit on RSA keys is 1024 bits, or 309 decimal digits.) 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. They performed “logic gates” (part’s of Shor’s algorithm) on four of the five atoms using lasers. The fifth atom was responsible for storing, forwarding, extracting and recycling subsequently 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.”
Chuang says, “In future generations, we foresee it being straightforwardly scalable, once the apparatus can trap more atoms and more laser beams can control the pulses. 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.”
So it is that, while this particular quantum computer can only calculate the prime factors of 15, it promises so much more.
“[Shor’s algorithm] captured the imagination of many researchers who took notice of quantum computing because of its promise of truly remarkable algorithmic acceleration,” said Mark Ritter, senior manager of physical sciences at IBM. “Therefore, to implement Shor’s algorithm is comparable to the ‘Hello, World’ of classical computing.”
