Monday, April 30, 2012

1101.0798 (Shelby Kimmel)

Speed from Repetition    [PDF]

Shelby Kimmel
We present an oracle problem, which we call the Repeated Randomness problem, that a quantum algorithm can solve in one query, while any classical algorithm requires $\Omega(\log n)$ queries, where the oracle function has $2^n$ inputs. This problem has connections to the parity problem introduced by Bernstein and Vazirani \cite{Bernstein1993} and to a variation of the NAND tree described by Zhan et al \cite{Zhan}.
View original: http://arxiv.org/abs/1101.0798

No comments:

Post a Comment