| 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 |