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.
@article{ITA_2012__46_4_615_0,
author = {Yakary\i lmaz, Abuzer},
title = {Superiority of one-way and realtime quantum machines},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {46},
year = {2012},
pages = {615-641},
doi = {10.1051/ita/2012018},
mrnumber = {3107866},
zbl = {1279.68090},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2012__46_4_615_0}
}
Yakaryılmaz, Abuzer. Superiority of one-way and realtime quantum machines. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 615-641. doi : 10.1051/ita/2012018. http://gdmltest.u-ga.fr/item/ITA_2012__46_4_615_0/
[1] and , 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] and , Two-way finite automata with quantum and classical states. Theoret. Comput. Sci. 287 (2002) 299-311. | MR 1944456 | Zbl 1061.68047
[3] and , Superiority of exact quantum automata for promise problems. Inf. Process. Lett. 112 (2012) 289-291. | MR 2879167 | Zbl 1237.68082
[4] and , Automata : from Mathematics to Applications, in Automata and quantum computing, in preparation.
[5] , , and , Dense quantum coding and quantum finite automata. J. ACM 49 (2002) 496-511. | MR 2146458
[6] and , Quantum complexity theory. SIAM J. Comput. 26 (1997) 1411-1473. | MR 1471988 | Zbl 0895.68042
[7] and , Analogies and differences between quantum and stochastic automata. Theor. Comput. Sci. 262 (2001) 69-81. | MR 1836211 | Zbl 0983.68094
[8] , and , Small size quantum automata recognizing some regular languages. Theor. Comput. Sci. 340 (2005) 394-407. | MR 2150762 | Zbl 1087.68047
[9] , and , 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 1052.68038
[10] and , Characterizations of 1-way quantum finite automata. SIAM J. Comput. 31 (2002) 1456-1478. | MR 1936654 | Zbl 1051.68062
[11] , and , Counter machines and counter languages. Math. Syst. Theory 2 (1968) 265-283. | MR 235932 | Zbl 0165.32002
[12] , Language recognition using finite probabilistic multitape and multihead automata. Problemy Peredachi Informatsii 15 (1979) 99-106. | MR 572723 | Zbl 0449.68040
[13] , and , A new family of nonstochastic languages. Inf. Process. Lett. 110 (2010) 410-413. | MR 2662059 | Zbl 1229.68048
[14] , Quantum pushdown automata, in Proc. of SOFSEM'00 : Theory and Practice of Informatics. Lett. Notes Comput. Sci. 1963 (2000) 336-346. | Zbl 1043.68556
[15] , Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7 (1978) 311-324. | MR 513714 | Zbl 0389.68030
[16] 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] , Quantum automata with open time evolution. Int. J. Natural Comput. Res. 1 (2010) 70-85.
[18] and , 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] , 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 1784528 | Zbl 0970.81008
[20] , Multihead one-way finite automata. Theoret. Comput. Sci. 85 (1991) 135-153. | Zbl 0746.68051
[21] and , On the size of one-way quantum finite automata with periodic behaviors. Theoret. Inform. Appl. 36 (2002) 277-291. | Numdam | MR 1958244 | Zbl 1013.68088
[22] and , Quantum automata for some multiperiodic languages. Theoret. Comput. Sci. 387 (2007) 177-186. | MR 2362189 | Zbl 1148.68031
[23] and , Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. | MR 1756213 | Zbl 0939.68037
[24] , , and , Quantum versus classical pushdown automata in exact computation. IPSJDC 1 (2005) 426-435. | MR 2214562
[25] , , and , On the power of non-deterministic quantum finite automata. IEICE Trans. Inf. Syst. E85-D (2002) 327-332.
[26] , and , 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] and , Quantum Computation and Quantum Information. Cambridge University Press (2000). | MR 1796805 | Zbl 1288.81001
[28] , Introduction to Probabilistic Automata. Academic Press, New York (1971). | MR 289222 | Zbl 0234.94055
[29] , Probabilistic automata. Inf. Control 6 (1963) 230-243. | Zbl 0182.33602
[30] , On multi-head finite automata. IBM J. Res. Devel. 10 (1966) 388-394. | MR 202502 | Zbl 0168.01303
[31] and , Quantum function computation using sublogarithmic space (2010) (Poster presentation at QIP2010) [arXiv:1009.3124].
[32] and , Computation with narrow CTCs, in Unconventional Computation. Lect. Notes Comput. 6714 (2011) 201-211. | MR 2833872 | Zbl pre05908791
[33] and , Quantum counter automata. Int. J. Found. Comput. Sci. To appear. | MR 2983370 | Zbl 1279.68175
[34] , Generalized automata and stochastic languages. Proc. Am. Math. Soc. 21 (1969) 303-309. | MR 242596 | Zbl 0184.02802
[35] , Space-bounded quantum complexity. J. Comput. Syst. Sci. 59 (1999) 281-326. | MR 1723487 | Zbl 0947.68051
[36] , Quantum computational complexity, in Encyclopedia of Complexity and Systems Science, edited by R.A. Meyers. Springer (2009) 7174-7201. | MR 3074622 | Zbl 1171.93001
[37] , Personal communication (2009).
[38] , 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. | MR 3107866
[39] , Classical and Quantum Computation with Small Space Bounds. Ph.D. thesis, Boğaziçi University (2011) [arXiv:1102.0378].
[40] and , Efficient probability amplification in two-way quantum finite automata. Theoret. Comput. Sci. 410 (2009) 1932-1941. | MR 2517652 | Zbl 1163.68026
[41] and , 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 1248.68315
[42] and , Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10 (2010) 747-770. | MR 2731439 | Zbl 1236.81071
[43] and , Succinctness of two-way probabilistic and quantum finite automata. Discrete Math. Theoret. Comput. Sci. 12 (2010) 19-40. | MR 2760333 | Zbl 1286.68297
[44] and , 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] and , Unbounded-error quantum computation with small space bounds. Inf. Comput. 279 (2011) 873-892. | MR 2817180 | Zbl 1221.68092
[46] and , Proving the power of postselection. Fundam. Inform. (2012). [arXiv:1111.3125]. | MR 3088338 | Zbl 1279.68091
[47] , , and , Quantum computation with write-only memory. Natural Comput. 11 (2012) 81-94. | MR 2899203 | Zbl 1251.68117
[48] , , and , One-way probabilistic reversible and quantum one-counter automata. Theoret. Comput. Sci. 289 (2002) 963-976. | MR 1945259 | Zbl 1061.68099
[49] , and , Quantum versus deterministic counter automata. Theoret. Comput. Sci. 334 (2005) 275-297. | MR 2132952 | Zbl 1080.68060