Some relations between quantum Turing machines and Turing machines

Preprint English OPEN
Sicard, Andrés ; Vélez, Mario (1999)
  • Subject: Quantum Physics
    acm: TheoryofComputation_GENERAL | TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES | TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
    arxiv: Computer Science::General Literature | Computer Science::Computational Complexity | Computer Science::Formal Languages and Automata Theory

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.
  • References (5)

    [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.

  • Metrics
    No metrics available
Share - Bookmark