Distributional property testing in a quantum world
  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.
