×

zbMATH — the first resource for mathematics

Quantum automata and algebraic groups. (English) Zbl 1124.81004
Summary: We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest: we give an algorithm which, given a finite number of invertible matrices, computes the Zariski closure of the group generated by these matrices.

MSC:
81P68 Quantum computation
68Q45 Formal languages and automata
20G15 Linear algebraic groups over arbitrary fields
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Babai, L.; Beals, R.; Rockmore, D., Deciding finiteness for matrix groups in deterministic polynomial time, (), 117-126 · Zbl 0925.20001
[2] Basu, S.; Pollack, R.; Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM, 43, 6, 1002-1045, (1996) · Zbl 0885.68070
[3] Becker, T.; Weispfenning, V., Gröbner bases, A computational approach to commutative algebra, () · Zbl 0772.13010
[4] Bertoni, A., The solution of problems relative to probabilistic automata in the frame of the formal languages theory, (), 107-112 · Zbl 0327.94069
[5] Bertoni, A.; Carpentieri, M., Analogies and differences between quantum and stochastic automata, Theoretical computer science, 262, 69-81, (2001) · Zbl 0983.68094
[6] Bertoni, A.; Mauri, G.; Torelli, M., Some recursively unsolvable problems relating to isolated cutpoints in probabilistic automata, (), 87-94 · Zbl 0366.94064
[7] Beukers, F., Differential Galois theory, (), 413-439 · Zbl 0813.12001
[8] Blondel, V.; Canterini, V., Undecidable problems for probabilistic automata of fixed dimension, Theory of computing systems, 36, 283-286, (2003)
[9] Blondel, V., Jeandel, E., Koiran, P., Portier, N. Decidable and undecidable problems about quantum automata. LIP Research Report 2003-34. Ecole Normale Supérieure de Lyon (submitted for publication in SIAM Journal on Computing) · Zbl 1078.81012
[10] Derksen, H.; Kemper, G., Computational invariant theory, () · Zbl 1011.13003
[11] Eisenbud, D., Commutative algebra with a view toward algebraic geometry, () · Zbl 0819.13001
[12] Fortuna, E.; Gianni, P.; Trager, B.M., Derivations and radicals of polynomial ideals over fields of arbitrary characteristic, Journal of symbolic computation, 33, 609-625, (2002) · Zbl 1059.13014
[13] Ge, G., 1993. Algorithms related to multiplicative representations of algebraic numbers. Ph.D. Thesis, University of California, Berkely
[14] Ivanyos, G., Deciding finiteness for matrix semigroups over function fields over finite fields, Israel journal of mathematics, 124, 185-188, (2001) · Zbl 1018.20053
[15] Jeandel, E., 2002. Indécidabilité sur les automates quantiques. Master Thesis, Ecole Normale Supérieure de Lyon
[16] de Jong, T., An algorithm for computing the integral closure, Journal of symbolic computation, 26, 3, 273-277, (1998) · Zbl 0932.13021
[17] Kaplansky, I., Fields and rings, (1972), University of Chicago · Zbl 1001.16500
[18] Kemper, G., The calculation of radical ideals in positive characteristic, Journal of symbolic computation, 34, 3, 229-238, (2002) · Zbl 1010.13001
[19] Kondacs, A., Watrous, J., 1997. On the power of quantum finite state automata. In: Proc. 38th IEEE Symposium on Foundations of Computer Science, pp. 66-75
[20] Masser, D.W., Linear relations on algebraic groups, (), 248-262 · Zbl 0656.10031
[21] Matsumoto, R., Computing the radical of an ideal in positive characteristic, Journal of symbolic computation, 32, 3, 263-271, (2001) · Zbl 1028.13010
[22] Moore, C.; Crutchfield, J., Quantum automata and quantum grammars, Theoretical computer science, 237, 2, 257-306, (2000) · Zbl 0939.68037
[23] Onishchik, A.; Vinberg, E., Lie groups and algebraic groups, (1990), Springer Verlag · Zbl 0722.22004
[24] Paz, A., Introduction to probabilistic automata, (1971), Academic Press New York, NY · Zbl 0234.94055
[25] Rabin, M.O., Probabilistic automata, Information and control, 6, 230-245, (1963) · Zbl 0182.33602
[26] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. parts I, II, III, Journal of symbolic computation, 13, 3, 255-352, (1992) · Zbl 0798.68073
[27] Rockmore, D.N.; Tan, K.-S.; Beals, R., Deciding finiteness for matrix groups over function fields, Israel journal of mathematics, 109, 93-116, (1999) · Zbl 0932.20051
[28] Schur, I., 1911. Über Gruppen periodischer Substitutionen. Sitzungsber. Preuss. Akad. Wiss., pp. 619-627 · JFM 42.0155.01
[29] Voutier, P., An effective lower bound for the height of algebraic numbers, Acta arithmetica, 74, 1, 81-95, (1996)
[30] Vasconcelos, W.V., Computational methods in commutative algebra and algebraic geometry, () · Zbl 0188.33701
[31] Waldschmidt, M., Diophantine approximation on linear algebraic groups, (2000), Springer
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.