Counterfactual quantum computation
Counterfactual quantum computation is a method of inferring the result of a computation without actually running a quantum computer otherwise capable of actively performing that computation.
Conceptual origin[edit]
Physicists Graeme Mitchison and Richard Jozsa introduced the notion of counterfactual computing[1] as an application of quantum computing, founded on the concepts of counterfactual definiteness, on a re-interpretation of the Elitzur–Vaidman bomb tester thought experiment, and making theoretical use of the phenomenon of interaction-free measurement.
After seeing a talk on counterfactual computation by Jozsa at the Isaac Newton Institute, Keith Bowden of the Theoretical Physics Research Unit at Birkbeck College, University of London published a paper[2] in 1997 describing a digital computer that could be counterfactually interrogated to calculate whether a light beam would fail to pass through a maze[3] as an example of this idea.
More recently the idea of counterfactual quantum communication has been proposed and demonstrated.[4]
Outline of the method[edit]
The quantum computer may be physically implemented in arbitrary ways[5] but, to date, the common apparatus considered features a Mach–Zehnder interferometer. The quantum computer is set in a superposition of "not running" and "running" states by means such as the quantum Zeno effect. Those state histories are quantum interfered. After many repetitions of very rapid projective measurements, the "not running" state evolves to a final value imprinted into the properties of the quantum computer. Measuring that value allows for learning the result of some types of computations[6] such as Grover's algorithm even though the result was derived from the non-running state of the quantum computer.
Definition[edit]
The original formulation[1] of counterfactual quantum computation stated that a set m of measurement outcomes is a counterfactual outcome if there is only one history associated to m and that history contains only "off" (non-running) states, and there is only a single possible computational output associated to m.
A refined definition[7] of counterfactual computation expressed in procedures and conditions is: (i) Identify and label all histories (quantum paths), with as many labels as needed, which lead to the same set m of measurement outcomes, and (ii) coherently superpose all possible histories. (iii) After cancelling the terms (if any) whose complex amplitudes together add to zero, the set m of measurement outcomes is a counterfactual outcome if (iv) there are no terms left with the computer-running label in their history labels, and (v) there is only a single possible computer output associated to m.
Mirror array[edit]
In 1997, after discussions with Abner Shimony and Richard Jozsa, and inspired by the idea of the (1993) Elitzur-Vaidman bomb tester, Keith Bowden (Birkbeck College) published a paper[2] describing a digital computer that could be counterfactually interrogated to calculate whether a photon would fail to pass through a maze of mirrors.[3] This so-called mirror array replaces the tentative bomb in Elitzur and Vaidman's device (actually a Mach–Zehnder interferometer). One time in four a photon will exit the device in such a way as to indicate that the maze is not navigable, even though the photon never passed through the mirror array. The mirror array itself is set up in such a way that it is defined by an n by n matrix of bits. The output (fail or otherwise) is itself defined by a single bit. Thus the mirror array itself is an n-squared bit in, 1 bit out digital computer which calculates mazes and can be run counterfactually. Although the overall device is clearly a quantum computer, the part which is counterfactually tested is semi classical.
Experimental demonstration[edit]
In 2015, counterfactual quantum computation was demonstrated in the experimental context of "spins of a negatively charged nitrogen-vacancy color center in a diamond".[8] Previously suspected limits of efficiency were exceeded, achieving counterfactual computational efficiency of 85% with the higher efficiency foreseen in principle.[9]
References[edit]
- ^ a b Mitchison, Graeme; Jozsa, Richard (May 8, 2001). "Counterfactual computation". Proceedings of the Royal Society of London A. 457 (2009): 1175–1193. arXiv:quant-ph/9907007. Bibcode:2001RSPSA.457.1175M. CiteSeerX 10.1.1.251.9270. doi:10.1098/rspa.2000.0714. S2CID 16208575.
- ^ a b Bowden, Keith G, "Classical Computation can be Counterfactual", in Aspects I, Proc ANPA19, Cambridge 1997 (published May 1999), ISBN 0-9526215-3-3
- ^ a b Bowden, Keith (1997-03-15). "Can Schrodinger's Cat Collapse the Wavefunction?". Archived from the original on 2007-10-16. Retrieved 2007-12-08. (Revised version of "Classical Computation can be Counterfactual")
- ^ Liu Y, et al. (2012) "Experimental demonstration of counterfactual quantum communication". Phys Rev Lett 109:030501
- ^ Hosten, Onur; Rakher, Matthew T.; Barreiro, Julio T.; Peters, Nicholas A.; Kwiat, Paul G. (December 14, 2005). "Counterfactual quantum computation through quantum interrogation". Nature. 439 (7079): 949–952. Bibcode:2006Natur.439..949H. doi:10.1038/nature04523. PMID 16495993. S2CID 3042464.
- ^ Mitchison, Graeme; Jozsa, Richard (February 1, 2008). "The limits of counterfactual computation". arXiv:quant-ph/0606092.
- ^ Hosten, Onur; Rakher, Matthew T.; Barreiro, Julio T.; Peters, Nicholas A.; Kwiat, Paul (Jun 26, 2006). "Counterfactual computation revisited". arXiv:quant-ph/0607101.
- ^ Kong, Fei; Ju, Chenyong; Huang, Pu; Wang, Pengfei; Kong, Xi; Shi, Fazhan; Jiang, Liang; Du, Jiangfeng (August 21, 2015). "Experimental Realization of High-Efficiency Counterfactual Computation". Physical Review Letters. 115 (8): 080501. Bibcode:2015PhRvL.115h0501K. doi:10.1103/PhysRevLett.115.080501. PMID 26340170.
- ^ Zyga, Lisa. "Quantum computer that 'computes without running' sets efficiency record". Phys.org. Omicron Technology Limited. Retrieved 6 September 2015.
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems | |||||||||
| Quantum communication |
| ||||||||
| Quantum algorithms | |||||||||
| Quantum complexity theory | |||||||||
| Quantum processor benchmarks | |||||||||
| Quantum computing models | |||||||||
| Quantum error correction | |||||||||
| Physical implementations |
| ||||||||
| Quantum programming | |||||||||
