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.

We show that, for any stochastic event $p$ of period $n$, there exists a measure-once one-way quantum finite automaton (1qfa) with at most $2\sqrt{6n}+25$ states inducing the event $ap+b$, for constants $a>0$, $b\phantom{\rule{-0.166667em}{0ex}}\ge 0$, satisfying $a+b\le 1$. 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 $n$ can be accepted with isolated cut point by a 1qfa with no more than $2\sqrt{6n}+26$ states. Our results give added evidence of the strength of measure-once 1qfa’s with respect to classical automata.

DOI : https://doi.org/10.1051/ita:2002014
Classification : 68Q10,  68Q19,  68Q45
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},
zbl = {1013.68088},
mrnumber = {1958244},
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
DA  - 2002///
SP  - 277
EP  - 291
VL  - 36
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2002014/
UR  - https://zbmath.org/?q=an%3A1013.68088
UR  - https://www.ams.org/mathscinet-getitem?mr=1958244
UR  - https://doi.org/10.1051/ita:2002014
DO  - 10.1051/ita:2002014
LA  - en
ID  - ITA_2002__36_3_277_0
ER  - 
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] A. Aho, J. Hopcroft and J. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley (1974). | MR 413592 | Zbl 0326.68005

[2] A. Ambainis, A. Ķikusts and M. Valdats, 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 1890780 | Zbl 0976.68087

[3] A. Ambainis and J. Watrous, Two-way Finite Automata with Quantum and Classical States. Technical Report (1999) quant-ph/9911009. | Zbl 1061.68047

[4] A. Ambainis and R. Freivalds, 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] A. Brodsky and N. Pippenger, Characterizations of 1-Way Quantum Finite Automata, Technical Report. Department of Computer Science, University of British Columbia, TR-99-03 (revised). | Zbl 1051.68062

[6] C. Colbourn and A. Ling, Quorums from Difference Covers. Inform. Process. Lett. 75 (2000) 9-12. | MR 1774826

[7] L. Grover, A Fast Quantum Mechanical Algorithm for Database Search, in Proc. 28th ACM Symposium on Theory of Computing (1996) 212-219. | MR 1427516 | Zbl 0922.68044

[8] J. Gruska, Quantum Computing. McGraw-Hill (1999). | MR 1978991

[9] J. Gruska, Descriptional complexity issues in quantum computing. J. Autom. Lang. Comb. 5 (2000) 191-218. | MR 1778471 | Zbl 0965.68021

[10] T. Jiang, E. Mcdowell and B. Ravikumar, The Structure and Complexity of Minimal nfa's over a Unary Alphabet. Int. J. Found. Comput. Sci. 2 (1991) 163-182. | Zbl 0746.68040

[11] A. Ķikusts, A Small 1-way Quantum Finite Automaton. Technical Report (1998) quant-ph/9810065.

[12] M. Kohn, Practical Numerical Methods: Algorithms and Programs. The Macmillan Company (1987). | MR 892962 | Zbl 0665.65002

[13] A. Kondacs and J. Watrous, 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.

[14] M. Marcus and H. Minc, Introduction to Linear Algebra. The Macmillan Company (1965). Reprinted by Dover (1988). | MR 188221 | Zbl 0142.26801

[15] M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities. Prindle, Weber & Schmidt (1964). Reprinted by Dover (1992). | MR 1215484 | Zbl 0126.02404

[16] C. Mereghetti and B. Palano, 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 1915411 | Zbl 1042.68066

[17] C. Mereghetti, B. Palano and G. Pighizzini, 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 1908867 | Zbl 1010.68068

[18] C. Mereghetti and G. Pighizzini, Two-Way Automata Simulations and Unary Languages. J. Autom. Lang. Comb. 5 (2000) 287-300. | MR 1778478 | Zbl 0965.68043

[19] C. Moore and J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. | MR 1756213 | Zbl 0939.68037

[20] J.-E. Pin, 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 912712 | Zbl 0627.68069

[21] P. Shor, 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 1489242

[22] P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (1997) 1484-1509. | MR 1471990 | Zbl 1005.11065

[23] B. Wichmann, A note on restricted difference bases. J. London Math. Soc. 38 (1963) 465-466. | MR 158857 | Zbl 0123.04302

Cité par Sources :