Suppose we are given two probability distributions on some N-element set. How many samples do we need to test whether the two distributions are close or far from each other in the L_1 norm? This problem known as Statistical Difference has been extensively studied during the last years in the field of property testing. I will describe quantum algorithms for Statistical Difference problem that provide a polynomial speed up in terms of the query complexity compared to the known classical lower bounds. Specifically, I will assume that each distribution can be generated by querying an oracle function on a random uniformly distributed input string. It will be shown that testing whether distributions are orthogonal requires approximately N^{1/2} queries classically and approximately N^{1/3} queries quantumly. Testing whether distributions are close requires approximately N^{2/3} queries classically and O(N^{1/2}) queries quantumly. This is a joint work with Aram Harrow (University of Bristol) and Avinatan Hassidim (The Hebrew University).
