@inproceedings{9233c45e10924385871aa0e7970eb6cd,
title = "Exact results for accepting probabilities of quantum automata",
abstract = "One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this paper, we determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recognized by a QFA with probability at most 0.7726.",
author = "Andris Ambainis and Arnolds Ķikusts",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 26th International Symposium on Mathematical Foundations of Computer Science, MFCS 2001 ; Conference date: 27-08-2001 Through 31-08-2001",
year = "2001",
doi = "10.1007/3-540-44683-4\_13",
language = "English",
isbn = "9783540446835",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "135--147",
editor = "Jiri Sgall and Ales Pultr and Petr Kolman",
booktitle = "Mathematical Foundations of Computer Science 2001 - 26th International Symposium, MFCS 2001, Proceedings",
address = "Germany",
}