On the state complexity of semi-quantum finite automata
Zheng, Shenggen ; Gruska, Jozef ; Qiu, Daowen
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014), p. 187-207 / Harvested from Numdam
Access to full text

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.

@article{ITA_2014__48_2_187_0,
     author = {Zheng, Shenggen and Gruska, Jozef and Qiu, Daowen},
     title = {On the state complexity of semi-quantum finite automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {48},
     year = {2014},
     pages = {187-207},
     doi = {10.1051/ita/2014003},
     mrnumber = {3302484},
     zbl = {1292.81027},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2014__48_2_187_0}
}

Zheng, Shenggen; Gruska, Jozef; Qiu, Daowen. On the state complexity of semi-quantum finite automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) pp. 187-207. doi : 10.1051/ita/2014003. http://gdmltest.u-ga.fr/item/ITA_2014__48_2_187_0/

[1] A. Ambainis, A. Nayak, A. Ta-Shma and U. Vazirani, Dense quantum coding and quantum automata. J. ACM 49 (2002) 496-511. | MR 2146458

[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. | MR 1615194 | Zbl 1036.68510

[3] A. Ambainis and J. Watrous, Two-way finite automata with quantum and classical states. Theoret. Comput. Sci. 287 (2002) 299-311. | MR 1944456 | Zbl 1061.68047

[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. | MR 2517650 | Zbl 1163.68020

[6] A. Ambainis and A. Yakaryilmaz, Superiority of exact quantum automata for promise problems. Inform. Process. Lett. 112 (2012) 289-291. | MR 2879167 | Zbl 1237.68082

[7] A. Bertoni, C. Mereghetti and B. Palano, Small size quantum automata recognizing some regular languages. Theoret. Comput. Sci. 340 (2005) 394-407. | MR 2150762 | Zbl 1087.68047

[8] A. Bertoni, C. Mereghetti and b. Palano. Some formal tools for analyzing quantum automata. Theoret. Comput. Sci. 356 (2006) 14-25. | MR 2217824 | Zbl 1160.68375

[9] J.C. Birget, State-complexity of finite-state devices, state compressibility and incompressibility. Math. Systems Theory 26 (1993) 237-269. | MR 1209997 | Zbl 0779.68061

[10] A. Brodsky and N. Pippenger, Characterizations of 1-way quantum finite automata. SIAM J. Comput. 31 (2002) 1456-1478. | MR 1936654 | Zbl 1051.68062

[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. | MR 1731563 | Zbl 1028.68056

[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. | MR 881208 | Zbl 0638.68096

[14] C. Dwork and L. Stockmeyer, A time-complexity gap for two-way probabilistic finite state automata. SIAM J. Comput. 19 (1990) 1011-1023. | MR 1069095 | Zbl 0711.68075

[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. | MR 2417956 | Zbl 1155.68036

[17] R. Freivalds, M. Ozols and L. Mancinska, Improved constructions of mixed state quantum automata. Theoret. Comput. Sci. 410 (2009) 1923-1931. | MR 2517651 | Zbl 1163.68022

[18] W. Feller, An Introduction to Probability Theory and its Applications, vol. I. Wiley, New York, 1967. | Zbl 0039.13201

[19] J. Gruska, Quantum Computing. McGraw-Hill, London (1999). | MR 1978991

[20] J. Gruska, Descriptional complexity issues in quantum computing. J. Automata Languages Combinatorics 5 (2000) 191-218. | MR 1778471 | Zbl 0965.68021

[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. | MR 645539 | Zbl 0980.68066

[23] G.A. Kiraz, Compressed Storage of Sparse Finite-State Transducers, Proc. of CIAA, vol. 2214 of Lect. Notes Comput. Sci. (2001) 109-121. | Zbl 1050.68589

[24] H. Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols. Proc. of the 32th STOC (2000) 644-651. | MR 2115303 | Zbl 1296.68058

[25] E. Kushilevitz, Communication Complexity. Adv. Comput. 44 (1997) 331-360. | Zbl 0869.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. | Zbl 1183.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. | MR 2440660 | Zbl 1154.68073

[29] C. Mereghetti and G. Pighizzini, Two-way automata simulations and unary languages. J. Automata, Languages and Combinatorics 5 (2000) 287-300. | MR 1778478 | Zbl 0965.68043

[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. | Numdam | MR 1908867 | Zbl 1010.68068

[31] C. Mereghetti and B. Palano, On the size of one-way quantum finite automata with periodic behaviors. RAIRO: ITA 36 (2002) 277-291. | Numdam | MR 1958244 | Zbl 1013.68088

[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. | MR 1897056 | Zbl 1050.68095

[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. | MR 2967324 | Zbl 1279.68164

[34] C. Moore and J. P. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. | MR 1756213 | Zbl 0939.68037

[35] A. Paz, Introduction to Probabilistic Automata. Academic Press, New York (1971). | MR 289222 | Zbl 0234.94055

[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. | Zbl pre06101071

[37] M. O. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Research Devel. 3 (1959) 115-125. | MR 103795 | Zbl 0158.25404

[38] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2000. | MR 1796805 | Zbl 1288.81001

[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. | MR 3014620 | Zbl pre06300099

[40] A. Salomaa, On the reducibility of events represented in automata. In Annales Academiae Scientiarum Fennicae. Volume Series A of I. Math. (1964) 353. | MR 168462 | Zbl 0168.26003

[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. | MR 1264137 | Zbl 0795.68112

[42] S. Yu, State Complexity: Recent Results and Open Problems. Fundamenta Informaticae 64 (2005) 471-480. | MR 2347575 | Zbl 1102.68076

[43] A. Yakaryilmaz and A.C. Cem Say, Unbounded-error quantum computation with small space bounds, Inform. Comput. 209 (2011) 873-892. | MR 2817180 | Zbl 1221.68092

[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. | MR 2760333 | Zbl 1286.68297

[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. | Zbl pre06101071

[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. | MR 3084151 | Zbl 1296.68098

[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. | MR 2983371 | Zbl 1259.68117

[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).