Abstract
We compare the descriptional power of quantum finite automata with control language (qfcs) and deterministic finite automata (dfas). By suitably adapting Rabin’s technique, we show how to convert any given qfc to an equivalent dfa, incurring in an at most exponential size increase. This enables us to state a lower bound on the size of qfcs, which is logarithmic in the size of equivalent minimal dfas. In turn, this result yields analogous size lower bounds for several models of quantum finite automata in the literature.
Partially supported by MIUR under the project “PRIN: Automi e Linguaggi Formali: Aspetti Matematici e Applicativi.”
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., Beaudry, M., Golovkins, M., Kikusts, A., Mercer, M., Thérien, D.: Algebraic results on quantum automata. Th. Comp. Sys. 39, 165–188 (2006)
Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: Proc. 39th Symp. Found. Comp. Sci., pp. 332–342 (1998)
Ambainis, A., Yakaryilmaz, A.: Superiority of exact quantum automata for promise problems. Information Processing Letters 112, 289–291 (2012)
Bertoni, A., Mereghetti, C., Palano, B.: Quantum computing: 1-way quantum automata. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 1–20. Springer, Heidelberg (2003)
Bertoni, A., Mereghetti, C., Palano, B.: Small size quantum automata recognizing some regular languages. Theoretical Computer Science 340, 394–407 (2005)
Bertoni, A., Mereghetti, C., Palano, B.: Some formal tools for analyzing quantum automata. Theoretical Computer Science 356, 14–25 (2006)
Bianchi, M.P., Palano, B.: Events and languages on unary quantum automata. Fundamenta Informaticae 104, 1–15 (2010)
Brodsky, A., Pippenger, N.: Characterizations of 1-way quantum finite automata. SIAM J. Comput. 5, 1456–1478 (2002)
Golovkins, M., Kravtsev, M.: Probabilistic reversible automata and quantum automata. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 574–583. Springer, Heidelberg (2002)
Hirvensalo, M.: Quantum automata with open time evolution. Int. J. Nat. Comp. Res. 1, 70–85 (2010)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (2001)
Hughes, R.I.G.: The Structure and Interpretation of Quantum Mechanics. Harvard University Press, Cambridge (1992)
Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proc. 38th Annual Symposium on Foundations of Computer Science, pp. 66–75 (1997)
Moore, C., Crutchfield, J.: Quantum automata and quantum grammars. Theoretical Computer Science 237, 275–306 (2000)
Mereghetti, C., Palano, B.: Quantum finite automata with control language. Theoretical Informatics and Applications 40, 315–332 (2006)
Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: Proc. 40th Symposium on Foundations of Computer Science, pp. 369–376 (1999)
Rabin, M.O.: Probabilistic automata. Information and Control 6, 230–245 (1963)
Scharnhorst, K.: Angles in complex vector spaces. Act. Ap. Math. 69, 95–103 (2001)
Shilov, G.: Linear Algebra. Prentice Hall (1971); Reprinted by Dover (1977)
Yakaryilmaz, A., Cem Say, A.C.: Unbounded-error quantum computation with small space bounds. Information & Computation 209, 873–892 (2011)
Zheng, S., Qiu, D., Li, L., 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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bianchi, M.P., Mereghetti, C., Palano, B. (2013). Size Lower Bounds for Quantum Automata. In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds) Unconventional Computation and Natural Computation. UCNC 2013. Lecture Notes in Computer Science, vol 7956. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39074-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-39074-6_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39073-9
Online ISBN: 978-3-642-39074-6
eBook Packages: Computer ScienceComputer Science (R0)