Quantum computer solves problem, without running

February 22, 2006

By combining quantum computation and quantum interrogation, scientists at the University of Illinois at Urbana-Champaign have found an exotic way of determining an answer to an algorithm – without ever running the algorithm.

Using an optical-based quantum computer, a research team led by physicist Paul Kwiat has presented the first demonstration of "counterfactual computation," inferring information about an answer, even though the computer did not run. The researchers report their work in the Feb. 23 issue of Nature.

Quantum computers have the potential for solving certain types of problems much faster than classical computers. Speed and efficiency are gained because quantum bits can be placed in superpositions of one and zero, as opposed to classical bits, which are either one or zero. Moreover, the logic behind the coherent nature of quantum information processing often deviates from intuitive reasoning, leading to some surprising effects.

"It seems absolutely bizarre that counterfactual computation – using information that is counter to what must have actually happened – could find an answer without running the entire quantum computer," said Kwiat, a John Bardeen Professor of Electrical and Computer Engineering and Physics at Illinois. "But the nature of quantum interrogation makes this amazing feat possible."

Sometimes called interaction-free measurement, quantum interrogation is a technique that makes use of wave-particle duality (in this case, of photons) to search a region of space without actually entering that region of space.

Utilizing two coupled optical interferometers, nested within a third, Kwiat's team succeeded in counterfactually searching a four-element database using Grover's quantum search algorithm. "By placing our photon in a quantum superposition of running and not running the search algorithm, we obtained information about the answer even when the photon did not run the search algorithm," said graduate student Onur Hosten, lead author of the Nature paper. "We also showed theoretically how to obtain the answer without ever running the algorithm, by using a 'chained Zeno' effect."

Through clever use of beam splitters and both constructive and destructive interference, the researchers can put each photon in a superposition of taking two paths. Although a photon can occupy multiple places simultaneously, it can only make an actual appearance at one location. Its presence defines its path, and that can, in a very strange way, negate the need for the search algorithm to run.

"In a sense, it is the possibility that the algorithm could run which prevents the algorithm from running," Kwiat said. "That is at the heart of quantum interrogation schemes, and to my mind, quantum mechanics doesn't get any more mysterious than this."

While the researchers' optical quantum computer cannot be scaled up, using these kinds of interrogation techniques may make it possible to reduce errors in quantum computing, Kwiat said. "Anything you can do to reduce the errors will make it more likely that eventually you'll get a large-scale quantum computer."

Source: University of Illinois at Urbana-Champaign

Explore further: Moore's Law is 50 years old but will it continue?

Related Stories

Moore's Law is 50 years old but will it continue?

July 20, 2015

It's been 50 years since Gordon Moore, one of the founders of the microprocessor company Intel, gave us Moore's Law. This says that the complexity of computer chips ought to double roughly every two years.

3D potential through laser annihilation

June 16, 2015

Whether in the pages of H.G. Wells, the serial adventures of Flash Gordon, or that epic science fiction saga that is Star Wars, the appearance of laser beams—or rays or phasers or blasters—ultimately meant the imminent ...

Getting the measure of matter

June 16, 2015

Peter Rohde and his collaborators develop big ideas – and a measure of corny humour – using photons, the smallest possible units of light. (Did you hear about the photon that walked into a hotel and the clerk asked for ...

Recommended for you

A cataclysmic event of a certain age

July 27, 2015

At the end of the Pleistocene period, approximately 12,800 years ago—give or take a few centuries—a cosmic impact triggered an abrupt cooling episode that earth scientists refer to as the Younger Dryas.

New blow for 'supersymmetry' physics theory

July 27, 2015

In a new blow for the futuristic "supersymmetry" theory of the universe's basic anatomy, experts reported fresh evidence Monday of subatomic activity consistent with the mainstream Standard Model of particle physics.

Dense star clusters shown to be binary black hole factories

July 29, 2015

The coalescence of two black holes—a very violent and exotic event—is one of the most sought-after observations of modern astronomy. But, as these mergers emit no light of any kind, finding such elusive events has been ...

Image: Hubble sees a dying star's final moments

July 31, 2015

A dying star's final moments are captured in this image from the NASA/ESA Hubble Space Telescope. The death throes of this star may only last mere moments on a cosmological timescale, but this star's demise is still quite ...


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.