Abstract

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.

Publication Details
Publication Type
Journal Article
Year of Publication
2020
Volume
25
Number of Pages
1–25
DOI
10.4230/LIPIcs.ITCS.2020.25
URL
https://arxiv.org/abs/1902.00814
Journal
Proceedings of ITCS 2020
Contributors
Groups
Date Published
01/2020