Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9907007 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Counterfactual computation

Graeme Mitchison, Richard Jozsa

Published May 8, 2001• 77 citations
arXivHTMLPDF

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 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.

DOI
10.1098/rspa.2000.0714

Related papers

Quantum Effects in Algorithms

Richard Jozsa

We discuss some seemingly paradoxical yet valid effects of quantum physics in information processing. Firstly, we argue that the act of ``doing nothing'' on part of an entangled quantum system is a highly non-trivial operation and that it is the essential ingredient underlying the computational speedup in the known quantum algorithms. Secondly, we show that the watched pot effect of quantum measurement theory gives the following novel computational possibility: suppose that we have a quantum computer with an on/off switch, programmed ready to solve a decision problem. Then (in certain circumstances) the mere fact that the computer would have given the answer if it were run, is enough for us to learn the answer, even though the computer is in fact not run.

arXiv:quant-ph/9805086•May 29, 1998•15 citations

Quantum Counterfactuals: Interaction-Free Measurements and Classical Logic’s Constraints

Carmen Sánchez Ovcharov, Karim Gherab-Martín, José Alejandro Fernández Cuesta

The aim of this paper is to carry out a critical analysis of the uses of the material conditionals employed to represent the counterfactual detections taking place inside Elitzur-Vaidman quantum bomb detectors in so-called quantum interaction free measurements (IFMs). We provide an exhaustive philosophical study of this classical approach focusing on its limitations. To do so, we formulate atomic propositions corresponding to the observable events of the experiments, to overcome the shortcomings of the conditional expression. Finally, we show that the standard definition ofcounterfactuality in quantum contexts based on classical logic is epistemologically too limited, presenting quantum logics as the most promising possible approach to address this type of quantum counterfactuality.

Logos & Episteme•Jan 1, 2025•0 citations

SOME REMARKS ON KNOWLEDGE AND PROBABILITY ARISING FROM COUNTERFACTUAL QUANTUM EFFECTS

Rossella Lupacchini

Can the mere possibility of a physical phenomenon affect the outcome of an experiment? In fact quantum theory presents us actual physical effects arising from "counterfactuals", that is physical effects brought about by things that might have happened, although they did not happen. How can it be? After a short outline of the quantum-mechanical description of physical reality, the occurrence of such counterfactual effects in quantum theory is illustrated by means of a Mach-Zehnder interferometer. Then these paradoxical phenomena undermining the very notion of physical event and questioning about which knowledge of physical reality can ever be obtained will be analysed using a classical possible-worlds model of knowledge and probability. Finally, a surprising application of counterfactual quantum effects producing a new kind of computing with no classical analogue will be shown.

Conference on the Foundations of Quantum Mechanics: Historical Analysis and Open Questions•May 1, 2000•0 citations

The limits of counterfactual computation

Graeme Mitchison, Richard Jozsa

We show that the protocol recently proposed by Hosten et al. does not allow all possible results of a computation to be obtained counterfactually, as was claimed. It only gives a counterfactual outcome for one of the computer outputs. However, we confirm the observation that the protocol gives some protection against decoherence. In some situations, though, it may be more effective simply to run the computer several times.

arXiv:quant-ph/0606092•Jun 10, 2006•19 citations

“Counterfactual” quantum protocols

Lev Vaidman A

The counterfactuality of recently proposed protocols is analyzed. A definition of “counterfactuality” is offered and it is argued that an interaction-free measurement (IFM) of the presence of an opaque object can be named “counterfactual”, while proposed “counterfactual” measurements of the absence of such objects are not counterfactual. The quantum key distribution protocols which rely only on measurements of the presence of the object are counterfactual, but quantum direct communication protocols are not. Therefore, the name “counterfactual” is not appropriate for recent “counterfactual” protocols which transfer quantum states by quantum direct communication.

arXiv:1605.02181•International Journal of Quantum Information•May 21, 2016•11 citations

Quantum counterfactual communication without a weak trace

David R. M. Arvidsson-Shukur, C. H. W. Barnes

