Abstract
Multi-letter quantum finite automata (QFAs) can be thought of quantum variants of the one-way multi-head finite automata (Hromkovič, Acta Informatica 19:377–384, 1983). It has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages, for example (a + b)*b, that are not acceptable by QFAs of Moore and Crutchfield (Theor Comput Sci 237:275–306, 2000) as well as Kondacs and Watrous (66–75, 1997; Observe that 1-letter QFAs are exactly measure-once QFAs (MO-1QFAs) of Moore and Crutchfield (Theor Comput Sci 237:275–306, 2000)). In this paper, we study the decidability of the equivalence and minimization problems of multi-letter QFAs. Three new results presented in this paper are the following ones: (1) Given a k 1-letter QFA \({{\mathcal A}_1}\) and a k 2-letter QFA \({{\mathcal A}_2}\) over the same input alphabet Σ, they are equivalent if and only if they are (n 2 m k-1−m k-1 + k)-equivalent, where m = |Σ| is the cardinality of Σ, k = max(k 1,k 2), and n = n 1 + n 2, with n 1 and n 2 being numbers of states of \({{\mathcal A}_{1}}\) and \({{\mathcal A}_{2}}\) , respectively. When k = 1, this result implies the decidability of equivalence of measure-once QFAs (Moore and Crutchfield in Theor Comput Sci 237:275–306, 2000). (It is worth mentioning that our technical method is essentially different from the previous ones used in the literature.) (2) A polynomial-time O(m 2k-1 n 8 + km k n 6) algorithm is designed to determine the equivalence of any two multi-letter QFAs (see Theorems 2 and 3; Observe that if a brute force algorithm to determine equivalence would be used, as suggested by the decidability outcome of the point (1), the worst case time complexity would be exponential). Observe also that time complexity is expressed here in terms of the number of states of the multi-letter QFAs and k can be seen as a constant. (3) It is shown that the states minimization problem of multi-letter QFAs is solvable in EXPSPACE. This implies also that the state minimization problem of MO-1QFAs (see Moore and Crutchfield in Theor Comput Sci 237:275–306, 2000, page 304, Problem 5), an open problem stated in that paper, is also solvable in EXPSPACE.
Similar content being viewed by others
References
Amano, M., Iwama, K.: Undecidability on quantum finite automata. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 368–375. Atlanta, Georgia, USA (1999)
Ambainis, A., Freivalds, R.: One-way quantum finite automata: strengths, weaknesses and generalizations. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 332–341. IEEE Computer Society Press, Palo Alfo, California, USA. Also quant-ph/9802062 (1998)
Basu S., Pollack R., Roy M.-F.: Algorithms in Real Algebraic Geometry, 2nd Edn. Springer, New York (2006)
Belovs, A., Rosmanis, A., Smotrovs, J.: Multi-letter reversible and quantum finite automata. In: Proceedings of the 13th International Conference on Developments in Language Theory (DLT’2007). Lecture Notes in Computer Science, vol. 4588, pp. 60–71. Springer, Berlin (2007)
Bertoni, A., Mereghetti, C., Palano, B.: Quantum computing: 1-way quantum automata. In: Proceedings of the 9th International Conference on Developments in Language Theory (DLT’2003). Lecture Notes in Computer Science, vol. 2710, pp. 1–20. Springer, Berlin (2003)
Brodsky, A., Pippenger, N.: Characterizations of 1-way quantum finite automata. SIAM J. Comput. 31, 1456–1478 (2002)
Canny, J.: Some algebraic and geometric computations in PSPACE. In: STOC ’88: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. ACM, pp. 460–469. New York, USA (1988)
Eilenberg S.: Automata, Languages, and Machines, vol. A. Academic Press, New York (1974)
Faddeev D.K., Faddeeva V.N.: Computational Methods of Linear Algebra. Freeman, San Francisco (1963)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212–219. Philadelphia, Pennsylvania, USA (1996)
Gruska J.: Quantum Computing. McGraw-Hill, London (1999)
Hirvensalo, M.: Improved undecidability results on the emptiness problem of probabilistic and quantum cut-point languages. In: SOFSEM’2007. Lecture Notes in Computer Science, vol. 4362, pp. 309–319. Springer, Berlin (2007)
Hromkovič J.: One-way multihead deterministic finite automata. Acta Inf. 19, 377–384 (1983)
Hopcroft J.E., Ullman J.D.: Introduction to Automata Theory, Languages, and Computation. Addision-Wesley, New York (1979)
Ibarra O.H., Kim C.E.: On 3-head versus 2-head finite automata. Acta Inf. 4, 193–200 (1975)
Jeandel E.: Topological automata. Theory Comput. Syst. 40, 397–407 (2007)
Kondacs, A., Watrous, J.: On the power of finite state automata. In: Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer Science, pp. 66–75. Miami Beach, Florida, USA (1997)
Li L.Z., Qiu D.W.: Determination of equivalence between quantum sequential machines. Theor. Comput. Sci. 358, 65–74 (2006)
Li L.Z., Qiu D.W.: Determining the equivalence for one-way quantum finite automata. Theor. Comput. Sci. 403, 42–51 (2008)
Li L.Z., Qiu D.W.: A note on quantum sequential machines. Theor. Comput. Sci. 410, 2529–2535 (2009)
Mateus, P., Qiu, D.W., Li, L.Z.: On the complexity of minimizing probabilistic and quantum automata. Submitted for publication
Moore C., Crutchfield J.P.: Quantum automata and quantum grammars. Theor. Comput. Sci 237, 275–306 (2000)
Paz A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)
Qiu D.W.: Characterization of sequential quantum machines. Int. J. Theor. Phys. 41, 811–822 (2002)
Qiu D.W., Li L.Z.: An overview of quantum computation models: quantum automata. Frontiers Comput. Sci. China 2(2), 193–207 (2008)
Qiu, D.W., Yu, S.: Hierarchy and equivalence of multi-letter quantum finite automata. Theor. Comput. Sci. 410, 3006–3017. Also arXiv: 0812.0852, 2008 (2009)
Rabin M.O.: Probabilistic automata. Inf. Control 6(3), 230–245 (1963)
Renegar, J.: A faster PSPACE algorithm for deciding the existential theory of the reals. In: Proceedings of 29th IEEE Annual Symposium on Foundations of Computer Science, pp. 291–295. (1988)
Roman S.: Lattices and Ordered Sets. Springer, New York (2008)
Rozenberg, G., Salomaa, A. (eds): Handbook of Formal Languages, vol. 1. Springer, Berlin (1997)
Shor P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
Tarski A.: A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley, CA (1951)
Tzeng W.G.: A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput. 21(2), 216–227 (1992)
Yu S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds) Handbook of Formal Languages, pp. 41–110. Springer, Berlin (1998)
Yakaryilmaz, A., Cem Say, A.C.: Languages recognized with unbounded error by quantum finite automata. In: Proceedings of the 4th Computer Science Symposium in Russia. Lecture Notes in Comput. Sci. vol. 5675, pp. 356–367. Springer, Berlin (2009)
Yakaryilmaz A., Cem Say A.C.: Unbounded-error quantum computation with small space bounds. Inf. Comput. 209, 873–892 (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported in part by the National Natural Science Foundation (Nos. 60873055, 61073054), the Natural Science Foundation of Guangdong Province of China (No. 10251027501000004), the Fundamental Research Funds for the Central Universities (Nos. 10lgzd12,11lgpy36), the Research Foundation for the Doctoral Program of Higher School of Ministry of Education (Nos. 20100171110042, 20100171120051) of China, the China Postdoctoral Science Foundation project (Nos. 20090460808, 201003375), the grant MSM0021622419 of Czech Republic, and the project of SQIG at IT, funded by FCT and EU FEDER projects projects QSec PTDC/EIA/67661/2006, AMDSC UTAustin/MAT/0057/2008, NoE Euro-NF, and IT Project QuantTel.
Rights and permissions
About this article
Cite this article
Qiu, D., Li, L., Zou, X. et al. Multi-letter quantum finite automata: decidability of the equivalence and minimization of states. Acta Informatica 48, 271 (2011). https://doi.org/10.1007/s00236-011-0139-6
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00236-011-0139-6