dorsal/arxiv
View SchemaCounterfactual Computation
| Authors | Graeme Mitchison, Richard Jozsa |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9907007 |
| URL | https://arxiv.org/abs/quant-ph/9907007 |
| DOI | 10.1098/rspa.2000.0714 |
| Journal | Proc.Roy.Soc.Lond. A457 (2001) 1175-1194 |
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.
{
"annotation_id": "d29a8e45-0cc3-4527-b01c-0c14a3f5b6d6",
"date_created": "2026-03-02T18:02:48.581000Z",
"date_modified": "2026-03-02T18:02:48.581000Z",
"file_hash": "844dc28067e7040492135e5368bfbb217d08df36ba169ee32db7d56361d7dce4",
"private": false,
"record": {
"abstract": "Suppose that we are given a quantum computer programmed ready to perform a\ncomputation if it is switched on. Counterfactual computation is a process by\nwhich the result of the computation may be learnt without actually running the\ncomputer. Such processes are possible within quantum physics and to achieve\nthis effect, a computer embodying the possibility of running the computation\nmust be available, even though the computation is, in fact, not run. We study\nthe possibilities and limitations of general protocols for the counterfactual\ncomputation of decision problems (where the result r is either 0 or 1). If p(r)\ndenotes the probability of learning the result r ``for free\u0027\u0027 in a protocol\nthen one might hope to design a protocol which simultaneously has large p(0)\nand p(1). However we prove that p(0)+p(1) never exceeds 1 in any protocol and\nwe derive further constraints on p(0) and p(1) in terms of N, the number of\ntimes that the computer is not run. In particular we show that any protocol\nwith p(0)+p(1)=1-epsilon must have N tending to infinity as epsilon tends to 0.\nThese general results are illustrated with some explicit protocols for\ncounterfactual computation. We show that \"interaction-free\" measurements can be\nregarded as counterfactual computations, and our results then imply that N must\nbe large if the probability of interaction is to be close to zero. Finally, we\nconsider some ways in which our formulation of counterfactual computation can\nbe generalised.",
"arxiv_id": "quant-ph/9907007",
"authors": [
"Graeme Mitchison",
"Richard Jozsa"
],
"categories": [
"quant-ph"
],
"doi": "10.1098/rspa.2000.0714",
"journal_ref": "Proc.Roy.Soc.Lond. A457 (2001) 1175-1194",
"title": "Counterfactual Computation",
"url": "https://arxiv.org/abs/quant-ph/9907007"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f0d64bfc-d8eb-4507-8c51-7c985d3c91c2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}