Counterfactual computation
Graeme Mitchison, Richard Jozsa · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 2001
Suppose that we are given a quantum computer programmed ready to perform a computation if it is switched on. Counterfactual computation is a process by which the result of the computation may be learnt without actually running the computer. Such processes are possible within quantum physics and to achieve this effect a computer embodying the possibility of running the computation must be available, even though the computation is, in fact, not run. We study the possibilities and limitations of protocols for the counterfactual computation of decision problems (where the result r is either 0 or 1). If p⊂r denotes the probability of learning the result r 'for free' in a protocol, then one might hope to design a protocol which simultaneously has large p⊂0 and p⊂1. However, we prove that p⊂0 + p⊂1 ≤ 1 in any protocol of this type and derive further constraints on p⊂0 and p⊂1 in terms of N, the number of times that the computer is not run. In particular, we show that any protocol with p⊂0 + p⊂1 = 1 – ∈ must have N tending to infinity as ∈ tends to 0. We show that ‘interaction–free’ measurements can be regarded as counterfactual computations, and our results then imply that N must be large if the probability of interaction is to be close to zero. Finally, we consider some ways in which our formulation of counterfactual computation can be generalized.