Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with unrestricted amplitudes:
TR14-159 | 27th November 2014
A. C. Cem Say, Abuzer Yakaryilmaz

Magic coins are useful for small-space quantum machines

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 ... more >>>

ISSN 1433-8092 | Imprint