6533b85efe1ef96bd12c05ff

RESEARCH PRODUCT

Improved Constructions of Quantum Automata

subject

description

We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use $\frac{4}{\epsilon} \log 2p + O(1)$ states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of logp than the previously known construction of [2]. Similarly to [2], our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some preliminary results in this direction.