Abstract of Paper

On the Lower Bounds for One-way Quantum Automata
by Farid Ablayev and Aida Gainutdinova

Abstract:

In the paper we consider measured-once ({MO-QFA}) and measured-many
({MM-QFA}) models of one-way quantum finite automaton. We prove that
for {MO-QFA } ${\cal Q}$ that $(1/2+\varepsilon)$-acceptes regular
language $L$ it is hold that
 
\[ dim({\cal Q})\geq  \frac{\log dim(A)}{\log
\left(1+\frac{1}{c\varepsilon}\right)} \]
 
where $A$ is a minimal deterministic finite automata accepting $L$,
$dim({\cal Q})$, and $dim(A)$ are complexity (number of states) of
automata ${\cal Q}$ and $A$ respectively, $(1/2-\varepsilon)$ is the
error of ${\cal Q}$ and $c$ is a positive constant.
 
The example of language presented by Ambainis and Freivalds in 1998
show that our lower bound is tight.  Similar lower bound is true for
MM-QFA model.