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

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

Using two optical interferometers nested within a third, Kwiat's team succeeded in counterfactually searching a four-element database using Lov Grover's quantum algorithm for searching unsorted databases. "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 paper.

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

E-mail 2006