# On the Size of One-way Quantum Finite Automata with Periodic Behaviors

Carlo Mereghetti; Beatrice Palano

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 36, Issue: 3, page 277-291
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMereghetti, Carlo, and Palano, Beatrice. "On the Size of One-way Quantum Finite Automata with Periodic Behaviors." RAIRO - Theoretical Informatics and Applications 36.3 (2010): 277-291. <http://eudml.org/doc/92702>.

@article{Mereghetti2010,

abstract = {
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 ≥ 0, satisfying a+b ≥ 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.
},

author = {Mereghetti, Carlo, Palano, Beatrice},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Quantum finite automata; periodic events and languages; measure-once one-way quantum finite automaton},

language = {eng},

month = {3},

number = {3},

pages = {277-291},

publisher = {EDP Sciences},

title = {On the Size of One-way Quantum Finite Automata with Periodic Behaviors},

url = {http://eudml.org/doc/92702},

volume = {36},

year = {2010},

}

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

DA - 2010/3//

PB - EDP Sciences

VL - 36

IS - 3

SP - 277

EP - 291

AB -
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 ≥ 0, satisfying a+b ≥ 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.

LA - eng

KW - Quantum finite automata; periodic events and languages; measure-once one-way quantum finite automaton

UR - http://eudml.org/doc/92702

ER -

## References

top- A. Aho, J. Hopcroft and J. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley (1974). Zbl0326.68005
- A. Ambainis, A. Kikusts and M. Valdats, On the Class of Languages Recognizable by1-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. Zbl0976.68087
- A. Ambainis and J. Watrous, Two-way Finite Automata with Quantum and Classical States. Technical Report (1999) quant-ph/9911009. Zbl1061.68047
- 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.
- 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). Zbl1051.68062
- C. Colbourn and A. Ling, Quorums from Difference Covers. Inform. Process. Lett.75 (2000) 9-12. Zbl1339.68089
- L. Grover, A Fast Quantum Mechanical Algorithm for Database Search, in Proc. 28th ACM Symposium on Theory of Computing (1996) 212-219. Zbl0922.68044
- J. Gruska, Quantum Computing. McGraw-Hill (1999).
- J. Gruska, Descriptional complexity issues in quantum computing. J. Autom. Lang. Comb.5 (2000) 191-218. Zbl0965.68021
- 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. Zbl0746.68040
- A. Kikusts, A Small 1-way Quantum Finite Automaton. Technical Report (1998) quant-ph/9810065.
- M. Kohn, Practical Numerical Methods: Algorithms and Programs. The MacmillanCompany (1987).
- 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.
- M. Marcus and H. Minc, Introduction to Linear Algebra. The Macmillan Company (1965). Reprinted by Dover (1988). Zbl0142.26801
- M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities. Prindle, Weber & Schmidt (1964). Reprinted by Dover (1992). Zbl0126.02404
- 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. Zbl1042.68066
- 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). Zbl1010.68068
- C. Mereghetti and G. Pighizzini, Two-Way Automata Simulations and Unary Languages. J. Autom. Lang. Comb.5 (2000) 287-300. Zbl0965.68043
- C. Moore and J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci.237 (2000) 275-306. Zbl0939.68037
- 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.
- P. Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, in Proc. 35th Annual Symposium on Foundations of Computer Science. IEEE ComputerScience Press (1994) 124-134.
- P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput.26 (1997) 1484-1509. Zbl1005.11065
- B. Wichmann, A note on restricted difference bases. J. London Math. Soc.38 (1963) 465-466. Zbl0123.04302

## Citations in EuDML Documents

top- Abuzer Yakaryılmaz, Superiority of one-way and realtime quantum machines
- Abuzer Yakaryılmaz, Superiority of one-way and realtime quantum machines
- Abuzer Yakaryılmaz, Superiority of one-way and realtime quantum machines
- Shenggen Zheng, Jozef Gruska, Daowen Qiu, On the state complexity of semi-quantum finite automata
- Carlo Mereghetti, Beatrice Palano, Quantum finite automata with control language

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.