Improved constructions of quantum automata
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use 4/epsilon log 2p 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 log p than the previously known construction. Our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction. (C) 2009 Elsevier B.V. All rights reserved.
exponential advantage quantum finite automata quantum computation