



@article {2388,
	title = {Distributional property testing in a quantum world},
	journal = {Proceedings of ITCS 2020},
	volume = {25},
	year = {2020},
	month = {02/02/2019},
	pages = {1-25},
	abstract = {<p>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.</p>},
	doi = {http://dx.doi.org/10.4230/LIPIcs.ITCS.2020.25},
	url = {https://arxiv.org/abs/1902.00814},
	author = {Andras Gilyen and Tongyang Li}
}
