Superiority of one-way and realtime quantum machines

Yakaryılmaz, Abuzer

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 4, pp. 615-641.

In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.

[1] A. Ambainis and R. Freivalds, 1-way quantum finite automata : strengths, weaknesses and generalizations, in Proc. of 39th Annual Symposium on Foundations of Computer Science, FOCS'98 (1998) 332-341.

[2] A. Ambainis and J. Watrous, Two-way finite automata with quantum and classical states. Theoret. Comput. Sci. 287 (2002) 299-311. | MR | Zbl

[3] A. Ambainis and A. Yakaryılmaz, Superiority of exact quantum automata for promise problems. Inf. Process. Lett. 112 (2012) 289-291. | MR | Zbl

[4] A. Ambainis and A. Yakaryılmaz, Automata : from Mathematics to Applications, in Automata and quantum computing, in preparation.

[5] A. Ambainis, A. Nayak, A. Ta-Shma and U. Vazirani, Dense quantum coding and quantum finite automata. J. ACM 49 (2002) 496-511. | MR

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

[7] A. Bertoni and M. Carpentieri, Analogies and differences between quantum and stochastic automata. Theor. Comput. Sci. 262 (2001) 69-81. | MR | Zbl

[8] A. Bertoni, C. Mereghetti and B. Palano, Small size quantum automata recognizing some regular languages. Theor. Comput. Sci. 340 (2005) 394-407. | MR | Zbl

[9] R. Bonner, R. Freivalds and M. Kravtsev, Quantum versus probabilistic one-way finite automata with counter, in Proc. of SOFSEM 2007 : Theory and Practice of Computer Science. Lett. Notes Comput. Sci. 2234 (2001) 181-190. | Zbl

[10] A. Brodsky and N. Pippenger, Characterizations of 1-way quantum finite automata. SIAM J. Comput. 31 (2002) 1456-1478. | MR | Zbl

[11] P.C. Fischer, A.R. Meyer and A.L. Rosenberg, Counter machines and counter languages. Math. Syst. Theory 2 (1968) 265-283. | MR | Zbl

[12] R. Freivalds, Language recognition using finite probabilistic multitape and multihead automata. Problemy Peredachi Informatsii 15 (1979) 99-106. | MR | Zbl

[13] R. Freivalds, A. Yakaryılmaz and A.C.C. Say, A new family of nonstochastic languages. Inf. Process. Lett. 110 (2010) 410-413. | MR | Zbl

[14] M. Golovkins, Quantum pushdown automata, in Proc. of SOFSEM'00 : Theory and Practice of Informatics. Lett. Notes Comput. Sci. 1963 (2000) 336-346. | Zbl

[15] S.A. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7 (1978) 311-324. | MR | Zbl

[16] K. Hamaguchi M. Nakanishi and T. Indoh, On the power of quantum pushdown automata with a classical stack and 1.5-way quantum finite automata. Technical Report NAIST-IS-TR2001005, Nara Institute of Science and Technology (2001). Available on http://isw3.naist.jp/IS/TechReport/report/2001005.ps.

[17] M. Hirvensalo, Quantum automata with open time evolution. Int. J. Natural Comput. Res. 1 (2010) 70-85.

[18] A. Kondacs and J. Watrous, On the power of quantum finite state automata, in Proc. of 38th Annual Symposium on Foundations of Computer Science, FOCS'97. Lett. Notes Comput. Sci. (1997) 66-75.

[19] M. Kravtsev, Quantum finite one-counter automata, in Proc. of SOFSEM'99 : Theory and Practice of Computer Science. Lect. Notes Comput. Sci. 1725 (1999) 431-440. | MR | Zbl

[20] M. Kutyłowski, Multihead one-way finite automata. Theoret. Comput. Sci. 85 (1991) 135-153. | Zbl

[21] C. Mereghetti and B. Palano, On the size of one-way quantum finite automata with periodic behaviors. Theoret. Inform. Appl. 36 (2002) 277-291. | Numdam | MR | Zbl

[22] C. Mereghetti and B. Palano, Quantum automata for some multiperiodic languages. Theoret. Comput. Sci. 387 (2007) 177-186. | MR | Zbl

[23] C. Moore and J.P. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. | MR | Zbl

[24] Y. Murakami, M. Nakanishi, S. Yamashita and K. Watanabe, Quantum versus classical pushdown automata in exact computation. IPSJDC 1 (2005) 426-435. | MR

