Qtm Document.docx

Quantum Turing machine From Wikipedia, the free encyclopedia

Jump to navigationJump to search

Turing machines Machine



Turing machine equivalents



Turing machine examples



Turing machine gallery Variants



Alternating Turing machine



Differentiable neural computer



Non-deterministic Turing machine



Quantum Turing machine

 

Probabilistic Turing machine

 

Post–Turing machine

Read-only Turing machine

Read-only right moving Turing machines



Multitape Turing machine



Multi-track Turing machine



Symmetric Turing machine

 

Total Turing machine

Unambiguous Turing machine



Universal Turing machine



Zeno machine Science

 

Alan Turing

Category:Turing machine



v



t



e

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 article 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.[2]:2 These models are computationally equivalent.[3] Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on transition matrices. That is, a matrix can be specified whose product with the matrix representing a classical or probabilistic machine provides the quantum probability matrix representing the quantum machine. This was shown by Lance Fortnow.[4] 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.[5] 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.[6] Contents    

1Informal sketch 2See also 3References 4Further reading

Informal sketch[edit] Unsolved problem in physics: Is a universal quantum computer sufficient to efficiently simulate an arbitrary physical system? (more unsolved problems in physics)

A way of understanding the quantum Turing machine (QTM) is that it generalizes the classical Turing machine(TM) in the same way that the quantum finite automaton (QFA) generalizes the deterministic finite automaton(DFA). In essence, the internal states of a classical TM are replaced by pure or mixed states in a Hilbert space; the transition function is replaced by a collection of unitary matrices that map the Hilbert space to itself.[1] That is, a classical Turing machine is described by a 7-tuple

.

For a three-tape quantum Turing machine (one tape holding the input, a second tape holding intermediate calculation results, and a third tape holding output):



The set of states

is replaced by a Hilbert space.



The tape alphabet symbols are likewise replaced by a Hilbert space (usually a different Hilbert space than the set of states).



The blank symbol



The input and output symbols are usually taken as a discrete set, as in the classical system; thus, neither the input nor output to a quantum machine need be a quantum system itself.



The transition function is a generalization of a transition monoid, and is understood to be a collection of unitary matricesthat

corresponds to the zero-vector.

are automorphisms of the Hilbert space 

The initial state



The set space

.

may be either a mixed state or a pure state.

of final or accepting states is a subspace of the Hilbert .

The above is merely a sketch of a quantum Turing machine, rather than its formal definition, as it leaves vague several important details: for example, how often a measurement is performed; see for example, the difference between a measure-once and a measure-many QFA. This question of measurement affects the way in which writes to the output tape are defined.

See also[edit] 

Quantum simulator § Solving physics problems

References[edit] 1.

2.

3. 4.

5.

^ Jump up to:a b Deutsch, David (July 1985). "Quantum theory, the Church-Turing principle and the universal quantum computer" (PDF). Proceedings of the Royal Society A. 400 (1818): 97– 117. Bibcode:1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382. doi:1 0.1098/rspa.1985.0070. Archived from the original (PDF) on 2008-1123. ^ Abel Molina; John Watrous (2018). "Revisiting the simulation of quantum Turing machines by quantum circuits". arXiv:1808.01701 [cs.CC]. ^ Andrew Yao (1993). Quantum circuit complexity. 34th Annual Symposium on Foundations of Computer Science. pp. 352–361. ^ Fortnow, Lance (2003). "One Complexity Theorist's View of Quantum Computing". Theoretical Computer Science. 292 (3): 597– 610. doi:10.1016/S0304-3975(01)00377-2. ^ Simon Perdrix; Philippe Jorrand (2007-04-04). "ClassicallyControlled Quantum Computation". Math. Struct. In Comp. Science. 16 (4): 601–620. arXiv:quantph/0407008. doi:10.1017/S096012950600538X. also Simon Perdrix and Philippe Jorrand (2006). "Classically-Controlled Quantum

6.

Computation" (PDF). Math. Struct. In Comp. Science. 16(4): 601– 620. CiteSeerX 10.1.1.252.1823. doi:10.1017/S096012950600538X. ^ Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 (2063): 3473–3482. arXiv:quantph/0412187. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005. 1546. Preprint available at [1]

Further reading[edit] 







Molina, Abel; Watrous, John (2018). "Revisiting the simulation of quantum Turing machines by quantum circuits". arXiv:1808.01701 [cs.CC]. Iriyama, Satoshi; Ohya, Masanori; Volovich, Igor (2004). "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm". arXiv:quant-ph/0405191. Deutsch, D. (1985). "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer". Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. 400 (1818): 97– 117. Bibcode:1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382. do i:10.1098/rspa.1985.0070. JSTOR 2397601. The quantum computer – history hide

Quantum information science Quantum computing Qubit physical vs. logical DiVincenzo's criteria Quantum information Quantum programming Quantum processors Cloud-based quantum computing Timeline of quantum computing Quantum capacity Classical capacity Entanglement-assisted classical capacity Quantum channel

Quantum network Quantum cryptography Quantum key distribution BB84 SARG04 Kak's three stage protocol Quantum teleportation Superdense coding LOCC Entanglement distillation Universal quantum simulator Deutsch–Jozsa algorithm Grover's algorithm Quantum Fourier transform Shor's algorithm Simon's problem Quantum phase estimation algorithm Quantum counting algorithm Quantum annealing Quantum algorithm for linear systems of equations Amplitude amplification Quantum Turing machine EQP BQP QMA PostBQP QIP Quantum circuit Quantum logic gate One-way quantum computer cluster state Adiabatic quantum computation Topological quantum computer

Stabilizer codes Entanglement-Assisted Quantum Error Correction Shor code Steane code CSS code Quantum convolutional codes Toric code



Cavity QED



Circuit QED

Quantum optics

Linear optical quantum computing



KLM protocol



Boson sampling



Trapped ion quantum computer

Ultracold atoms



Optical lattice



Nuclear magnetic resonance QC



Kane QC

Spin-based



Loss–DiVincenzo QC



Nitrogen-vacancy center



Charge qubit

Superconducting



Flux qubit

quantum



Phase qubit

computing



Transmon

libquantum OpenQASM Q#

Categories: 

Turing machine



Quantum complexity theory

Navigation menu 

Not logged in



Talk



Contributions

  



Create account



Log in

 

Article Talk



This page was last edited on 11 March 2019, at 20:10 (UTC).

Read Edit View history

Search                              

Main page Contents Featured content Current events Random article Donate to Wikipedia Wikipedia store Interaction Help About Wikipedia Community portal Recent changes Contact page Tools What links here Related changes Upload file Special pages Permanent link Page information Wikidata item Cite this page Print/export Create a book Download as PDF Printable version Languages ‫العربية‬ 한국어 Italiano Português Русский Tiếng Việt 中文

5 more Edit links



Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.



Privacy policy



About Wikipedia



Disclaimers



Contact Wikipedia



Developers



Cookie statement



Mobile view

 