Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines

Preprint English OPEN
Qiu, Daowen;
(2005)
  • Subject: Quantum Physics
    acm: TheoryofComputation_GENERAL | ComputerSystemsOrganization_MISCELLANEOUS

As was well known, in classical computation, Turing machines, circuits, multi-stack machines, and multi-counter machines are equivalent, that is, they can simulate each other in polynomial time. In quantum computation, Yao [11] first proved that for any quantum Turing m... View more
  • References (12)
    12 references, page 1 of 2

    [1] E. Bernstein and U. Vazirani, Quantum complexity theory, SIAM J. Comput. 26 (1997) 1411-1473.

    [2] P.C. Fischer, Turing machine with restricted memory access, Information and Control 9 (4) (1966) 364-379.

    [3] M. Golovkins, Quantum Pushdown Automata, in: Proc. 27th Conf. on Current Trends in Theory and Practice of Informatics, Milovy, Lecture Notes in Computer Science, Vol. 1963, Spring-Verlag, Berlin, 2000, pp. 336-346.

    [4] J. Gruska, Quantum Computing, McGraw-Hill, London, 1999.

    [5] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addision-Wesley, New York, 1979.

    [6] M. Kravtsev, Quantum finite one-counter automata, in: SOFSEM'99, Lecture Notes in Computer Science, Vol.1725, Springer-Verlag, Berlin, 1999, pp.431-440.

    [7] M.L. Minsky, Recursive unsolvability of Post's problem of 'tag' and other topics in the theory of Turing machines, Annals of Mathematics 74 (3) (1961) 437-455.

    [8] C. Moore and J.P. Crutchfield, Quantum automata and quantum grammars, Theoret. Comput. Sci. 237 (2000) 275-306. Also quant-ph/9707031, 1997.

    [9] D.W. Qiu and M.S. Ying, Characterization of quantum automata, Theoret. Comput. Sci. 312 (2004) 479-489.

    [10] T. Yamasaki, H. Kobayashi, H. Imai, Quantum versus deterministic counter automata, Theoret. Comput. Sci. to appear.

  • Metrics
Share - Bookmark