| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 437824 | Theoretical Computer Science | 2009 | 7 Pages |
Abstract
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use 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.Our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
