Counterfactual quantum computation

Last updated

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.

Contents

Conceptual origin

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

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

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

In 1997, after discussions with Abner Shimony and Richard Jozsa, and inspired by the idea of the (1993) Elitzur-Vaidman bomb tester, Bowden 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

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]

Related Research Articles

<span class="mw-page-title-main">Quantum teleportation</span> Physical phenomenon

Quantum teleportation is a technique for transferring quantum information from a sender at one location to a receiver some distance away. While teleportation is commonly portrayed in science fiction as a means to transfer physical objects from one location to the next, quantum teleportation only transfers quantum information. The sender does not have to know the particular quantum state being transferred. Moreover, the location of the recipient can be unknown, but to complete the quantum teleportation, classical information needs to be sent from sender to receiver. Because classical information needs to be sent, quantum teleportation cannot occur faster than the speed of light.

In quantum computing, a qubit or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. Examples include the spin of the electron in which the two levels can be taken as spin up and spin down; or the polarization of a single photon in which the two states can be taken to be the vertical polarization and the horizontal polarization. In a classical system, a bit would have to be in one state or the other. However, quantum mechanics allows the qubit to be in a coherent superposition of both states simultaneously, a property that is fundamental to quantum mechanics and quantum computing.

In quantum mechanics, counterfactual definiteness (CFD) is the ability to speak "meaningfully" of the definiteness of the results of measurements that have not been performed. The term "counterfactual definiteness" is used in discussions of physics calculations, especially those related to the phenomenon called quantum entanglement and those related to the Bell inequalities. In such discussions "meaningfully" means the ability to treat these unmeasured results on an equal footing with measured results in statistical calculations. It is this aspect of counterfactual definiteness that is of direct relevance to physics and mathematical models of physical systems and not philosophical concerns regarding the meaning of unmeasured results.

This is a timeline of quantum computing.

<span class="mw-page-title-main">Mach–Zehnder interferometer</span> Device to determine relative phase shift

The Mach–Zehnder interferometer is a device used to determine the relative phase shift variations between two collimated beams derived by splitting light from a single source. The interferometer has been used, among other things, to measure phase shifts between the two beams caused by a sample or a change in length of one of the paths. The apparatus is named after the physicists Ludwig Mach and Ludwig Zehnder; Zehnder's proposal in an 1891 article was refined by Mach in an 1892 article. Demonstrations of Mach–Zehnder interferometry with particles other than photons had been demonstrated as well in multiple experiments.

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

Quantum error correction (QEC) is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is theorised as essential to achieve fault tolerant quantum computing that can reduce the effects of noise on stored quantum information, faulty quantum gates, faulty quantum preparation, and faulty measurements. This would allow algorithms of greater circuit depth.

<span class="mw-page-title-main">Artur Ekert</span> Polish-British physicist (born 1961)

Artur Konrad Ekert is a British-Polish professor of quantum physics at the Mathematical Institute, University of Oxford, professorial fellow in quantum physics and cryptography at Merton College, Oxford, Lee Kong Chian Centennial Professor at the National University of Singapore and the founding director of the Centre for Quantum Technologies (CQT). His research interests extend over most aspects of information processing in quantum-mechanical systems, with a focus on quantum communication and quantum computation. He is best known as one of the pioneers of quantum cryptography.

<span class="mw-page-title-main">Elitzur–Vaidman bomb tester</span> Quantum mechanics thought experiment

The Elitzur–Vaidman bomb-tester is a quantum mechanics thought experiment that uses interaction-free measurements to verify that a bomb is functional without having to detonate it. It was conceived in 1993 by Avshalom Elitzur and Lev Vaidman. Since their publication, real-world experiments have confirmed that their theoretical method works as predicted.

In physics, interaction-free measurement is a type of measurement in quantum mechanics that detects the position, presence, or state of an object without an interaction occurring between it and the measuring device. Examples include the Renninger negative-result experiment, the Elitzur–Vaidman bomb-testing problem, and certain double-cavity optical systems, such as Hardy's paradox.

<span class="mw-page-title-main">Lev Vaidman</span> Russian-Israeli physicist

Lev Vaidman is a Russian-Israeli physicist and Professor at Tel Aviv University, Israel. He is noted for his theoretical work in the area of fundamentals of quantum mechanics, which includes quantum teleportation, the Elitzur–Vaidman bomb tester, and the weak values. He was a member of the Editorial Advisory Board of The American Journal of Physics from 2007 to 2009. In 2010, the Elitzur–Vaidman bomb tester was chosen as one of the "Seven Wonders of the Quantum World" by New Scientist Magazine.

