%0 Journal Article %J Proceedings of ITCS 2020 %D 2020 %T Distributional property testing in a quantum world %A Andras Gilyen %A Tongyang Li %X

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.

%B Proceedings of ITCS 2020 %V 25 %P 1-25 %8 02/02/2019 %G eng %U https://arxiv.org/abs/1902.00814 %N 19 %R http://dx.doi.org/10.4230/LIPIcs.ITCS.2020.25