%0 Generic %1 Aaronson2011 %A Aaronson, Scott %A Drucker, Andrew %D 2011 %K complexity computational quantum %T Advice Coins for Classical and Quantum Computation %U http://arxiv.org/abs/1101.5355 %X We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states can be sensitive to arbitrarily small changes in a coin's bias. This contrasts with classical probabilistic finite automata, whose sensitivity to changes in a coin's bias is bounded by a classic 1970 result of Hellman and Cover. Despite this finding, we are able to bound the power of advice coins for space-bounded classical and quantum computation. We define the classes BPPSPACE/coin and BQPSPACE/coin, of languages decidable by classical and quantum polynomial-space machines with advice coins. Our main theorem is that both classes coincide with PSPACE/poly. Proving this result turns out to require substantial machinery. We use an algorithm due to Neff for finding roots of polynomials in NC; a result from algebraic geometry that lower-bounds the separation of a polynomial's roots; and a result on fixed-points of superoperators due to Aaronson and Watrous, originally proved in the context of quantum computing with closed timelike curves.

@misc{Aaronson2011, abstract = { We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states can be sensitive to arbitrarily small changes in a coin's bias. This contrasts with classical probabilistic finite automata, whose sensitivity to changes in a coin's bias is bounded by a classic 1970 result of Hellman and Cover. Despite this finding, we are able to bound the power of advice coins for space-bounded classical and quantum computation. We define the classes BPPSPACE/coin and BQPSPACE/coin, of languages decidable by classical and quantum polynomial-space machines with advice coins. Our main theorem is that both classes coincide with PSPACE/poly. Proving this result turns out to require substantial machinery. We use an algorithm due to Neff for finding roots of polynomials in NC; a result from algebraic geometry that lower-bounds the separation of a polynomial's roots; and a result on fixed-points of superoperators due to Aaronson and Watrous, originally proved in the context of quantum computing with closed timelike curves. }, added-at = {2011-01-28T16:37:24.000+0100}, author = {Aaronson, Scott and Drucker, Andrew}, biburl = {https://www.bibsonomy.org/bibtex/20d49e0219be04c043bd19b5054273826/hwello}, description = {[1101.5355] Advice Coins for Classical and Quantum Computation}, interhash = {c5426975de57629276b96658b4f9dc51}, intrahash = {0d49e0219be04c043bd19b5054273826}, keywords = {complexity computational quantum}, note = {cite arxiv:1101.5355 Comment: 23 pages, 2 figures}, timestamp = {2011-01-28T16:37:24.000+0100}, title = {Advice Coins for Classical and Quantum Computation}, url = {http://arxiv.org/abs/1101.5355}, year = 2011 }