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.