Abstract
We obtain several lower bounds on the language recognition power of Nayak’s generalized quantum finite automata (GQFA) [12]. Techniques for proving lower bounds on Kondacs and Watrous’ one-way quantum finite automata (KWQFA) were introduced by Ambainis and Freivalds [2], and were expanded in a series of papers. We show that many of these techniques can be adapted to prove lower bounds for GQFAs. Our results imply that the class of languages recognized by GQFAs is not closed under union. Furthermore, we show that there are languages which can be recognized by GQFAs with probability p > 1/2, but not with p > 2/3.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter 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. Theory of Computing Systems 38, 165–188 (2006)
Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: 39th Annual Symposium on Foundations of Computer Science, pp. 332–341 (1998)
Ambainis, A., Ķikusts, A.: Exact results for accepting probabilities of quantum automata. Theoretical Computer Science 295(1–3), 3–25 (2003)
Ambainis, A., Ķikusts, 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)
Bennett, C.H.: Logical reversibility of computation. IBM Journal of Research and development 6, 525–532 (1973)
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)
Brodsky, A., Pippenger, N.: Characterizations of 1-way quantum finite automata. SIAM Journal on Computing 31(5), 1456–1478 (2002)
Ciamarra, M.P.: Quantum reversibility and a new model of quantum automaton. Fundamentals of Computation Theory 13, 376–379 (2001)
Golovkins, M., Pin, J.-É.: Varieties generated by certain models of reversible finite automata. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 83–93. Springer, Heidelberg (2006)
Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: 38th Annual Symposium on Foundations of Computer Science, pp. 66–75. IEEE Computer Society Press, Los Alamitos (1997)
Moore, C., Crutchfield, J.: Quantum automata and quantum grammars. Theoretical Computer Science 237(1-2), 275–306 (2000)
Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: 40th Annual Symposium on Foundations of Computer Science, pp. 369–377 (1999)
Nayak, A., Salzman, J.: On communication over an entanglement-assisted quantum channel. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on the Theory of Computing, pp. 698–704 (2002)
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Pin, J.-É.: k BG=PG, a success story. In: Fountain, J. (ed.) NATO Advanced Study Institute Semigroups, Formal Languages, and Groups, pp. 33–47. Kluwer Academic Publishers, Dordrecht (1995)
Rabin, M.: Probabilistic automata. Information and Control 6(3), 230–245 (1963)
Yao, A.C.-C.: Quantum circuit complexity. In: Proceedings of the 36th annual Symposium on Foundations of Computer Science, pp. 352–361 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mercer, M. (2008). Lower Bounds for Generalized Quantum Finite Automata. In: Martín-Vide, C., Otto, F., Fernau, H. (eds) Language and Automata Theory and Applications. LATA 2008. Lecture Notes in Computer Science, vol 5196. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88282-4_34
Download citation
DOI: https://doi.org/10.1007/978-3-540-88282-4_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88281-7
Online ISBN: 978-3-540-88282-4
eBook Packages: Computer ScienceComputer Science (R0)