Quantum Turing machine

From Wikipedia, the free encyclopedia

A quantum Turing machine 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; thus, quantum Turing machines have the same relation to quantum computation that normal Turing machines have to classical computation.

Quantum Turing machines are not always used for analyzing quantum computation; the quantum circuit is a more common model. Both of these models are computationally equivalent^{[citation needed]}.

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

[edit] References

1. ^ Lance Fortnow (2003). "One Complexity Theorist's View of Quantum Computing". Theoretical Computer Science 292: 597--610.