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.