Quantum algorithm for Statistical Difference problem

          @misc{ pirsa_PIRSA:09020008,
            doi = {10.48660/09020008},
            url = {https://pirsa.org/09020008},
            author = {Bravyi, Sergey},
            keywords = {Quantum Information},
            language = {en},
            title = {Quantum algorithm for Statistical Difference problem},
            publisher = {Perimeter Institute},
            year = {2009},
            month = {feb},
            note = {PIRSA:09020008 see, \url{https://pirsa.org}}
          }
          

Abstract

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).