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/0606092

The limits of counterfactual computation

Graeme Mitchison, Richard Jozsa

Published Jun 10, 2006• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0606092

Related papers

Counterfactual computation revisited

Onur Hosten, Matthew T. Rakher, Julio T. Barreiro +2 more

Mitchison and Jozsa recently suggested that the "chained-Zeno" counterfactual computation protocol recently proposed by Hosten et al. is counterfactual for only one output of the computer. This claim was based on the existing abstract algebraic definition of counterfactual computation, and indeed according to this definition, their argument is correct. However, a more general definition (physically adequate) for counterfactual computation is implicitly assumed by Hosten et. al. Here we explain in detail why the protocol is counterfactual and how the "history tracking" method of the existing description inadequately represents the physics underlying the protocol. Consequently, we propose a modified definition of counterfactual computation. Finally, we comment on one of the most interesting aspects of the error-correcting protocol.

arXiv:quant-ph/0607101•Jul 14, 2006•5 citations

Limits to quantum computation due to decoherence

Martin Bodo Plenio, P. L. Knight

Springer eBooks•Jun 1, 2001•1 citation

Impossibility of the Counterfactual Computation for All Possible Outcomes

Lev Vaidman A

A recent proposal for counterfactual computation [O. Hosten et al. Nature (London) 439, 949 (2006) is analyzed. It is argued that the method does not provide counterfactual computation for all possible outcomes. The explanation involves a novel paradoxical feature of pre- and postselected quantum particles: The particle can reach a certain location without being on the path that leads to this location.

arXiv:quant-ph/0610174•Physical Review Letters•Apr 18, 2007•58 citations

Simulating the Effect of Decoherence and Inaccuracies on a Quantum Computer

Kevin Obenland, Alvin M. Despain

Lecture notes in computer science•Jan 1, 1999•17 citations

Counterfactual computation

Graeme Mitchison, Richard Jozsa

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.

arXiv:quant-ph/9907007•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•May 8, 2001•70 citations

DECOHERENCE AND ITS IMPLICATIONS IN QUANTUM COMPUTATION AND INFORMATION TRANSFER

Yakir Aharonov, Alonso Botero, Sandu Popescu +2 more

•Jan 1, 2001•0 citations
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.
Mitchison and Jozsa recently suggested that the "chained-Zeno" counterfactual computation protocol recently proposed by Hosten et al. is counterfactual for only one output of the computer. This claim was based on the existing abstract algebraic definition of counterfactual computation, and indeed according to this definition, their argument is correct. However, a more general definition (physically adequate) for counterfactual computation is implicitly assumed by Hosten et. al. Here we explain in detail why the protocol is counterfactual and how the "history tracking" method of the existing description inadequately represents the physics underlying the protocol. Consequently, we propose a modified definition of counterfactual computation. Finally, we comment on one of the most interesting aspects of the error-correcting protocol.
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.