By Adrian Cho, *Science*NOW
You've heard the hype a hundred times: Physicists hope to someday build a whiz-bang quantum computer that can solve problems that would overwhelm an ordinary computer. Now, four separate teams have taken a step toward achieving such "quantum speed-up" by demonstrating a simpler, more limited form of quantum computing that, if it can be improved, might soon give classical computers a run for their money. But don't get your hopes up for a full-fledged quantum computer. The gizmos may not be good for much beyond one particular calculation.
Even with the caveats, the challenge of quantum computing has proven so difficult that the new papers are gaining notice. "The question is, does this give you a first step to doing a hard calculation quantum mechanically, and it looks like it might," says Scott Aaronson, a theoretical computer scientist at the Massachusetts Institute of Technology (MIT) in Cambridge and an author on one of the papers.
Instead of flipping ordinary bits that can be set to either 0 or 1, a so-called universal quantum computer would manipulate quantum bits, or "qubits," that can be 0, 1, or, thanks to the weirdness of quantum mechanics, 0 and 1 at the same time. Crudely speaking, the quantum computer could crunch many numbers at once instead of doing them one at a time, as a "classical" computer must. So it could solve problems that would overwhelm a regular computer. For example, a full-fledged "universal" quantum computer could quickly factor huge numbers, an ability that could be used to break today's internet encryptions schemes.
First, researchers must assemble workable qubits. For example, an ion can serve as a qubit by spinning in one direction to represent 0, another way to represent 1, or both ways simultaneously to make the 0 and 1 state. A measurement of a qubit will "collapse" that two-way state to yield either a 0 or a 1, but the two-way state is still essential for processing many numbers at once. To make a universal quantum computer, scientists must also establish a weird quantum connection between qubits called "entanglement," in which measurement on one qubit determines the state of another. The best a rudimentary universal quantum computer has done is to factor the number 21—hardly a task that will crash your personal computer.
However, four groups have now demonstrated a more-limited type of quantum computation that might be developed more quickly. They all use photons, quantum particles of light, that run through a maze of crisscrossing optical channels. At the intersections, the photons can change paths with certain probabilities. In all of the experiments, three photons enter and exit through either five or six ports. The task is to calculate the probabilities for the photons to come out various combinations of output ports.
At first blush, the problem is similar to a classical puzzle of marbles rattling through such a maze. However, because of quantum mechanics, photons also act like waves that overlap to reinforce each other or cancel each other out in the various paths, which changes what emerges from the outputs. Calculating the possible outcomes requires a mathematical manipulation known as taking the "permanent" of a matrix of numbers that depends on the detail of the maze. That computation is so complex that, with just a few dozen photons and ports, it would overwhelm an ordinary computer.
However, the answer can be had by simply measuring what emerges from the outputs. In such "boson sampling," the optical circuits themselves serve as quantum computers to determine the distributions of permanents. And that's exactly what Andrew White, a physicist at the University of Queensland in Brisbane, Australia, and colleagues (including Aaronson) report Dec. 20 in Science, as do Ian Walmsley, a physicist at the University of Oxford in the United Kingdom and colleagues. Philip Walther, a physicist at the University of Vienna, and colleagues recently reported a similar result in a paper posted to the arXiv preprint server, as did Roberto Osellame of the Italian National Research Council and the Polytechnic University of Milan, and colleagues.
So have physicists outpaced a classical computer? Not even close. The current experiments use such a small number of photons that it would take a standard laptop a fraction of a second to make the same calculation. In contrast, the experiments themselves can still take hours. But if the work can be scaled up to about 25 photons and 400 channels then the classical computer should start to fall behind the experiment, Walther estimates. "In 10 years or so you may be able to use existing technology and resources to outperform a conventional computer," he says.
However, it's not clear that such an effort will work, says John Preskill, a theorist at the California Institute of Technology in Pasadena. A bigger optical circuit would be more susceptible to effects such as the absorption of photons within the circuit and optical noise that could distort the results, Preskill notes. Ironically, accounting for those imperfections could make modeling the circuits easier, not harder, and allow the computer to keep up, Preskill says.
As for the computation of permanents—the only problem this approach solves—it probably does not have any application beyond these experiments. Still, if boson sampling can be shown to be faster than ordinary computation, it would be worth looking for other applications, says Edward Farhi, a theoretical physicist at MIT. "Maybe it's not universal, but perhaps there's another problem that's more interesting that you can map on to it."
The real value of the problem is that it gives researchers a chance to show that a quantum computer can do something a classical computer can't, Preskill says. "That's kind of the core of what quantum computing is about," he says. "Of course, these guys have only three photons going in and coming out. So they've got a way to go."
*This story provided by ScienceNOW, the daily online news service of the journal *Science.