We show that, for any stochastic event of period , there exists a measure-once one-way quantum finite automaton (1qfa) with at most states inducing the event , for constants , , satisfying . This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period can be accepted with isolated cut point by a 1qfa with no more than states. Our results give added evidence of the strength of measure-once 1qfa’s with respect to classical automata.
Mots clés : quantum finite automata, periodic events and languages
@article{ITA_2002__36_3_277_0, author = {Mereghetti, Carlo and Palano, Beatrice}, title = {On the size of one-way quantum finite automata with periodic behaviors}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {277--291}, publisher = {EDP-Sciences}, volume = {36}, number = {3}, year = {2002}, doi = {10.1051/ita:2002014}, mrnumber = {1958244}, zbl = {1013.68088}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2002014/} }
TY - JOUR AU - Mereghetti, Carlo AU - Palano, Beatrice TI - On the size of one-way quantum finite automata with periodic behaviors JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2002 SP - 277 EP - 291 VL - 36 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2002014/ DO - 10.1051/ita:2002014 LA - en ID - ITA_2002__36_3_277_0 ER -
%0 Journal Article %A Mereghetti, Carlo %A Palano, Beatrice %T On the size of one-way quantum finite automata with periodic behaviors %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2002 %P 277-291 %V 36 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2002014/ %R 10.1051/ita:2002014 %G en %F ITA_2002__36_3_277_0
Mereghetti, Carlo; Palano, Beatrice. On the size of one-way quantum finite automata with periodic behaviors. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 277-291. doi : 10.1051/ita:2002014. http://www.numdam.org/articles/10.1051/ita:2002014/
[1] The Design and Analysis of Computer Algorithms. Addison-Wesley (1974). | MR | Zbl
, and ,[2] On the Class of Languages Recognizable by 1-way Quantum Finite Automata, in Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science. Springer, Lecture Notes in Comput. Sci. 2010 (2001) 305-316. | MR | Zbl
, and ,[3] Two-way Finite Automata with Quantum and Classical States. Technical Report (1999) quant-ph/9911009. | Zbl
and ,[4]
and , 1-way Quantum Finite Automata: Strengths, Weaknesses and Generalizations, in Proc. 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press (1998) 332-342.[5] Characterizations of 1-Way Quantum Finite Automata, Technical Report. Department of Computer Science, University of British Columbia, TR-99-03 (revised). | Zbl
and ,[6] Quorums from Difference Covers. Inform. Process. Lett. 75 (2000) 9-12. | MR
and ,[7] A Fast Quantum Mechanical Algorithm for Database Search, in Proc. 28th ACM Symposium on Theory of Computing (1996) 212-219. | MR | Zbl
,[8] Quantum Computing. McGraw-Hill (1999). | MR
,[9] Descriptional complexity issues in quantum computing. J. Autom. Lang. Comb. 5 (2000) 191-218. | MR | Zbl
,[10] The Structure and Complexity of Minimal nfa's over a Unary Alphabet. Int. J. Found. Comput. Sci. 2 (1991) 163-182. | Zbl
, and ,[11] A Small 1-way Quantum Finite Automaton. Technical Report (1998) quant-ph/9810065.
,[12] Practical Numerical Methods: Algorithms and Programs. The Macmillan Company (1987). | MR | Zbl
,[13] On the Power of Quantum Finite State Automata, in Proc. 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press (1997) 66-75.
and ,[14] Introduction to Linear Algebra. The Macmillan Company (1965). Reprinted by Dover (1988). | MR | Zbl
and ,[15] A Survey of Matrix Theory and Matrix Inequalities. Prindle, Weber & Schmidt (1964). Reprinted by Dover (1992). | MR | Zbl
and ,[16] Upper Bounds on the Size of One-way Quantum Finite Automata, in Proc. 7th Italian Conference on Theoretical Computer Science. Springer, Lecture Notes in Comput. Sci. 2202 (2001) 123-135. | MR | Zbl
and ,[17] On the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata, in Pre-Proc. Descriptional Complexity of Automata, Grammars and Related Structures. Univ. Otto Von Guericke, Magdeburg, Germany (2001) 141-148. RAIRO: Theoret. Informatics Appl. (to appear). | Numdam | MR | Zbl
, and ,[18] Two-Way Automata Simulations and Unary Languages. J. Autom. Lang. Comb. 5 (2000) 287-300. | MR | Zbl
and ,[19] Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. | MR | Zbl
and ,[20] On Languages Accepted by finite reversible automata, in Proc. 14th International Colloquium on Automata, Languages and Programming. Springer-Verlag, Lecture Notes in Comput. Sci. 267 (1987) 237-249. | MR | Zbl
,[21] Algorithms for Quantum Computation: Discrete Logarithms and Factoring, in Proc. 35th Annual Symposium on Foundations of Computer Science. IEEE Computer Science Press (1994) 124-134. | MR
,[22] Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (1997) 1484-1509. | MR | Zbl
,[23] A note on restricted difference bases. J. London Math. Soc. 38 (1963) 465-466. | MR | Zbl
,Cité par Sources :