[25] M. Nakanishi, T. Indoh, K. Hamaguchi and T. Kashiwabara, On the power of non-deterministic quantum finite automata. IEICE Trans. Inf. Syst. E85-D (2002) 327-332.

[26] M. Nakanishi, K. Hamaguchi and T. Kashiwabara, Expressive power of quantum pushdown automata with classical stack operations under the perfect-soundness condition. IEICE Trans. Inf. Syst. E89-D (2006) 1120-1127.

[27] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press (2000). | MR | Zbl

[28] A. Paz, Introduction to Probabilistic Automata. Academic Press, New York (1971). | MR | Zbl

[29] M.O. Rabin, Probabilistic automata. Inf. Control 6 (1963) 230-243. | Zbl

[30] A.L. Rosenberg, On multi-head finite automata. IBM J. Res. Devel. 10 (1966) 388-394. | MR | Zbl

[31] A.C.C. Say and A. Yakaryılmaz, Quantum function computation using sublogarithmic space (2010) (Poster presentation at QIP2010) [arXiv:1009.3124].

[32] A.C.C. Say and A. Yakaryılmaz, Computation with narrow CTCs, in Unconventional Computation. Lect. Notes Comput. 6714 (2011) 201-211. | MR

[33] A.C.C. Say and A. Yakaryılmaz, Quantum counter automata. Int. J. Found. Comput. Sci. To appear. | MR | Zbl

[34] P. Turakainen, Generalized automata and stochastic languages. Proc. Am. Math. Soc. 21 (1969) 303-309. | MR | Zbl

[35] J. Watrous, Space-bounded quantum complexity. J. Comput. Syst. Sci. 59 (1999) 281-326. | MR | Zbl

[36] J. Watrous, Quantum computational complexity, in Encyclopedia of Complexity and Systems Science, edited by R.A. Meyers. Springer (2009) 7174-7201. | MR | Zbl

[37] J. Watrous, Personal communication (2009).

[38] A. Yakaryılmaz, Superiority of one-way and realtime quantum machines and new directions, in Third Workshop on Non-Classical Models for Automata and Applications (2011) 209-224.

[39] A. Yakaryılmaz, Classical and Quantum Computation with Small Space Bounds. Ph.D. thesis, Boğaziçi University (2011) [arXiv:1102.0378].

[40] A. Yakaryılmaz and A.C.C. Say, Efficient probability amplification in two-way quantum finite automata. Theoret. Comput. Sci. 410 (2009) 1932-1941. | MR | Zbl

[41] A. Yakaryılmaz and A.C.C. Say, Languages recognized with unbounded error by quantum finite automata, in Proc. of 4th International Computer Science Symposium in Russia, CSR'09. Lect. Notes Comput. Sci. 5675 (2009) 356-367. | Zbl

[42] A. Yakaryılmaz and A.C.C. Say, Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10 (2010) 747-770. | MR | Zbl

[43] A. Yakaryılmaz and A.C.C. Say, Succinctness of two-way probabilistic and quantum finite automata. Discrete Math. Theoret. Comput. Sci. 12 (2010) 19-40. | MR | Zbl

[44] A. Yakaryılmaz and A.C.C. Say, Probabilistic and quantum finite automata with postselection. Technical Report [arXiv:1102.0666] (2011). (A preliminary version of this paper appeared in Proc. of Randomized and Quantum Computation (satellite workshop of MFCS and CSL)) (2010) 14-24.

[45] A. Yakaryılmaz and A.C.C. Say, Unbounded-error quantum computation with small space bounds. Inf. Comput. 279 (2011) 873-892. | MR | Zbl

[46] A. Yakaryılmaz and A.C.C. Say, Proving the power of postselection. Fundam. Inform. (2012). [arXiv:1111.3125]. | MR | Zbl

[47] A. Yakaryılmaz, R. Freivalds, A.C.C. Say and R. Agadzanyan, Quantum computation with write-only memory. Natural Comput. 11 (2012) 81-94. | MR | Zbl

[48] T. Yamasaki, H. Kobayashi, Y. Tokunaga and H. Imai, One-way probabilistic reversible and quantum one-counter automata. Theoret. Comput. Sci. 289 (2002) 963-976. | MR | Zbl

[49] T. Yamasaki, H. Kobayashi and H. Imai, Quantum versus deterministic counter automata. Theoret. Comput. Sci. 334 (2005) 275-297. | MR | Zbl