The classical theories of communication rely on the assumption that there has to be a flow of particles from Bob to Alice in order for him to send a message to her. We develop a quantum protocol that allows Alice to perceive Bob's message ``counterfactually''; that is, without Alice receiving any particles that have interacted with Bob. By utilizing a setup built on results from interaction-free measurements, we outline a communication protocol whereby the information travels in the opposite direction of the emitted particles. In comparison to previous attempts on such protocols, this one is such that a weak measurement at the message source would not leave a weak trace that could be detected by Alice's receiver. While some interaction-free schemes require a large number of carefully aligned beam splitters, our protocol is realizable with two or more beam splitters. We demonstrate this protocol by numerically solving the time-dependent Schr\"odinger equation for a Hamiltonian that implements this quantum counterfactual phenomenon.

arXiv:1705.05628•Physical Review A•Dec 5, 2016•30 citations
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.
We discuss some seemingly paradoxical yet valid effects of quantum physics in information processing. Firstly, we argue that the act of ``doing nothing'' on part of an entangled quantum system is a highly non-trivial operation and that it is the essential ingredient underlying the computational speedup in the known quantum algorithms. Secondly, we show that the watched pot effect of quantum measurement theory gives the following novel computational possibility: suppose that we have a quantum computer with an on/off switch, programmed ready to solve a decision problem. Then (in certain circumstances) the mere fact that the computer would have given the answer if it were run, is enough for us to learn the answer, even though the computer is in fact not run.
The aim of this paper is to carry out a critical analysis of the uses of the material conditionals employed to represent the counterfactual detections taking place inside Elitzur-Vaidman quantum bomb detectors in so-called quantum interaction free measurements (IFMs). We provide an exhaustive philosophical study of this classical approach focusing on its limitations. To do so, we formulate atomic propositions corresponding to the observable events of the experiments, to overcome the shortcomings of the conditional expression. Finally, we show that the standard definition ofcounterfactuality in quantum contexts based on classical logic is epistemologically too limited, presenting quantum logics as the most promising possible approach to address this type of quantum counterfactuality.
Can the mere possibility of a physical phenomenon affect the outcome of an experiment? In fact quantum theory presents us actual physical effects arising from "counterfactuals", that is physical effects brought about by things that might have happened, although they did not happen. How can it be? After a short outline of the quantum-mechanical description of physical reality, the occurrence of such counterfactual effects in quantum theory is illustrated by means of a Mach-Zehnder interferometer. Then these paradoxical phenomena undermining the very notion of physical event and questioning about which knowledge of physical reality can ever be obtained will be analysed using a classical possible-worlds model of knowledge and probability. Finally, a surprising application of counterfactual quantum effects producing a new kind of computing with no classical analogue will be shown.
The counterfactuality of recently proposed protocols is analyzed. A definition of “counterfactuality” is offered and it is argued that an interaction-free measurement (IFM) of the presence of an opaque object can be named “counterfactual”, while proposed “counterfactual” measurements of the absence of such objects are not counterfactual. The quantum key distribution protocols which rely only on measurements of the presence of the object are counterfactual, but quantum direct communication protocols are not. Therefore, the name “counterfactual” is not appropriate for recent “counterfactual” protocols which transfer quantum states by quantum direct communication.
The classical theories of communication rely on the assumption that there has to be a flow of particles from Bob to Alice in order for him to send a message to her. We develop a quantum protocol that allows Alice to perceive Bob's message ``counterfactually''; that is, without Alice receiving any particles that have interacted with Bob. By utilizing a setup built on results from interaction-free measurements, we outline a communication protocol whereby the information travels in the opposite direction of the emitted particles. In comparison to previous attempts on such protocols, this one is such that a weak measurement at the message source would not leave a weak trace that could be detected by Alice's receiver. While some interaction-free schemes require a large number of carefully aligned beam splitters, our protocol is realizable with two or more beam splitters. We demonstrate this protocol by numerically solving the time-dependent Schr\"odinger equation for a Hamiltonian that implements this quantum counterfactual phenomenon.