Paper Info
Title
Magic coins are useful for small-space quantum machines.
Abstract
Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use double 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 (2qcfa) 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. Corollaries demonstrate even faster machines when one is allowed to use a counter as memory, and an alternative proof of the uncountability of stochastic languages.
Year
Venue
Keywords
2014
QUANTUM INFORMATION & COMPUTATION
real-valued transitions,quantum automata,interactive proof systems
DocType
Volume
Issue
Journal
17
11-12
ISSN
Citations 
PageRank 
1533-7146
4
0.52
References 
Authors
10
2
Name
Order
Citations
PageRank
A. C. Cem Say119326.13
Abuzer Yakaryilmaz216825.31