On the state complexity of semi-quantum finite automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 2, pp. 187-207.

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.

DOI : 10.1051/ita/2014003
Mots-clés : quantum computing, quantum finite automata, semi-quantum finite automata, state complexity 
@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},
     pages = {187--207},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {2},
     year = {2014},
     doi = {10.1051/ita/2014003},
     mrnumber = {3302484},
     zbl = {1292.81027},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2014003/}
}
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
SP  - 187
EP  - 207
VL  - 48
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2014003/
DO  - 10.1051/ita/2014003
LA  - en
ID  - ITA_2014__48_2_187_0
ER  - 
%0 Journal Article
%A Zheng, Shenggen
%A Gruska, Jozef
%A Qiu, Daowen
%T On the state complexity of semi-quantum finite automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2014
%P 187-207
%V 48
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2014003/
%R 10.1051/ita/2014003
%G en
%F 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) no. 2, pp. 187-207. doi : 10.1051/ita/2014003. http://www.numdam.org/articles/10.1051/ita/2014003/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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

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

[25] E. Kushilevitz, Communication Complexity. Adv. Comput. 44 (1997) 331-360. | Zbl

[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

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

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

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

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

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

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

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

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

Cité par Sources :