Languages recognized by nondeterministic quantum finite automata

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

A new version with major revisions, 24 pages, latex

Scientific paper

The nondeterministic quantum finite automaton (NQFA) is the only known case where a one-way quantum finite automaton (QFA) model has been shown to be strictly superior in terms of language recognition power to its probabilistic counterpart. We give a characterization of the class of languages recognized by NQFA's, demonstrating that it is equal to the class of exclusive stochastic languages. We also characterize the class of languages that are recognized necessarily by two-sided error by QFA's. It is shown that these classes remain the same when the QFA's used in their definitions are replaced by several different model variants that have appeared in the literature. We prove several closure properties of the related classes. The ramifications of these results about classical and quantum sublogarithmic space complexity classes are examined.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Languages recognized by nondeterministic 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 Languages recognized by nondeterministic quantum finite automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Languages recognized by nondeterministic quantum finite automata will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-556280

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.