# On the state complexity of semi-quantum finite automata

Shenggen Zheng; Jozef Gruska; Daowen Qiu

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

- Volume: 48, Issue: 2, page 187-207
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topZheng, Shenggen, Gruska, Jozef, and Qiu, Daowen. "On the state complexity of semi-quantum finite automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.2 (2014): 187-207. <http://eudml.org/doc/273015>.

@article{Zheng2014,

abstract = {Some of the most interesting and important results concerning quantum finite automata are those showing that they can recognize certain languages with (much) less resources than corresponding classical finite automata. This paper shows three results of such a type that are stronger in some sense than other ones because (a) they deal with models of quantum finite automata with very little quantumness (so-called semi-quantum one- and two-way finite automata); (b) differences, even comparing with probabilistic classical automata, are bigger than expected; (c) a trade-off between the number of classical and quantum basis states needed is demonstrated in one case and (d) languages (or the promise problem) used to show main results are very simple and often explored ones in automata theory or in communication complexity, with seemingly little structure that could be utilized.},

author = {Zheng, Shenggen, Gruska, Jozef, Qiu, Daowen},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {quantum computing; quantum finite automata; semi-quantum finite automata; state complexity},

language = {eng},

number = {2},

pages = {187-207},

publisher = {EDP-Sciences},

title = {On the state complexity of semi-quantum finite automata},

url = {http://eudml.org/doc/273015},

volume = {48},

year = {2014},

}

TY - JOUR

AU - Zheng, Shenggen

AU - Gruska, Jozef

AU - Qiu, Daowen

TI - On the state complexity of semi-quantum finite automata

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2014

PB - EDP-Sciences

VL - 48

IS - 2

SP - 187

EP - 207

AB - Some of the most interesting and important results concerning quantum finite automata are those showing that they can recognize certain languages with (much) less resources than corresponding classical finite automata. This paper shows three results of such a type that are stronger in some sense than other ones because (a) they deal with models of quantum finite automata with very little quantumness (so-called semi-quantum one- and two-way finite automata); (b) differences, even comparing with probabilistic classical automata, are bigger than expected; (c) a trade-off between the number of classical and quantum basis states needed is demonstrated in one case and (d) languages (or the promise problem) used to show main results are very simple and often explored ones in automata theory or in communication complexity, with seemingly little structure that could be utilized.

LA - eng

KW - quantum computing; quantum finite automata; semi-quantum finite automata; state complexity

UR - http://eudml.org/doc/273015

ER -

## References

top- [1] A. Ambainis, A. Nayak, A. Ta-Shma and U. Vazirani, Dense quantum coding and quantum automata. J. ACM49 (2002) 496–511. Zbl1326.68133MR2146458
- [2] A. Ambainis, The complexity of probabilistic versus deterministic finite automata, Proc. of the International Symposium on Algorithms and Computation (ISAAC96). Lect. Notes Comput. Sci. 1178 (1996) 233–239. Zbl1036.68510MR1615194
- [3] A. Ambainis and J. Watrous, Two-way finite automata with quantum and classical states. Theoret. Comput. Sci.287 (2002) 299–311. Zbl1061.68047MR1944456
- [4] A. Ambainis and R. Freivalds, One-way quantum finite automata: strengths, weaknesses and generalizations, in: Proc. of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Palo Alfo, California, USA (1998) 332–341.
- [5] A. Ambainis and N. Nahimovs, Improved constructions of quantum automata. Theoret. Comput. Sci.410 (2009) 1916–1922. Zbl1163.68020MR2517650
- [6] A. Ambainis and A. Yakaryilmaz, Superiority of exact quantum automata for promise problems. Inform. Process. Lett.112 (2012) 289–291. Zbl1237.68082MR2879167
- [7] A. Bertoni, C. Mereghetti and B. Palano, Small size quantum automata recognizing some regular languages. Theoret. Comput. Sci.340 (2005) 394–407. Zbl1087.68047MR2150762
- [8] A. Bertoni, C. Mereghetti and b. Palano. Some formal tools for analyzing quantum automata. Theoret. Comput. Sci. 356 (2006) 14–25. Zbl1160.68375MR2217824
- [9] J.C. Birget, State-complexity of finite-state devices, state compressibility and incompressibility. Math. Systems Theory26 (1993) 237–269. Zbl0779.68061MR1209997
- [10] A. Brodsky and N. Pippenger, Characterizations of 1-way quantum finite automata. SIAM J. Comput.31 (2002) 1456–1478. Zbl1051.68062MR1936654
- [11] H. Buhrman, R. Cleve and A. Wigderson, Quantum vs. classical communication and computation. Proc. of 30th Annual ACM Symposium Theory Computing (1998) 63–68. Zbl1028.68056MR1731563
- [12] H. Buhrman, R. Cleve, S. Massar and R. de Wolf, Nonlocality and Communication Complexity. Rev. Mod. Phys.82 (2010) 665–698
- [13] M. Chrobak, Finite Automata and Unary Languages. Theoret. Comput. Sci.47 (1986) 149–158. Zbl0638.68096MR881208
- [14] C. Dwork and L. Stockmeyer, A time-complexity gap for two-way probabilistic finite state automata. SIAM J. Comput.19 (1990) 1011–1023. Zbl0711.68075MR1069095
- [15] R. Freivalds, On the growth of the number of states in result of determinization of probabilistic finite automata. Automatic Control Comput. Sci.3 (1982) 39–42.
- [16] R. Freivalds, Non-constructive methods for finite probabilistic automata. Int. J. Found. Comput. Sci.19 (2008) 565–580. Zbl1155.68036MR2417956
- [17] R. Freivalds, M. Ozols and L. Mancinska, Improved constructions of mixed state quantum automata. Theoret. Comput. Sci.410 (2009) 1923–1931. Zbl1163.68022MR2517651
- [18] W. Feller, An Introduction to Probability Theory and its Applications, vol. I. Wiley, New York, 1967. Zbl0039.13201
- [19] J. Gruska, Quantum Computing. McGraw-Hill, London (1999). MR1978991
- [20] J. Gruska, Descriptional complexity issues in quantum computing. J. Automata Languages Combinatorics5 (2000) 191–218. Zbl0965.68021MR1778471
- [21] J. Gruska, D.W. Qiu, and S.G. Zheng, Communication complexity of promise problems and their applications to finite automata, arXiv:1309.7739 (2013).
- [22] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addision-Wesley, New York, 1979. Zbl0980.68066MR645539
- [23] G.A. Kiraz, Compressed Storage of Sparse Finite-State Transducers, Proc. of CIAA, vol. 2214 of Lect. Notes Comput. Sci. (2001) 109–121. Zbl1050.68589
- [24] H. Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols. Proc. of the 32th STOC (2000) 644–651. Zbl1296.68058MR2115303
- [25] E. Kushilevitz, Communication Complexity. Adv. Comput.44 (1997) 331–360. Zbl0869.68048
- [26] A. Kondacs and J. Watrous, On the power of quantum finite state automata, in Proc. of 38th IEEE Annal. Sympos. Found. of Comput. Sci. (1997) 66–75.
- [27] F. Le Gall, Exponential separation of quantum and classical online space complexity, in Proc. of SPAA’06 (2006) 67–73. Zbl1183.68292
- [28] G. Liu, C. Martin-Vide, A. Salomaa and S. Yu, State complexity of basic operations combined with reversal, Inf. Comput.206 (2008) 1178–186. Zbl1154.68073MR2440660
- [29] C. Mereghetti and G. Pighizzini, Two-way automata simulations and unary languages. J. Automata, Languages and Combinatorics 5 (2000) 287–300. Zbl0965.68043MR1778478
- [30] C. Mereghetti, B. Palano and G. Pighizzini, Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. RAIRO: ITA 35 (2001) 477–490. Zbl1010.68068MR1908867
- [31] C. Mereghetti and B. Palano, On the size of one-way quantum finite automata with periodic behaviors. RAIRO: ITA 36 (2002) 277–291. Zbl1013.68088MR1958244
- [32] M. Milani and G. Pighizzini, Tight bounds on the simulation of unary probabilistic automata by deterministic automata, J. Automata, Languages and Combinatorics 6 (2001) 481–492. Zbl1050.68095MR1897056
- [33] P. Mateusa, D.W. Qiu and L.Z. Li, On the complexity of minimizing probabilistic and quantum automata. Inform. Comput.218 (2012) 36–53. Zbl1279.68164MR2967324
- [34] C. Moore and J. P. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci.237 (2000) 275–306. Zbl0939.68037MR1756213
- [35] A. Paz, Introduction to Probabilistic Automata. Academic Press, New York (1971). Zbl0234.94055MR289222
- [36] D. W. Qiu, Some Observations on Two-Way Finite Automata with Quantum and Classical States, ICIC 2008. In vol. 5226 of Lect. Notes Comput. Sci. (2008) 1–8. Zbl1330.68183
- [37] M. O. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Research Devel.3 (1959) 115–125. Zbl0158.25404MR103795
- [38] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2000. Zbl1288.81001MR1796805
- [39] D. W. Qiu, L.Z. Li, P. Mateus and J. Gruska, Quantum finite automata, CRC Handbook of Finite State Based Models and Applications. Edited by J.C. Wang. CRC Press (2012) 113–144. Zbl1304.68121MR3014620
- [40] A. Salomaa, On the reducibility of events represented in automata. In Annales Academiae Scientiarum Fennicae. Volume Series A of I. Math. (1964) 353. Zbl0168.26003MR168462
- [41] S. Yu, Q. Zhuang and K. Salomaa. The state complexity of some basic operations on regular languages. Theoret. Comput. Sci.125 (1994) 315–328. Zbl0795.68112MR1264137
- [42] S. Yu, State Complexity: Recent Results and Open Problems. Fundamenta Informaticae64 (2005) 471–480. Zbl1102.68076MR2347575
- [43] A. Yakaryilmaz and A.C. Cem Say, Unbounded-error quantum computation with small space bounds, Inform. Comput.209 (2011) 873–892. Zbl1221.68092MR2817180
- [44] A. Yakaryilmaz and A.C. Cem Say, Succinctness of two-way probabilistic and quantum finite automata. Discrete Math. Theoret. Comput. Sci.12 (2010) 19–40. Zbl1286.68297MR2760333
- [45] S.G. Zheng, D.W. Qiu, L.Z. Li and J. Gruska, One-way finite automata with quantum and classical states, vol 7300 of Lect. Notes Comput. Sci. Edited by H. Bordihn, M. Kutrib, and B. Truthe (2012) 273–290. Zbl1330.68183
- [46] S.G. Zheng, D.W. Qiu, J. Gruska, L.Z. Li and P. Mateus, State succinctness of two-way finite automata with quantum and classical states, Theoret. Comput. Sci.499 (2013) 98–112. Zbl1296.68098MR3084151
- [47] S.G. Zheng, D.W. Qiu and L.Z. Li, Some languages recognized by two-way finite automata with quantum and classical states. Int. J. Foundation Comput. Sci.23 (2012) 1117–1129. Zbl1259.68117MR2983371
- [48] S.G. Zheng, J. Gruska and D.W. Qiu. Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata. arXiv:1304.3876 (2013). Zbl1309.68074

## NotesEmbed ?

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