Title Upper Bounds on the Size of One-way Quantum Finite Automata Authors Carlo Mereghetti, Dipartimento di Informatica, Sistemistica e Comunicazione - Universita degli Studi di Milano - Bicocca Beatrice Palano, Dipartimento di Informatica - Universita degli Studi di Torino Main Fields 2. automata 8. formal languages 11. new computing paradigm Other Main Fields Quantum Computing Abstract + Keywords We show that, for any stochastic event $p$ of period $n$, there exists a {\em 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\geq 0$, satisfying $a+b\leq1$. 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. Keywords: quantum finite automata; periodic events and languages