Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1999 Copyright 1999 Universität Bonn, Institut für Informatik, Abt. V

Quantum Finite Multitape Automata
Andris Ambainis, Richard Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski
[Download PostScript] [Download PDF]

Quantum finite automata were introduced by C. Moore, J. P.Crutchfield \cite{MC 97}, and by A. Kondacs and J. Watrous \cite{KW97}. This notion is not a generalization of the deterministic finiteautomata. Moreover, in \cite{KW 97} it was proved that not all regularlanguages can be recognized by quantum finite automata. A. Ambainis andR. Freivalds \cite{AF 98} proved that for some languages quantum finiteautomata may be exponentially more concise rather than both deterministicand probabilistic finite automata. In this paper we introduce the notionof quantum finite multitape automata and prove that there is a languagerecognized by a quantum finite automaton but not by deterministic orprobabilistic finite automata. This is the first result on a problem whichcan be solved by a quantum computer but not by a deterministic orprobabilistic computer. Additionally we discover unexpectedprobabilistic automata recognizing complicated languages.

Last Change: 07/05/01 at 14:03:27
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope