http://www.physorg.com/news11087.html

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."

...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...

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."

...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...

http://www.cebaf.gov/news/internet/1997/spooky.html

Quantum events obey the laws of quantum theory, which governs the behavior of minute objects like atoms and subatomic particles, including photons of light. By contrast with the laws of "classical" physics (which apply to the relatively large objects of the everyday world), quantum physics often exhibits behavior that seems impossible.

One of the weird aspects of quantum mechanics is that something can simultaneously exist and not exist; if a particle is capable of moving along several different paths, or existing in several different states, the uncertainty principle of quantum mechanics allows it to travel along all paths and exist in all possible states simultaneously. However, if the particle happens to be measured by some means, its path or state is no longer uncertain. The simple act of measurement instantly forces it into just one path or state...

One of the weird aspects of quantum mechanics is that something can simultaneously exist and not exist; if a particle is capable of moving along several different paths, or existing in several different states, the uncertainty principle of quantum mechanics allows it to travel along all paths and exist in all possible states simultaneously. However, if the particle happens to be measured by some means, its path or state is no longer uncertain. The simple act of measurement instantly forces it into just one path or state...

"This research is interesting not only from a scientific and philosophical point of view, but because of a very practical consequence: we can now create a completely secure code. A quantum key, which is now within reach, would allow banks to carry out transactions with each other over optical fibers, completely safe from all possible code-breaking methods and from eavesdropping or interference."

The idea for such a system, he said, originated with Dr. Artur D. Eckert at Oxford University in England.

Details of the Swiss experiment will be described in a forthcoming technical paper, Gisin said, and he is working with the Swiss telecommunications agency to develop a cryptographic system based on entangled particle "twins." Identical random-number sequences generated simultaneously by pairs of widely separated twins would serve as cipher keys equivalent to the "one-time pads" used by spies and governments to encode and decode ultra-secret messages...

The idea for such a system, he said, originated with Dr. Artur D. Eckert at Oxford University in England.

Details of the Swiss experiment will be described in a forthcoming technical paper, Gisin said, and he is working with the Swiss telecommunications agency to develop a cryptographic system based on entangled particle "twins." Identical random-number sequences generated simultaneously by pairs of widely separated twins would serve as cipher keys equivalent to the "one-time pads" used by spies and governments to encode and decode ultra-secret messages...