Counterfactual quantum computation through quantum interrogation

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.