4 papers · 1 filter
Exact results for accepting probabilities of quantum automata
Andris Ambainis, Arnolds Kikusts
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 pap…
On the class of languages recognizable by 1-way quantum finite automata
Andris Ambainis, Arnolds Kikusts, Maris Valdats
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) l…
Probabilities to accept languages by quantum finite automata
Andris Ambainis, Richard Bonner, Rusins Freivalds +1
We construct a hierarchy of regular languages such that the current language in the hierarchy can be accepted by 1-way quantum finite automata with a probability smaller than the c…
A small 1-way quantum finite automaton
Arnolds Kikusts
We study 1-way quantum finite automata (QFAs) and compare them with their classical counterparts. We show that 1-way QFAs can be very space efficient. We construct a 1-way QFAs tha…