Physics – Quantum Physics
Scientific paper
2010-05-04
Physics
Quantum Physics
2nd version: updated some references, in particular to Aaronson's Fourier checking problem
Scientific paper
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle $f:[n]\to[m]$. Here the probability $\PP_f(j)$ of an outcome $j\in[m]$ is the fraction of its domain that $f$ maps to $j$. We give quantum algorithms for testing whether two such distributions are identical or $\epsilon$-far in $L_1$-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles $f$ and $g$), then this testing can be done in roughly $\sqrt{m}$ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly $m^{1/3}$ quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about $m^{2/3}$ queries in the unknown-unknown case and about $\sqrt{m}$ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.
Chakraborty Sourav
Fischer Eldar
Matsliah Arie
Wolf Ronald de
No associations
LandOfFree
New Results on Quantum Property Testing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New Results on Quantum Property Testing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Results on Quantum Property Testing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-532228