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

Abstract

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

How to cite

top

Zheng, 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. [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. [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. [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. [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. [5] A. Ambainis and N. Nahimovs, Improved constructions of quantum automata. Theoret. Comput. Sci.410 (2009) 1916–1922. Zbl1163.68020MR2517650
  6. [6] A. Ambainis and A. Yakaryilmaz, Superiority of exact quantum automata for promise problems. Inform. Process. Lett.112 (2012) 289–291. Zbl1237.68082MR2879167
  7. [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. [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. [9] J.C. Birget, State-complexity of finite-state devices, state compressibility and incompressibility. Math. Systems Theory26 (1993) 237–269. Zbl0779.68061MR1209997
  10. [10] A. Brodsky and N. Pippenger, Characterizations of 1-way quantum finite automata. SIAM J. Comput.31 (2002) 1456–1478. Zbl1051.68062MR1936654
  11. [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. [12] H. Buhrman, R. Cleve, S. Massar and R. de Wolf, Nonlocality and Communication Complexity. Rev. Mod. Phys.82 (2010) 665–698 
  13. [13] M. Chrobak, Finite Automata and Unary Languages. Theoret. Comput. Sci.47 (1986) 149–158. Zbl0638.68096MR881208
  14. [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. [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. [16] R. Freivalds, Non-constructive methods for finite probabilistic automata. Int. J. Found. Comput. Sci.19 (2008) 565–580. Zbl1155.68036MR2417956
  17. [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. [18] W. Feller, An Introduction to Probability Theory and its Applications, vol. I. Wiley, New York, 1967. Zbl0039.13201
  19. [19] J. Gruska, Quantum Computing. McGraw-Hill, London (1999). MR1978991
  20. [20] J. Gruska, Descriptional complexity issues in quantum computing. J. Automata Languages Combinatorics5 (2000) 191–218. Zbl0965.68021MR1778471
  21. [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. [22] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addision-Wesley, New York, 1979. Zbl0980.68066MR645539
  23. [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. [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. [25] E. Kushilevitz, Communication Complexity. Adv. Comput.44 (1997) 331–360. Zbl0869.68048
  26. [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. [27] F. Le Gall, Exponential separation of quantum and classical online space complexity, in Proc. of SPAA’06 (2006) 67–73. Zbl1183.68292
  28. [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. [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. [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. [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. [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. [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. [34] C. Moore and J. P. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci.237 (2000) 275–306. Zbl0939.68037MR1756213
  35. [35] A. Paz, Introduction to Probabilistic Automata. Academic Press, New York (1971). Zbl0234.94055MR289222
  36. [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. [37] M. O. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Research Devel.3 (1959) 115–125. Zbl0158.25404MR103795
  38. [38] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2000. Zbl1288.81001MR1796805
  39. [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. [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. [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. [42] S. Yu, State Complexity: Recent Results and Open Problems. Fundamenta Informaticae64 (2005) 471–480. Zbl1102.68076MR2347575
  43. [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. [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. [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. [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. [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. [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 ?

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.