Quantum Algorithms for Testing Properties of Distributions

Sergey Bravyi, Aram W. Harrow & Avinatan Hassidim
Suppose one has access to oracles generating samples from two unknown probability distributions $p$ and $q$ on some $N$-element set. How many samples does one need to test whether the two distributions are close or far from each other in the $L_1$-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is...