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  first proved that for any quantum Turing m... View more
 E. Bernstein and U. Vazirani, Quantum complexity theory, SIAM J. Comput. 26 (1997) 1411-1473.
 P.C. Fischer, Turing machine with restricted memory access, Information and Control 9 (4) (1966) 364-379.
 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.
 J. Gruska, Quantum Computing, McGraw-Hill, London, 1999.
 J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addision-Wesley, New York, 1979.
 M. Kravtsev, Quantum finite one-counter automata, in: SOFSEM'99, Lecture Notes in Computer Science, Vol.1725, Springer-Verlag, Berlin, 1999, pp.431-440.
 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.
 C. Moore and J.P. Crutchfield, Quantum automata and quantum grammars, Theoret. Comput. Sci. 237 (2000) 275-306. Also quant-ph/9707031, 1997.
 D.W. Qiu and M.S. Ying, Characterization of quantum automata, Theoret. Comput. Sci. 312 (2004) 479-489.
 T. Yamasaki, H. Kobayashi, H. Imai, Quantum versus deterministic counter automata, Theoret. Comput. Sci. to appear.