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.
Work of the first and second authors was supported by the Employment of Newly Graduated Doctors of Science for Scientific Excellence project/grant (CZ.1.07./2.3.00/30.0009) of Czech Republic. Work of third author was supported by the National Natural Science Foundation of China (Nos. 61272058, 61073054).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ambainis, A., Nayak, A., Ta-Shma, A., Vazirani, U.: Dense quantum coding and quantum automata. Journal of the ACM 49(4), 496–511 (2002)
Ambainis, A., Watrous, J.: Two-way finite automata with quantum and classical states. Theoretical Computer Science 287, 299–311 (2002)
Ambainis, A., Freivalds, R.: One-way quantum finite automata: strengths, weaknesses and generalizations. In: Proceedings of the 39th FOCS, pp. 332–341 (1998)
Ambainis, A., Nahimovs, N.: Improved constructions of quantum automata. Theoretical Computer Science 410, 1916–1922 (2009)
Ambainis, A., Yakaryilmaz, A.: Superiority of exact quantum automata for promise problems. Information Processing Letters 112(7), 289–291 (2012)
Bertoni, A., Mereghetti, C., Palano, B.: Some formal tools for analyzing quantum automata. Theoretical Computer Science 356, 14–25 (2006)
Buhrman, H., Cleve, R., Massar, S., de Wolf, R.: Nonlocality and Communication Complexity. Rev. Mod. Phys. 82, 665–698 (2010)
Dwork, C., Stockmeyer, L.: A time-complexity gap for two-way probabilistic finite state automata. SIAM J. Comput. 19, 1011–1023 (1990)
Freivalds, R.: On the growth of the number of states in result of determinization of probabilistic finite automata. Automatic Control and Computer Sciences 3, 39–42 (1982)
Gruska, J.: Descriptional complexity issues in quantum computing. J. Automata, Languages Combin. 5(3), 191–218 (2000)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addision-Wesley, New York (1979)
Kiraz, G.A.: Compressed Storage of Sparse Finite-State Transducers. In: Boldt, O., Jürgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, pp. 109–121. Springer, Heidelberg (2001)
Klauck, H.: On quantum and probabilistic communication: Las Vegas and one-way protocols. In: Proceedings of the 32th STOC, pp. 644–651 (2000)
Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings of the 38th FOCS, pp. 66–75 (1997)
Kushilevitz, E.: Communication Complexity. Advances in Computers 44, 331–360 (1997)
Mereghetti, C., Pighizzini, G.: Two-way automata simulations and unary languages. J. Autom. Lang. Comb. 5, 287–300 (2000)
Mereghetti, C., Palano, B., Pighizzini, G.: Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. RAIRO-Inf. Theor. Appl. 35, 477–490 (2001)
Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theoretical Computer Science 237, 275–306 (2000)
Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)
Qiu, D.: Some Observations on Two-Way Finite Automata with Quantum and Classical States. In: Huang, D.-S., Wunsch II, D.C., Levine, D.S., Jo, K.-H. (eds.) ICIC 2008. LNCS, vol. 5226, pp. 1–8. Springer, Heidelberg (2008)
Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Research and Development 3(2), 115–125 (1959)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Salomaa, A.: On the reducibility of events represented in automata. In: Annales Academiae Scientiarum Fennicae, volume Series A of I. Mathematica 353 (1964)
Yakaryilmaz, A., Cem Say, A.C.: Succinctness of two-way probabilistic and quantum finite automata. Discrete Mathematics and Theoretical Computer Science 12(4), 19–40 (2010)
Zheng, S.G., Qiu, D.W., Li, L.Z., Gruska, J.: One-way finite automata with quantum and classical states. In: Bordihn, H., Kutrib, M., Truthe, B. (eds.) Languages Alive. LNCS, vol. 7300, pp. 273–290. Springer, Heidelberg (2012)
Zheng, S.G., Qiu, D.W., Gruska, J., Li, L.Z., Mateus, P.: State succinctness of two-way finite automata with quantum and classical states. Theoretical Computer Science 499, 98–112 (2013)
Zheng, S.G., Gruska, J., Qiu, D.W.: On the state complexity of semi-quantum finite automata. arXiv:1307.2499 (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Zheng, S., Gruska, J., Qiu, D. (2014). On the State Complexity of Semi-quantum Finite Automata. In: Dediu, AH., Martín-Vide, C., Sierra-Rodríguez, JL., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2014. Lecture Notes in Computer Science, vol 8370. Springer, Cham. https://doi.org/10.1007/978-3-319-04921-2_49
Download citation
DOI: https://doi.org/10.1007/978-3-319-04921-2_49
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04920-5
Online ISBN: 978-3-319-04921-2
eBook Packages: Computer ScienceComputer Science (R0)