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

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.

Outline of Method

The quantum computer may be physically implemented in arbitrary ways^[2] but the common apparatus considered to date 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^[3] 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 (1) there is only one history associated to m and that history contains only "off" (non-running) states, and (2) there is only a single possible computational output associated to m.

A refined definition^[4] 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.

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".^[5] Previously suspected limits of efficiency were exceeded, achieving counterfactual computational efficiency of 85% with the higher efficiency foreseen in principle.^[6]

References

Quantum information science
General	Quantum computer Qubit Quantum information Quantum machine Quantum programming Timeline of quantum computing
Quantum communication	Quantum capacity Classical capacity Entanglement-assisted classical capacity Quantum channel Quantum network Quantum cryptography Quantum key distribution Quantum energy teleportation Quantum teleportation Superdense coding LOCC Entanglement distillation
Quantum algorithms	Universal quantum simulator Deutsch–Jozsa algorithm Grover's algorithm Quantum Fourier transform Shor's algorithm Simon's problem Quantum phase estimation algorithm Quantum annealing Algorithmic cooling
Quantum complexity theory	Quantum Turing machine EQP BQP QMA PostBQP
Quantum computing models	Quantum circuit Quantum gate One-way quantum computer cluster state Adiabatic quantum computation Topological quantum computer
Decoherence prevention	Quantum error correction Stabilizer codes Entanglement-Assisted Quantum Error Correction Quantum convolutional codes
Physical implementations	Quantum optics Cavity QED Circuit QED Linear optical quantum computing Ultracold atoms Trapped ion quantum computer Optical lattice Spin-based Nuclear magnetic resonance QC Kane QC Loss–DiVincenzo QC Nitrogen-vacancy center Superconducting quantum computing Charge qubit Flux qubit Phase qubit