Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-159 | 27th November 2014 13:20

Magic coins are useful for small-space quantum machines


Authors: A. C. Cem Say, Abuzer Yakaryilmaz
Publication: 27th November 2014 13:25
Downloads: 831


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.

ISSN 1433-8092 | Imprint