“Classical Computation Can Be Counterfactual 1996-09-02 V1.1 (or Can Schrodinger’s Cat Collapse the Wavefunction?)”, 1997-03-15 (; similar):
We show that at least some classes of classical computation can be carried out counterfactually in a particular sense. By counterfactually we mean that, given a set of quantum superpositions which include the possibility of the (classical) computation being carried out, then an observation can be made such that, even if the computation is not carried out, the result of the computation can be obtained. That is, on some observations, the output of a computer run can be obtained without the computer even being switched on and depends only on the existence of the computer and the possibility of the computation being carried out. As with all counterfactual measurements the proportion of “successful” trials (ie. those in which the computation does not occur, although the result of the computation is obtained) can be made arbitrarily large, but the time taken to get the output is the same as that which would be needed in order to carry out the computation. The interest is in circumstances where there is a reason not to carry out the computation (such as the likelihood that it would permanently change the computer) but we still wish to know the result.
Although the computation is classical, the overall setup including the measuring device constitutes a quantum computer, and our result is essentially a special case of Josza’s algorithm [1995] which shows that all quantum computation [1985] can be carried out counterfactually. However today’s technology is many years away from building a general quantum computer in Deutsch’s sense. Our paradigm demonstrates that by considering a quantum computer to consist of a combination of classical and nonclassical parts, and by restricting the quantum part to observation and the classical part to computation, we can build interesting devices now. We consider how we can widen the class of counterfactual classical computations and come across some unexpected results and interesting speculations.