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