3 September 2009—Modern cryptography relies on the extreme difficulty computers have in factoring huge numbers, but an algorithm that works only on a quantum computer finds factors easily. Today in Science, researchers at the University of Bristol, in England, report the first factoring using this method—called Shor’s algorithm—on a chip-scale quantum computer, bringing the field a tiny step closer to realizing practical quantum computation and code cracking.
Quantum computers are based on the quantum bit, or qubit. A bit in an ordinary computer can be either a 1 or a 0, but a qubit can be 1, 0, or a ”superposition” of both at the same time. That makes solving certain problems—like factoring—exponentially faster, because it lets the computer try many more solutions at once. The race is on to find the ideal quantum computer architecture, with qubit contenders that include ions, electrons, superconducting circuits, and in the University of Bristol’s case, photons.
MIT professor Seth Lloyd, who has been researching quantum computing and communication systems since the early 1990s, says that ”optical methods [using photons] have a long way to go before being useful.” But, Lloyd adds, the Bristol experiment demonstrates that the components for optical quantum computing can be squeezed onto a chip, which is an important step forward.
Shor’s algorithm was first demonstrated in a computing system based on nuclear magnetic resonance—manipulating molecules in a solution with strong magnetic fields. It was later demonstrated with quantum optical methods but with the use of bulk components like mirrors and beam splitters that take up an unwieldy area of several square meters.
Last year, the Bristol researchers showed they could miniaturize this optical setup, building a quantum photonic circuit on a silicon chip mere millimeters square. They replaced mirrors and beam splitters with waveguides that weave their way around the chip and interact to split, reflect, and transmit light through the circuit. They then injected photons into the waveguides to act as their qubits.
Now they’ve put their circuit to work: Using four photons that pass through a sequence of quantum logic gates, the optical circuit helped find the prime factors of the number 15. While the researchers showed that it was possible to solve for the factors, the chip itself didn’t just spit out 5 and 3. Instead, it came up with an answer to the ”order-finding routine,” the ”computationally hard” part of Shor’s algorithm that requires a quantum calculation to solve the problem in a reasonable amount of time, according to Jeremy O’Brien, a professor of physics and electrical engineering at the University of Bristol. The researchers then finished the computation using an ordinary computer to finally come up with the correct factors.
Of course, says O’Brien, ”a smart schoolkid could tell you [the answer] in a few seconds.” To be really useful, he says, ”what we’d need is a quantum computer that has millions of qubits, to solve problems that are genuinely hard to solve otherwise.”
That quantum factoring machine is decades away, but in the meantime chip-scale optical architectures like those of the Bristol team could help in applications like quantum key distribution, which guarantees secure communication based on the laws of quantum mechanics rather than on the mathematical difficulty of factoring. Or they could be used to simulate quantum systems in physics experiments, which might require just hundreds of qubits instead of thousands or millions.
”We know 3 times 5 is 15,” says University of Maryland quantum computing expert Christopher Monroe, but this experiment ”has promise for developing something that could tell us the answer to something we don’t know.”
MIT’s Lloyd is not convinced that the technology is scalable. The real trick, he says, will be to develop a self-contained method that measures the photons, reads the results, and finds the factors of huge numbers without dipping back into classical computation or knowing the answer ahead of time. That’s the ”tough technological problem that no one has any idea how to solve,” Lloyd says, although he believes it’s ”not against the laws of physics.”
O’Brien, however, says that only the hard part needs to be done on a quantum computer, which will likely be a highly sophisticated device and in much demand. ”You wouldn’t waste its time with classical computations,” O’Brien says. ”If the other bits are easy, why do them on a quantum computer?”
The Bristol group next aims to build larger, more sophisticated quantum optical circuits, with more waveguides packed on the chip, in addition to more-efficient single-photon generators and detectors. That will push them toward a scaled-up system that might, decades hence, break math-based encryption codes using millions of qubits.