×

Small size quantum automata recognizing some regular languages. (English) Zbl 1087.68047

Summary: Given a class \(\{p_\alpha\mid\alpha\in I\}\) of stochastic events induced by \(M\)-state 1-way quantum finite automata (1qfa’s) on an alphabet \(\Sigma\), we investigate the size (number of states) of 1qfa’s that \(\delta\)-approximate a convex linear combination of \(\{p_\alpha\mid\alpha \in I\}\), and we apply the results to the synthesis of small size 1qfa’s. We obtain: An \(O((Md/\delta^3) \log^2(d/ \delta^2))\) general size bound, where \(d\) is the Vapnik dimension of \(\{p_\alpha (w)\mid w\in\Sigma^*\}\). For commutative \(n\)-periodic events \(p\) on \(\Sigma\) with \(|\Sigma|= H\), we prove an \(O((H\log n/\delta^2))\) size bound for inducing a \(\delta\)-approximation of \(\tfrac 12+\tfrac 12 p\) whenever \(\|{\mathcal F} (\widehat p)\|_1\leq n^H\), where \({\mathcal F}(\widehat p)\) is the discrete Fourier transform of (the vector \(\widehat p\) associated with) \(p\). If the characteristic function \(\chi_L\) of an \(n\)-periodic unary language \(L\) satisfies \(\|{\mathcal F}(\widehat{\chi_L}))\|_1\leq n\), then \(L\) is recognized with isolated cut-point by a 1qfa with \(O(\log n)\) states. Vice versa, if \(L\) is recognized with isolated cut-point by a 1qfa with \(O(\log n)\) state, then \(\|{\mathcal F} (\widehat{\chi_L}))\|_1=O(n\log n)\).

MSC:

68Q45 Formal languages and automata
81P68 Quantum computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Ben-David, S.; Cesa-Bianchi, N.; Haussler, D., Scale-sensitive dimensions, Uniform Convergence, and Learnability, J. ACM, 44, 615-631 (1997) · Zbl 0891.68086
[2] A. Ambainis, R. Freivalds, 1-way quantum finite automata: strengths, weaknesses and generalizations, in: Proc. 39th Symp. on Foundations of Computer Science, 1998, pp. 332-342.; A. Ambainis, R. Freivalds, 1-way quantum finite automata: strengths, weaknesses and generalizations, in: Proc. 39th Symp. on Foundations of Computer Science, 1998, pp. 332-342.
[3] Bertoni, A.; Carpentieri, M., Regular languages accepted by quantum automata, Inform. Comput., 165, 174-182 (2001) · Zbl 1003.68061
[4] A. Bertoni, C. Mereghetti, B. Palano, Quantum computing: 1-way quantum automata, in: Proc. Seventh Conf. on Developments in Language Theory, Lecture Notes in Computer Science, Vol. 2710, Springer, Berlin, 2003, pp. 1-20.; A. Bertoni, C. Mereghetti, B. Palano, Quantum computing: 1-way quantum automata, in: Proc. Seventh Conf. on Developments in Language Theory, Lecture Notes in Computer Science, Vol. 2710, Springer, Berlin, 2003, pp. 1-20. · Zbl 1037.68058
[5] Bertoni, A.; Mereghetti, C.; Palano, B., Golomb rulers and difference sets for succinct quantum automata, Internat. J. Foundations Comput. Sci., 14, 871-888 (2003) · Zbl 1075.68028
[6] Brodsky, A.; Pippenger, N., Characterizations of 1-way quantum finite automata, SIAM J. Comput., 31, 1456-1478 (2001) · Zbl 1051.68062
[7] Gruska, J., Quantum Computing (1999), McGraw-Hill: McGraw-Hill New York
[8] Gruska, J., Descriptional complexity issues in quantum computing, J. Automata, Languages Combinatorics, 5, 191-218 (2000) · Zbl 0965.68021
[9] Höffdings, W., Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 13-30 (1963) · Zbl 0127.10602
[10] C. Moore, J. Crutchfield, Quantum automata and quantum grammars, Theoretical Computer Science 237 (2000) 275-306. A preliminary version of this work appears as Technical Report in 1997.; C. Moore, J. Crutchfield, Quantum automata and quantum grammars, Theoretical Computer Science 237 (2000) 275-306. A preliminary version of this work appears as Technical Report in 1997. · Zbl 0939.68037
[11] Marcus, M.; Minc, H., Introduction to Linear Algebra (1965), Macmillan: Macmillan New York, (reprinted by Dover, 1988) · Zbl 0142.26801
[12] Marcus, M.; Minc, H., A Survey of Matrix Theory and Matrix Inequalities (1964), Prindle, Weber & Schmidt: Prindle, Weber & Schmidt Boston, MA, (reprinted by Dover, 1992) · Zbl 0126.02404
[13] Mereghetti, C.; Palano, B., On the size of one-way quantum finite automata with periodic behaviors, Theoret. Inform. Appl., 36, 277-291 (2002) · Zbl 1013.68088
[14] Mereghetti, C.; Palano, B.; Pighizzini, G., Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata, Theoret. Inform. Appl., 35, 477-490 (2001) · Zbl 1010.68068
[15] Mood, A. M.; Graybill, F. A.; Boes, D. C., Introduction to the Theory of Statistics (1983), McGraw-Hill: McGraw-Hill New York
[16] Paz, A., Introduction to Probabilistic Automata (1971), Academic Press: Academic Press New York · Zbl 0234.94055
[17] J.E. Pin, On languages accepted by finite reversible automata, in: Proc. 14th Internat. Colloq. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 267, Springer, Berlin, 1987, pp. 237-249.; J.E. Pin, On languages accepted by finite reversible automata, in: Proc. 14th Internat. Colloq. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 267, Springer, Berlin, 1987, pp. 237-249. · Zbl 0627.68069
[18] Rabin, M., Probabilistic automata, Inform. Control, 6, 230-245 (1963) · Zbl 0182.33602
[19] V.N. Vapnik, Inductive principles of the search for empirical dependencies, in: Proc. Second Workshop on Computer in Learning Theory, Morgan Kaufmann, Los Altos, CA, 1989, pp. 1-21.; V.N. Vapnik, Inductive principles of the search for empirical dependencies, in: Proc. Second Workshop on Computer in Learning Theory, Morgan Kaufmann, Los Altos, CA, 1989, pp. 1-21. · Zbl 0746.68075
[20] Vapnik, V. N.; Chervonenkis, A. Y., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 264-280 (1971) · Zbl 0247.60005
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.