 News Home
 Hot Topics
Current
 Categories
 From the Magazine

10 April 2014 11:44 am ,
Vol. 344 ,
#6180

The Pyrenean ibex, an impressive mountain goat that lived in the central Pyrenees in Spain, went extinct in 2000. But a...

Tight budgets are forcing NASA to consider turning off one or more planetary science projects that have completed their...

Ebola is not a stranger to West Africa—an outbreak in the 1990s killed chimpanzees and sickened one researcher. But the...

In an asyetunpublished report, an international panel of geoscientists has concluded that a pair of deadly...

Tropical disease experts tried and failed before to eradicate yaws, a rare disfiguring disease of poor countries. Now,...

Since 2002, researchers have reported that agricultural communities in the hot and humid Pacific Coast of Central...

Balkan endemic kidney disease surfaced in the 1950s and for decades defied attempts to finger the cause. It occurred...


10 April 2014 11:44 am ,
Vol. 344 ,
#6180
 ScienceNow
 ScienceInsider
 ScienceLive
 About Us
New Form of Quantum Computation Promises Showdown With Ordinary Computers
21 December 2012 5:40 pm
You've heard the hype a hundred times: Physicists hope to someday build a whizbang quantum computer that can solve problems that would overwhelm an ordinary computer. Now, four separate teams have taken a step toward achieving such "quantum speedup" 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 fullfledged 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 socalled 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 fullfledged "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 twoway state to yield either a 0 or a 1, but the twoway 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 morelimited 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 in today's issue of 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."