Quantum finite multitape automata

Details Quantum finite multitape automata Quantum finite multitape automata

1999-05-07

arxiv.org/abs/quant-ph/9905026v1

Physics

Quantum Physics

14 pages, LaTeX

Scientific paper

Quantum finite automata were introduced by C.Moore, J.P. Crutchfield, and by A.Kondacs and J.Watrous. This notion is not a generalization of the deterministic finite automata. Moreover, it was proved that not all regular languages can be recognized by quantum finite automata. A.Ambainis and R.Freivalds proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by a deterministic or probabilistic finite automata. This is the first result on a problem which can be solved by a quantum computer but not by a deterministic or probabilistic computer. Additionally we discover unexpected probabilistic automata recognizing complicated languages.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599398