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

RAIRO - Theoretical Informatics and Applications (2012)

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

## Access Full Article

top## Abstract

top## How to cite

topYakaryı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- 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.
- A. Ambainis and J. Watrous, Two-way finite automata with quantum and classical states. Theoret. Comput. Sci.287 (2002) 299–311. Zbl1061.68047
- A. Ambainis and A. Yakaryılmaz, Superiority of exact quantum automata for promise problems. Inf. Process. Lett.112 (2012) 289–291. Zbl1237.68082
- A. Ambainis and A. Yakaryılmaz, Automata : from Mathematics to Applications, in Automata and quantum computing, in preparation. Zbl1237.68082
- A. Ambainis, A. Nayak, A. Ta-Shma and U. Vazirani, Dense quantum coding and quantum finite automata. J. ACM49 (2002) 496–511. Zbl1326.68133
- E. Bernstein and U. Vazirani, Quantum complexity theory. SIAM J. Comput.26 (1997) 1411–1473. Zbl0895.68042
- A. Bertoni and M. Carpentieri, Analogies and differences between quantum and stochastic automata. Theor. Comput. Sci.262 (2001) 69–81. Zbl0983.68094
- A. Bertoni, C. Mereghetti and B. Palano, Small size quantum automata recognizing some regular languages. Theor. Comput. Sci.340 (2005) 394–407. Zbl1087.68047
- 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
- A. Brodsky and N. Pippenger, Characterizations of 1-way quantum finite automata. SIAM J. Comput.31 (2002) 1456–1478. Zbl1051.68062
- P.C. Fischer, A.R. Meyer and A.L. Rosenberg, Counter machines and counter languages. Math. Syst. Theory2 (1968) 265–283. Zbl0165.32002
- R. Freivalds, Language recognition using finite probabilistic multitape and multihead automata. Problemy Peredachi Informatsii15 (1979) 99–106.
- 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
- 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
- S.A. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci.7 (1978) 311–324. Zbl0389.68030
- 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
- M. Hirvensalo, Quantum automata with open time evolution. Int. J. Natural Comput. Res.1 (2010) 70–85.
- 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.
- 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
- M. Kutyłowski, Multihead one-way finite automata. Theoret. Comput. Sci.85 (1991) 135–153. Zbl0746.68051
- 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
- C. Mereghetti and B. Palano, Quantum automata for some multiperiodic languages. Theoret. Comput. Sci.387 (2007) 177–186. Zbl1148.68031
- C. Moore and J.P. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci.237 (2000) 275–306. Zbl0939.68037
- Y. Murakami, M. Nakanishi, S. Yamashita and K. Watanabe, Quantum versus classical pushdown automata in exact computation. IPSJDC1 (2005) 426–435.
- 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.
- 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.
- M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press (2000). Zbl1049.81015
- A. Paz, Introduction to Probabilistic Automata. Academic Press, New York (1971). Zbl0234.94055
- M.O. Rabin, Probabilistic automata. Inf. Control6 (1963) 230–243.
- A.L. Rosenberg, On multi-head finite automata. IBM J. Res. Devel.10 (1966) 388–394. Zbl0168.01303
- A.C.C. Say and A. Yakaryılmaz, Quantum function computation using sublogarithmic space (2010) (Poster presentation at QIP2010) [arXiv:1009.3124].
- A.C.C. Say and A. Yakaryılmaz, Computation with narrow CTCs, in Unconventional Computation. Lect. Notes Comput.6714 (2011) 201–211. Zbl1330.68080
- A.C.C. Say and A. Yakaryılmaz, Quantum counter automata. Int. J. Found. Comput. Sci. To appear. Zbl1279.68175
- P. Turakainen, Generalized automata and stochastic languages. Proc. Am. Math. Soc.21 (1969) 303–309. Zbl0184.02802
- J. Watrous, Space-bounded quantum complexity. J. Comput. Syst. Sci.59 (1999) 281–326. Zbl0947.68051
- J. Watrous, Quantum computational complexity, in Encyclopedia of Complexity andSystems 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]. Zbl1221.68092
- 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
- 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
- A. Yakaryılmaz and A.C.C. Say, Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput.10 (2010) 747–770. Zbl1236.81071
- 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
- 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.
- A. Yakaryılmaz and A.C.C. Say, Unbounded-error quantum computation with small space bounds. Inf. Comput.279 (2011) 873–892. Zbl1221.68092
- A. Yakaryılmaz and A.C.C. Say, Proving the power of postselection. Fundam. Inform. (2012). [arXiv:1111.3125]. Zbl1279.68091
- 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
- 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
- T. Yamasaki, H. Kobayashi and H. Imai, Quantum versus deterministic counter automata. Theoret. Comput. Sci.334 (2005) 275–297. Zbl1080.68060

## NotesEmbed ?

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