Improved constructions of quantum automata

Details Improved constructions of quantum automata Improved constructions of quantum automata

2008-05-12

arxiv.org/abs/0805.1686v1

Physics

Quantum Physics

9 pages

Scientific paper

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 \log p than the previously known construction of Ambainis and Freivalds (quant-ph/9802062). Similarly to Ambainis and Freivalds, our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.

Affiliated with

Also associated with

No associations

Rating

Improved constructions of quantum automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved constructions of quantum automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved constructions of quantum automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-326101