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

Abuzer Yakaryılmaz

RAIRO - Theoretical Informatics and Applications (2012)

  • Volume: 46, Issue: 4, page 615-641
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Yakaryılmaz, Abuzer. "Superiority of one-way and realtime quantum machines∗∗∗." RAIRO - Theoretical Informatics and Applications 46.4 (2012): 615-641. <http://eudml.org/doc/277833>.

@article{Yakaryılmaz2012,
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.},
author = {Yakaryılmaz, Abuzer},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Quantum computation; quantum automata; blind counter automata; multihead finite automata; nondeterminism; bounded error; quantum computation},
language = {eng},
month = {11},
number = {4},
pages = {615-641},
publisher = {EDP Sciences},
title = {Superiority of one-way and realtime quantum machines∗∗∗},
url = {http://eudml.org/doc/277833},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Yakaryılmaz, Abuzer
TI - Superiority of one-way and realtime quantum machines∗∗∗
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/11//
PB - EDP Sciences
VL - 46
IS - 4
SP - 615
EP - 641
AB - 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.
LA - eng
KW - Quantum computation; quantum automata; blind counter automata; multihead finite automata; nondeterminism; bounded error; quantum computation
UR - http://eudml.org/doc/277833
ER -

References

top
  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.  Zbl1061.68047
  3. A. Ambainis and A. Yakaryılmaz, Superiority of exact quantum automata for promise problems. Inf. Process. Lett.112 (2012) 289–291.  Zbl1237.68082
  4. A. Ambainis and A. Yakaryılmaz, Automata : from Mathematics to Applications, in Automata and quantum computing, in preparation.  Zbl1237.68082
  5. A. Ambainis, A. Nayak, A. Ta-Shma and U. Vazirani, Dense quantum coding and quantum finite automata. J. ACM49 (2002) 496–511.  Zbl1326.68133
  6. E. Bernstein and U. Vazirani, Quantum complexity theory. SIAM J. Comput.26 (1997) 1411–1473.  Zbl0895.68042
  7. A. Bertoni and M. Carpentieri, Analogies and differences between quantum and stochastic automata. Theor. Comput. Sci.262 (2001) 69–81.  Zbl0983.68094
  8. A. Bertoni, C. Mereghetti and B. Palano, Small size quantum automata recognizing some regular languages. Theor. Comput. Sci.340 (2005) 394–407.  Zbl1087.68047
  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.  Zbl1052.68038
  10. A. Brodsky and N. Pippenger, Characterizations of 1-way quantum finite automata. SIAM J. Comput.31 (2002) 1456–1478.  Zbl1051.68062
  11. P.C. Fischer, A.R. Meyer and A.L. Rosenberg, Counter machines and counter languages. Math. Syst. Theory2 (1968) 265–283.  Zbl0165.32002
  12. R. Freivalds, Language recognition using finite probabilistic multitape and multihead automata. Problemy Peredachi Informatsii15 (1979) 99–106.  
  13. R. Freivalds, A. Yakaryılmaz and A.C.C. Say, A new family of nonstochastic languages. Inf. Process. Lett.110 (2010) 410–413.  Zbl1229.68048
  14. M. Golovkins, Quantum pushdown automata, in Proc. of SOFSEM’00 : Theory and Practice of Informatics. Lett. Notes Comput. Sci.1963 (2000) 336–346.  Zbl1043.68556
  15. S.A. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci.7 (1978) 311–324.  Zbl0389.68030
  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 .  URIhttp://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.  Zbl0970.81008
  20. M. Kutyłowski, Multihead one-way finite automata. Theoret. Comput. Sci.85 (1991) 135–153.  Zbl0746.68051
  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.  Zbl1013.68088
  22. C. Mereghetti and B. Palano, Quantum automata for some multiperiodic languages. Theoret. Comput. Sci.387 (2007) 177–186.  Zbl1148.68031
  23. C. Moore and J.P. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci.237 (2000) 275–306.  Zbl0939.68037
  24. Y. Murakami, M. Nakanishi, S. Yamashita and K. Watanabe, Quantum versus classical pushdown automata in exact computation. IPSJDC1 (2005) 426–435.  
  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).  Zbl1049.81015
  28. A. Paz, Introduction to Probabilistic Automata. Academic Press, New York (1971).  Zbl0234.94055
  29. M.O. Rabin, Probabilistic automata. Inf. Control6 (1963) 230–243.  
  30. A.L. Rosenberg, On multi-head finite automata. IBM J. Res. Devel.10 (1966) 388–394.  Zbl0168.01303
  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.  Zbl1330.68080
  33. A.C.C. Say and A. Yakaryılmaz, Quantum counter automata. Int. J. Found. Comput. Sci. To appear.  Zbl1279.68175
  34. P. Turakainen, Generalized automata and stochastic languages. Proc. Am. Math. Soc.21 (1969) 303–309.  Zbl0184.02802
  35. J. Watrous, Space-bounded quantum complexity. J. Comput. Syst. Sci.59 (1999) 281–326.  Zbl0947.68051
  36. J. Watrous, Quantum computational complexity, in Encyclopedia of Complexity andSystems Science, edited by R.A. Meyers. Springer (2009) 7174–7201.  
  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].  Zbl1221.68092
  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.  Zbl1163.68026
  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.  Zbl1248.68315
  42. A. Yakaryılmaz and A.C.C. Say, Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput.10 (2010) 747–770.  Zbl1236.81071
  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.  Zbl1286.68297
  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.  Zbl1221.68092
  46. A. Yakaryılmaz and A.C.C. Say, Proving the power of postselection. Fundam. Inform. (2012). [arXiv:1111.3125].  Zbl1279.68091
  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.  Zbl1251.68117
  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.  Zbl1061.68099
  49. T. Yamasaki, H. Kobayashi and H. Imai, Quantum versus deterministic counter automata. Theoret. Comput. Sci.334 (2005) 275–297.  Zbl1080.68060

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.