  Although polynomial-time probabilistic Turing machines can utilize
uncomputable transition probabilities to recognize uncountably many languages
with bounded error when allowed to use logarithmic space, it is known that such
"magic coins" give no additional computational power to constant-space versions
of those machines. We show that adding a few quantum bits to the model changes
the picture dramatically. For every language $L$, there exists such a two-way
quantum finite automaton that recognizes a language of the same Turing degree
as $L$ with bounded error in polynomial time. When used as verifiers in
public-coin interactive proof systems, such automata can verify membership in
all languages with bounded error, outperforming their classical counterparts,
which are known to fail for the palindromes language.
