publication . Preprint . 2005

Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines

Qiu, Daowen;
Open Access English
  • Published: 29 Jan 2005
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 machines $M$, there exists quantum Boolean circuit $(n,t)$-simulating $M$, where $n$ denotes the length of input strings, and $t$ is the number of move steps before machine stopping. However, the simulations of quantum Turing machines by quantum multi-stack machines and quantum multi-counter machines have not been considered, and quantum multi-stack machines have not been established, either. Thoug...
ACM Computing Classification System: TheoryofComputation_GENERALComputerSystemsOrganization_MISCELLANEOUS
free text keywords: Quantum Physics
Download from

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

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

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

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

[11] A.C. Yao, Quantum circuit complexity, in: Proc. 34th IEEE Symp. on Foundations of Computer science, 1993, pp. 352-361.

[12] T. Yamakami, A Foundation of Programming a Multi-Tape Quantum Turing Machine, in: MFCS'99, Lecture Notes in Computer Science, Vol.1672, Springer-Verlag, Berlin, 1999, pp. 430-441. More precisely, we show that VσM2 is a unitary operator on l2(CM2) = HQ2⊗H[0,r−1]Z⊗HN. For any (qi,ni1,ni2) ∈ Q2 × [0,r − 1]Z × N, i = 1,2, n(q, n1, n2, . . . , nr) : q ∈ Q, ni ∈ N, i = 1, 2, . . . , r, Pir=−11 ni ≤ 1o and therefore, Vσ is a linear operator on l2(CM2 ) where CM2 = n|qi|n1i|n2i . . . |nri : q ∈ Q, ni ∈ N, i = 1, 2, . . . , r, Pjr=−11 nj ≤ 1o, that is, l2(CM2 ) = HQ ⊗ (H{0,1})⊗(r−1) ⊗ HN. [OpenAIRE]

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