Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1999 Copyright 1999 University of Bonn, Department of Computer Science, Abt. V
85204

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V