publication . Preprint . 1999

Some relations between quantum Turing machines and Turing machines

Sicard, Andrés; Vélez, Mario;
Open Access English
  • Published: 02 Dec 1999
Abstract
For quantum Turing machines we present three elements: Its components, its time evolution operator and its local transition function. The components are related with the components of deterministic Turing machines, the time evolution operator is related with the evolution of reversible Turing machines and the local transition function is related with the transition function of probabilistic and reversible Turing machines.
Subjects
arXiv: Computer Science::Computational ComplexityComputer Science::General LiteratureComputer Science::Formal Languages and Automata Theory
ACM Computing Classification System: TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoryofComputation_GENERALTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
free text keywords: Quantum Physics
Related Organizations
Download from

[1] Bersntein, E., and Vazarini, U. Quantum Complexity Theory. Siam Journal on Computing 26, 5 (Octuber 1997), 1411-1473.

[2] Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A400 (1985), 97-117.

[3] Gill, J. Computational complexity of probabilistic turing machines. Siam Journal on Computing 6, 4 (December 1977), 675-695.

[4] Ozawa, M., and Nishimura, H. Local Transition Function of Qunatum Turing Machines. http://xxx.lanl.gov/ps/quant-ph/9811069.ps, 1999.

[5] Turing, A. M. On computable numbers, with an application to the entscheidungsproblem. Proc. London Math. Soc (1936). A correction, ibid, vol 43. 1936-1937. pa´gs. 544 - 546.

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue