Hostname: page-component-8448b6f56d-t5pn6 Total loading time: 0 Render date: 2024-04-23T22:59:40.363Z Has data issue: false hasContentIssue false
  • English
  • Français

Superiority of one-way and realtime quantum machines∗∗∗

Published online by Cambridge University Press:  08 October 2012

Abuzer Yakaryılmaz
Abuzer Yakaryılmaz*
Affiliation:
University of Latvia, Faculty of Computing, Raina bulv. 19, LV-1586 Rīga, Latvia. abuzer@lu.lv
Get access

Abstract

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.

Keywords

Quantum computationquantum automatablind counter automatamultihead finite automatanondeterminismbounded error
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 46 , Issue 4: Special Issue: Non-Classical Models of Automata and Applications III (NCMA-2011) , October 2012 , pp. 615 - 641
Copyright
© EDP Sciences 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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. CrossRef
Ambainis, A. and Watrous, J., Two-way finite automata with quantum and classical states. Theoret. Comput. Sci. 287 (2002) 299–311. Google Scholar
Ambainis, A. and Yakaryılmaz, A., Superiority of exact quantum automata for promise problems. Inf. Process. Lett. 112 (2012) 289–291. Google Scholar
A. Ambainis and A. Yakaryılmaz, Automata : from Mathematics to Applications, in Automata and quantum computing, in preparation.
Ambainis, A., Nayak, A., Ta-Shma, A. and Vazirani, U., Dense quantum coding and quantum finite automata. J. ACM 49 (2002) 496–511. Google Scholar
Bernstein, E. and Vazirani, U., Quantum complexity theory. SIAM J. Comput. 26 (1997) 1411–1473. Google Scholar
Bertoni, A. and Carpentieri, M., Analogies and differences between quantum and stochastic automata. Theor. Comput. Sci. 262 (2001) 69–81. Google Scholar
Bertoni, A., Mereghetti, C. and Palano, B., Small size quantum automata recognizing some regular languages. Theor. Comput. Sci. 340 (2005) 394–407. Google Scholar
Bonner, R., Freivalds, R. and Kravtsev, M., 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. Google Scholar
Brodsky, A. and Pippenger, N., Characterizations of 1-way quantum finite automata. SIAM J. Comput. 31 (2002) 1456–1478. Google Scholar
Fischer, P.C., Meyer, A.R. and Rosenberg, A.L., Counter machines and counter languages. Math. Syst. Theory 2 (1968) 265–283. Google Scholar
Freivalds, R., Language recognition using finite probabilistic multitape and multihead automata. Problemy Peredachi Informatsii 15 (1979) 99–106. Google Scholar
Freivalds, R., Yakaryılmaz, A. and Say, A.C.C., A new family of nonstochastic languages. Inf. Process. Lett. 110 (2010) 410–413. Google Scholar
Golovkins, M., Quantum pushdown automata, in Proc. of SOFSEM’00 : Theory and Practice of Informatics. Lett. Notes Comput. Sci. 1963 (2000) 336–346. Google Scholar
Greibach, S.A., Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7 (1978) 311–324. Google Scholar
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.
Hirvensalo, M., Quantum automata with open time evolution. Int. J. Natural Comput. Res. 1 (2010) 70–85. Google Scholar
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.
Kravtsev, M., Quantum finite one-counter automata, in Proc. of SOFSEM’99 : Theory and Practice of Computer Science. Lect. Notes Comput. Sci. 1725 (1999) 431–440. Google Scholar
Kutyłowski, M., Multihead one-way finite automata. Theoret. Comput. Sci. 85 (1991) 135–153. Google Scholar
Mereghetti, C. and Palano, B., On the size of one-way quantum finite automata with periodic behaviors. Theoret. Inform. Appl. 36 (2002) 277–291. Google Scholar
Mereghetti, C. and Palano, B., Quantum automata for some multiperiodic languages. Theoret. Comput. Sci. 387 (2007) 177–186. Google Scholar
Moore, C. and Crutchfield, J.P., Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275–306. Google Scholar
Murakami, Y., Nakanishi, M., Yamashita, S. and Watanabe, K., Quantum versus classical pushdown automata in exact computation. IPSJDC 1 (2005) 426–435. Google Scholar
Nakanishi, M., Indoh, T., Hamaguchi, K. and Kashiwabara, T., On the power of non-deterministic quantum finite automata. IEICE Trans. Inf. Syst. E85-D (2002) 327–332. Google Scholar
Nakanishi, M., Hamaguchi, K. and Kashiwabara, T., Expressive power of quantum pushdown automata with classical stack operations under the perfect-soundness condition. IEICE Trans. Inf. Syst. E89-D (2006) 1120–1127. Google Scholar
M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press (2000).
A. Paz, Introduction to Probabilistic Automata. Academic Press, New York (1971).
Rabin, M.O., Probabilistic automata. Inf. Control 6 (1963) 230–243. Google Scholar
Rosenberg, A.L., On multi-head finite automata. IBM J. Res. Devel. 10 (1966) 388–394. Google Scholar
A.C.C. Say and A. Yakaryılmaz, Quantum function computation using sublogarithmic space (2010) (Poster presentation at QIP2010) [arXiv:1009.3124].
Say, A.C.C. and Yakaryılmaz, A., Computation with narrow CTCs, in Unconventional Computation. Lect. Notes Comput. 6714 (2011) 201–211. Google Scholar
A.C.C. Say and A. Yakaryılmaz, Quantum counter automata. Int. J. Found. Comput. Sci. To appear.
Turakainen, P., Generalized automata and stochastic languages. Proc. Am. Math. Soc. 21 (1969) 303–309. Google Scholar
Watrous, J., Space-bounded quantum complexity. J. Comput. Syst. Sci. 59 (1999) 281–326. Google Scholar
J. Watrous, Quantum computational complexity, in Encyclopedia of Complexity and Systems Science, edited by R.A. Meyers. Springer (2009) 7174–7201.
J. Watrous, Personal communication (2009).
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.
A. Yakaryılmaz, Classical and Quantum Computation with Small Space Bounds. Ph.D. thesis, Boğaziçi University (2011) [arXiv:1102.0378].
Yakaryılmaz, A. and Say, A.C.C., Efficient probability amplification in two-way quantum finite automata. Theoret. Comput. Sci. 410 (2009) 1932–1941. Google Scholar
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. CrossRef
Yakaryılmaz, A. and Say, A.C.C., Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10 (2010) 747–770. Google Scholar
Yakaryılmaz, A. and Say, A.C.C., Succinctness of two-way probabilistic and quantum finite automata. Discrete Math. Theoret. Comput. Sci. 12 (2010) 19–40. Google Scholar
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.
Yakaryılmaz, A. and Say, A.C.C., Unbounded-error quantum computation with small space bounds. Inf. Comput. 279 (2011) 873–892. Google Scholar
A. Yakaryılmaz and A.C.C. Say, Proving the power of postselection. Fundam. Inform. (2012). [arXiv:1111.3125].
Yakaryılmaz, A., Freivalds, R., Say, A.C.C. and Agadzanyan, R., Quantum computation with write-only memory. Natural Comput. 11 (2012) 81–94. Google Scholar
Yamasaki, T., Kobayashi, H., Tokunaga, Y. and Imai, H., One-way probabilistic reversible and quantum one-counter automata. Theoret. Comput. Sci. 289 (2002) 963–976. Google Scholar
Yamasaki, T., Kobayashi, H. and Imai, H., Quantum versus deterministic counter automata. Theoret. Comput. Sci. 334 (2005) 275–297. Google Scholar