@inproceedings{36edd325341240afb5041ebbbe7a0309,
title = "Quantum finite multitape automata",
abstract = "Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] 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 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.",
author = "Andris Ambainis and Richard Bonner and Rusins Freivalds and Marats Golovkins and Marek Karpinski",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 26th Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 1999 ; Conference date: 27-11-1999 Through 04-12-1999",
year = "1999",
doi = "10.1007/3-540-47849-3\_21",
language = "English",
isbn = "354066694X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "340--348",
editor = "Jan Pavelka and Miroslav Barto{\v s}ek and Gerard Tel",
booktitle = "SOFSEM 1999",
address = "Germany",
}