Counterfactual computation

DOI10.1098/RSPA.2000.0714MaRDI QIDQ2748105zbMATH OpenOpenAlexWikidataFDO

Authors Graeme Mitchison, Richard Jozsa

Publication date 14 January 2004

Published in Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/9907007

zbMATH Keywords

counterfactualinteraction-freemeasurementprobability of learningquantum computation

Mathematics Subject Classification ID

General topics in artificial intelligence (68T01) Quantum computation (81P68)

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.

Recommendations

• Unconventional Computation
• Interaction-free measurements and counterfactual computation in IBM quantum computers
• ``Counterfactual quantum protocols
• Counterfactuality of `counterfactual' communication
• Some remarks on knowledge and probability arising from counterfactual quantum effects

Cited in

(19)

• Quantum effects in algorithms
• Quantum computation based on retarded and advanced propagation.
• ``Interaction-free channel discrimination
• Termination of nondeterministic quantum programs
• Compiling quantum programs
• Quantization of games: towards quantum artificial intelligence
• Interaction-free measurements and counterfactual computation in IBM quantum computers
• Information carrier and resource optimization of counterfactual quantum communication
• Local distinguishability of Bell-type states
• Some remarks on knowledge and probability arising from counterfactual quantum effects
• Counterfactuality of `counterfactual' communication
• scientific article; zbMATH DE number 1406116 (Why is no real title available?)
• Quantum cryptography: key distribution and beyond
• How to simulate a universal quantum computer using negative probabilities
• Unconventional Computation
• Probabilistic Evaluation of Counterfactual Queries
• Diffraction-based interaction-free measurements
• Quantum key distribution based on the quantum eraser
• An interaction-free quantum measurement-driven engine

This page was built for publication: Counterfactual computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2748105)