The logic underlying the coherent nature of quantum information processing often deviates from intuitive reasoning, leading to surprising effects. Counterfactual computation constitutes a striking example: the potential outcome of a quantum computation can be inferred, even if the computer is not run¹. Relying on similar arguments to interaction-free measurements² (or quantum interrogation³), counterfactual computation is accomplished by putting the computer in a superposition of 'running' and 'not running' states, and then interfering the two histories. Conditional on the as-yet-unknown outcome of the computation, it is sometimes possible to counterfactually infer information about the solution. Here we demonstrate counterfactual computation, implementing Grover's search algorithm with an all-optical approach⁴. It was believed that the overall probability of such counterfactual inference is intrinsically limited^{1, 5}, so that it could not perform better on average than random guesses. However, using a novel 'chained' version of the quantum Zeno effect⁶, we show how to boost the counterfactual inference probability to unity, thereby beating the random guessing limit. Our methods are general and apply to any physical system, as illustrated by a discussion of trapped-ion systems. Finally, we briefly show that, in certain circumstances, counterfactual computation can eliminate errors induced by decoherence.

1. Department of Physics, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801, USA
   
2. †Present address: Department of Physics, University of California Santa Barbara, Santa Barbara, California 93106, USA

Correspondence to: Onur Hosten¹ Correspondence and requests for materials should be addressed to O.H. (Email: hosten@uiuc.edu).

Received 4 August 2005; Accepted 14 December 2005