Computer Science – Computational Complexity
Scientific paper
2009-02-28
Computer Science
Computational Complexity
A new version, 21 pages, latex
Scientific paper
We prove that two-way probabilistic and quantum finite automata (2PFA's and 2QFA's) can be considerably more concise than both their one-way versions (1PFA's and 1QFA's), and two-way nondeterministic finite automata (2NFA's). For this purpose, we demonstrate several infinite families of regular languages which can be recognized with some fixed probability greater than $ {1/2} $ by just tuning the transition amplitudes of a 2QFA (and, in one case, a 2PFA) with a constant number of states, whereas the sizes of the corresponding 1PFA's, 1QFA's and 2NFA's grow without bound. We also show that 2QFA's with mixed states can support highly efficient probability amplification. The weakest known model of computation where quantum computers recognize more languages with bounded error than their classical counterparts is introduced.
Cem Say A. C.
Yakaryilmaz Abuzer
No associations
LandOfFree
Succinctness of two-way probabilistic and quantum finite 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 Succinctness of two-way probabilistic and quantum finite automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinctness of two-way probabilistic and quantum finite automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-48550