Quantum Turing machine

A quantum Turing machine (QTM), also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a particular quantum Turing machine. Such Turing machines were first proposed in a 1985 paper written by Oxford University physicist David Deutsch suggesting quantum gates could function in a similar fashion to traditional digital computing binary logic gates.^[1]

Quantum Turing machines are not always used for analyzing quantum computation; the quantum circuit is a more common model; these models are computationally equivalent.^[2]

Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on transition matrices, shown by Lance Fortnow.^[3]

Iriyama, Ohya, and Volovich have developed a model of a Linear Quantum Turing Machine (LQTM). This is a generalization of a classical QTM that has mixed states and that allows irreversible transition functions. These allow the representation of quantum measurements without classical outcomes.^[4]

A quantum Turing machine with postselection was defined by Scott Aaronson, who showed that the class of polynomial time on such a machine (PostBQP) is equal to the classical complexity class PP.^[5]

References

Further reading

• Satoshi Iriyama; Masanori Ohya; Igor Volovich (2004). "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm". arXiv:quant-ph/0405191 [quant-ph].
• Abstract of Deutsch's paper
• The quantum computer – history

v t e Quantum information science General Quantum computer Qubit Quantum information Quantum programming Timeline of quantum computing Quantum communication Quantum capacity Classical capacity Entanglement-assisted classical capacity Quantum channel Quantum cryptography Quantum key distribution 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 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