01482nas a2200145 4500008004100000245005500041210005500096260001500151300000900166490000700175520108100182100001901263700001701282856003701299 2020 eng d00aDistributional property testing in a quantum world0 aDistributional property testing in a quantum world c02/02/2019 a1-250 v253 a
A fundamental problem in statistics and learning theory is to test properties of distributions. We show that quantum computers can solve such problems with significant speed-ups. In particular, we give fast quantum algorithms for testing closeness between unknown distributions, testing independence between two distributions, and estimating the Shannon / von Neumann entropy of distributions. The distributions can be either classical or quantum, however our quantum algorithms require coherent quantum access to a process preparing the samples. Our results build on the recent technique of quantum singular value transformation, combined with more standard tricks such as divide-and-conquer. The presented approach is a natural fit for distributional property testing both in the classical and the quantum case, demonstrating the first speed-ups for testing properties of density operators that can be accessed coherently rather than only via sampling; for classical distributions our algorithms significantly improve the precision dependence of some earlier results.
1 aGilyen, Andras1 aLi, Tongyang uhttps://arxiv.org/abs/1902.00814