Counterfactual Computation

Abstract

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 general 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) never exceeds 1 in any protocol and we 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-epsilon must have N tending to infinity as epsilon tends to 0. These general results are illustrated with some explicit protocols for counterfactual computation. 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 generalised.

19 pages. LaTex, 2 figures. Revised version has some new sections and expanded explanations

Cited by in corpus (32)

• Counterfactual Quantum Cryptography
• Protocol for direct counterfactual quantum communication
• Quantum Shannon theory with superpositions of trajectories
• Sequential weak measurement
• Measuring incompatible observables of a single photon
• Experimental demonstration of counterfactual quantum communication
• The Impossibility of the Counterfactual Computation for all Possible Outcomes
• Modification of "Counterfactual communication protocols" which eliminates weak particle traces
• Experimental Realization of Sequential Weak Measurements of Arbitrary Non-commuting Pauli Observables
• Exchange-Free Computation on an Unknown Qubit at a Distance
• On-chip interaction-free measurements via the quantum Zeno effect
• An Interaction-Free Quantum Measurement-Driven Engine
• Deterministic Teleportation and Universal Computation Without Particle Exchange
• From Counterportation to Local Wormholes
• Counterfactual distribution of cat states
• Parallel interaction-free measurement using spatial adiabatic passage
• Verification of Nondeterministic Quantum Programs
• Counterfactuality, back-action, and information gain in multi-path interferometers
• Nondestructive interaction-free atom-photon controlled-NOT gate
• Misinference of interaction-free measurement from a classical system
• Role of interference and entanglement in quantum neural processing
• Angular Momentum Flows without anything carrying it
• Quantum Games and Programmable Quantum Systems
• Conditions for Nondistortion Interrogation of Quantum System
• Quantization of Games: Towards Quantum Artificial Intelligence
• Can a computer be "pushed" to perform faster-than-light?
• Counterfactuals in Quantum Mechanics
• Diffraction-Based Interaction-Free Measurements
• Quantum key distribution based on the quantum eraser
• Quantum Godwin's Law
• "Counterfactual" quantum protocols
• Termination of Nondeterministic Quantum Programs