Computer Science – Computational Complexity
Scientific paper
2009-01-18
Computer Science
Computational Complexity
2 pages, poster presented at the 4th Workshop on Theory of Quantum Computation, Communication, and Cryptography (TQC2009)
Scientific paper
In this note, we generalize the results of arXiv:0901.2703v1 We show that all one-way quantum finite automaton (QFA) models that are at least as general as Kondacs-Watrous QFA's are equivalent in power to classical probabilistic finite automata in this setting. Unlike their probabilistic counterparts, allowing the tape head to stay put for some steps during its traversal of the input does enlarge the class of languages recognized by such QFA's with unbounded error. (Note that, the proof of Theorem 1 in the abstract was presented in the previous version (arXiv:0901.2703v1).)
Cem Say A. C.
Yakaryilmaz Abuzer
No associations
LandOfFree
Language recognition by generalized quantum finite automata with unbounded error (abstract & poster) 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 Language recognition by generalized quantum finite automata with unbounded error (abstract & poster), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Language recognition by generalized quantum finite automata with unbounded error (abstract & poster) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-701960