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. We also introduce a novel access model for quantum distributions, enabling the coherent preparation of quantum samples, and propose a general framework that can naturally handle both classical and quantum distributions in a unified manner. Our framework generalizes and improves previous quantum algorithms for testing closeness between unknown distributions, testing independence between two distributions, and estimating the Shannon / von Neumann entropy of distributions. For classical distributions our algorithms significantly improve the precision dependence of some earlier results. We also show that in our framework procedures for classical distributions can be directly lifted to the more general case of quantum distributions, and thus obtain the first speed-ups for testing properties of density operators that can be accessed coherently rather than only via sampling.
@InProceedings{gilyen_et_al:LIPIcs.ITCS.2020.25, author = {Gily\'{e}n, Andr\'{a}s and Li, Tongyang}, title = {{Distributional Property Testing in a Quantum World}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {25:1--25:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.25}, URN = {urn:nbn:de:0030-drops-117100}, doi = {10.4230/LIPIcs.ITCS.2020.25}, annote = {Keywords: distributional property testing, quantum algorithms, quantum query complexity} }
Feedback for Dagstuhl Publishing