“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.”
Chuang and his colleagues have now come up with a new, scalable quantum system for factoring numbers efficiently. 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 — [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’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.”
Mark Ritter, senior manager of physical sciences at IBM, says the group’s method of recycling qubits reduces the resources required in the system by a factor of 3 — a significant though small step towards scaling up quantum computing.
“Improving the state-of-the-art by a factor of 3 is good,” says Ritter. But truly scaling the system “requires orders of magnitude more qubits, and these qubits must be shuttled around advanced traps with many thousands of simultaneous laser control pulses.”
If the team can successfully add more quantum components to the system, Ritter says it will have accomplished a long-unrealized feat.
“Shor's algorithm was the first non-trivial quantum algorithm showing a potential of ‘exponential’ speed-up over classical algorithms,” Ritter says. “It captured the imagination of many researchers who took notice of quantum computing because of its promise of truly remarkable algorithmic acceleration. Therefore, to implement Shor's algorithm is comparable to the ‘Hello, World’ of classical computing.”
What will all this eventually mean for encryption schemes of the future?
“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.”