Abstract
There are several nonequivalent definitions of quantum finite automata. Nearly all of them recognize only regular languages but not all regular languages. On the other hand, for all these definitions there is a result showing that there is a language l such that the size of the quantum automaton recognizing L is essentially smaller than the size of the minimal deterministic automaton recognizing L.
For most of the definitions of quantum finite automata the problem to describe the class of the languages recognizable by the quantum automata is still open. The partial results are surveyed in this paper. Moreover, for the most popular definition of the QFA, the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.
The end of the paper is devoted to unpublished results of the description of the class of the recognizable languages in terms of the second order predicate logics. This research is influenced by the results of Büchi [1,2], Elgot [3], Trakhtenbrot [4] (description of regular languages in terms of MSO), R.Fagin [5,6] (description of NP in terms of ESO), von Neumann [7] (quantum logics), Barenco, Bennett et al. [8](universal quantum gates).
Research supported by Grant No.05.1528 from the Latvian Council of Science and European Commission, contract IST-1999-11234.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Büchi, J.R.: Weak second-order arithmetic and finite automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 6, 66–92 (1960)
Büchi, J.R.: On a decision method in restricted second order arithmetic. In: Nagel, E. (ed.) Proceeding of the International Congress on Logic, Methodology and Philosophy of Science, pp. 1–11. Stanford University Press, Stanford (1960)
Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98, 21–51 (1961)
Trakhtenbrot, B.A.: Finite automata and the logic of one-place predicates. Siberian Mathematical Journal 3, 103–131 (1962) (in Russian); English translation: American Mathematical Society Translations 59, 23–55 (1966)
Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol. 7, pp. 43–73 (1974)
Fagin, R.: Monadic generalized spectra. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 21, 89–96 (1975)
von Neumann, J.: Mathematical Foundations of Quantum Mechanics. Princeton University Press, Princeton (1932)
Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N.H., Shor, P.W., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Physical Review A 52, 3457–3467 (1995)
Ambainis, A., Freivalds, R.: 1-way quantum finite automata: Strengths, weaknesses and generalizations. In: Proc. FOCS 1998, pp. 332–341 (1998), also quant-ph/98020622
Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theor. Comput. Sci. 237, 275–306 (2000); also quant-ph/9707031
Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proc. FOCS 1997, pp. 66–75 (1997)
Brodsky, A., Pippenger, N.: Characterizations of 1-way quantum finite automata. SIAM J. Comput. 31, 1456–1478 (2002); also quant-ph/9903014
Meyer, A.R., Thompson, C.: Remarks on algebraic decomposition of automata. Mathematical Systems Theory 3, 110–118 (1969)
Ambainis, A., Bonner, R.F., Freivalds, R., Kikusts, A.: Probabilities to accept languages by quantum finite automata. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol. 1627, pp. 174–183. Springer, Heidelberg (1999); also quant-ph/9904066
Kikusts, A.: A small 1-way quantum finite automation (1998); quant-ph/9810065
Ambainis, A., Nayak, A., Ta-Shma, A., Vazirani, U.: Dense quantum coding and quantum finite automata. J. ACM 49, 496–511 (2002); also quant-ph/9804043
Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: Proc. FOCS 1999, pp. 369–377 (1999); also quant-ph/9904093
Gruska, J.: Descriptional complexity issues in quantum computing. Journal of Automata, Languages and Combinatorics 5, 191–218 (2000)
Ambainis, A., Kikusts, A., Valdats, M.: On the class of languages recognizable by 1-way quantum finite automata. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 75–86. Springer, Heidelberg (2001)
Valdats, M.: The class of languages recognizable by 1-way quantum finite automata is not closed under union. In: Proc. Int. Workshop Quantum Computation and Learning, Sundbyholm Slott, Sweden, pp. 52–64 (2000)
Immerman, N.: Descriptive and computational complexity. In: Csirik, J.A., Demetrovics, J., Gecseg, F. (eds.) FCT 1989. LNCS, vol. 380, pp. 244–245. Springer, Heidelberg (1989)
Immerman, N.: Descriptive complexity: A logician’s approach to computation. Notices of the AMS 42, 1127–1133 (1995)
Pnueli, A.: The temporal logic of programs. In: Proc. FOCS 1977, pp. 1–14 (1977)
Engelfriet, J., Hoogeboom, H.J.: MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic 2, 216–254 (2001)
Stockmeyer, L.: The polynomial-time hierarchy. Theoretical Computer Science 3, 1–22 (1977)
Immerman, N.: Relational queries computable in polynomial time (extended abstract). In: Proc. STOC 1982, pp. 147–152. ACM Press, New York (1982)
Vardi, M.Y.: Complexity of relational query languages. In: Proc. STOC 1982, pp. 137–146 (1982)
Immerman, N.: Upper and lower bounds for first order expressibility. J. Comput. Syst. Sci. 25, 76–98 (1982)
Zadeh, L.A.: Fuzzy sets. Information and Control 8, 338–353 (1965)
Vincenzo, D.P.D.: Two-bit gates are universal for quantum computation. Physical Review A 51, 1015–1022 (1995)
Dzelme, I.: Quantum finite automata and logics. Master’s thesis, University of Latvia, Advisor: Freivalds, R (2005)
Mostowski, A.: On a generalization of quantifiers. Fundamenta Mathematicae 44, 12–36 (1957)
Burtschik, H.J., Vollmer, H.: Lindström quantifiers and leaf language definability. In: Electronic Colloquium on Computational Complexity, TR96–005 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Freivalds, R. (2006). Languages Recognizable by Quantum Finite Automata. In: Farré, J., Litovsky, I., Schmitz, S. (eds) Implementation and Application of Automata. CIAA 2005. Lecture Notes in Computer Science, vol 3845. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11605157_1
Download citation
DOI: https://doi.org/10.1007/11605157_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31023-5
Online ISBN: 978-3-540-33097-4
eBook Packages: Computer ScienceComputer Science (R0)