Time-bin encoding is a technique used in quantum information science to encode a qubit of information on a photon. Quantum information science makes use of qubits as a basic resource similar to bits in classical computing. Qubits are any two-level quantum mechanical system; there are many different physical implementations of qubits, one of which is time-bin encoding.

In quantum mechanics, a weak value is a quantity related to a shift of a measuring device's pointer when usually there is pre- and postselection. It should not be confused with a weak measurement, which is often defined in conjunction. The weak value was first defined by Yakir Aharonov, David Albert, and Lev Vaidman, published in Physical Review Letters 1988, and is related to the two-state vector formalism. There is also a way to obtain weak values without postselection.

<span class="mw-page-title-main">One-way quantum computer</span> Method of quantum computing

The one-way or measurement-based quantum computer (MBQC) is a method of quantum computing that first prepares an entangled resource state, usually a cluster state or graph state, then performs single qubit measurements on it. It is "one-way" because the resource state is destroyed by the measurements.

SARG04 is a 2004 quantum cryptography protocol derived from the first protocol of that kind, BB84.

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical communication. For example, it is impossible to copy data encoded in a quantum state. If one attempts to read the encoded data, the quantum state will be changed due to wave function collapse. This could be used to detect eavesdropping in quantum key distribution (QKD).

Linear optical quantum computing or linear optics quantum computation (LOQC) is a paradigm of quantum computation, allowing universal quantum computation. LOQC uses photons as information carriers, mainly uses linear optical elements, or optical instruments to process quantum information, and uses photon detectors and quantum memories to detect and store quantum information.

Boson sampling is a restricted model of non-universal quantum computation introduced by Scott Aaronson and Alex Arkhipov after the original work of Lidror Troyansky and Naftali Tishby, that explored possible usage of boson scattering to evaluate expectation values of permanents of matrices. The model consists of sampling from the probability distribution of identical bosons scattered by a linear interferometer. Although the problem is well defined for any bosonic particles, its photonic version is currently considered as the most promising platform for a scalable implementation of a boson sampling device, which makes it a non-universal approach to linear optical quantum computing. Moreover, while not universal, the boson sampling scheme is strongly believed to implement computing tasks which are hard to implement with classical computers by using far fewer physical resources than a full linear-optical quantum computing setup. This advantage makes it an ideal candidate for demonstrating the power of quantum computation in the near term.

The KLM scheme or KLM protocol is an implementation of linear optical quantum computing (LOQC), developed in 2000 by Emanuel Knill, Raymond Laflamme and Gerard J. Milburn. This protocol makes it possible to create universal quantum computers solely with linear optical tools. The KLM protocol uses linear optical elements, single-photon sources and photon detectors as resources to construct a quantum computation scheme involving only ancilla resources, quantum teleportations and error corrections.

Consider two remote players, connected by a channel, that don't trust each other. The problem of them agreeing on a random bit by exchanging messages over this channel, without relying on any trusted third party, is called the coin flipping problem in cryptography. Quantum coin flipping uses the principles of quantum mechanics to encrypt messages for secure communication. It is a cryptographic primitive which can be used to construct more complex and useful cryptographic protocols, e.g. Quantum Byzantine agreement.

References

  1. 1 2 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.
  2. 1 2 Bowden, Keith G, "Classical Computation can be Counterfactual", in Aspects I, Proc ANPA19, Cambridge 1997 (published May 1999), ISBN   0-9526215-3-3
  3. 1 2 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")
  4. ↑ Liu Y, et al. (2012) "Experimental demonstration of counterfactual quantum communication". Phys Rev Lett 109:030501
  5. ↑ 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.
  6. ↑ Mitchison, Graeme; Jozsa, Richard (February 1, 2008). "The limits of counterfactual computation". arXiv: quant-ph/0606092 .
  7. ↑ Hosten, Onur; Rakher, Matthew T.; Barreiro, Julio T.; Peters, Nicholas A.; Kwiat, Paul (Jun 26, 2006). "Counterfactual computation revisited". arXiv: quant-ph/0607101 .
  8. ↑ 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.
  9. ↑ Zyga, Lisa. "Quantum computer that 'computes without running' sets efficiency record". Phys.org. Omicron Technology Limited. Retrieved 6 September 2015.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.