New Results on Quantum Property Testing

Understand

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.