Document Open Access Logo

Distributional Property Testing in a Quantum World

Authors András Gilyén, Tongyang Li

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2020.25.pdf
  • Filesize: 0.67 MB
  • 19 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Distribution functions
  • Theory of computation → Algorithm design techniques
  • Theory of computation → Quantum query complexity
Keywords
  • distributional property testing
  • quantum algorithms
  • quantum query complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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. 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.

Cite As Get BibTex

András Gilyén and Tongyang Li. Distributional Property Testing in a Quantum World. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.25

Author Details

András Gilyén
  • QuSoft, CWI and University of Amsterdam, The Netherlands
Tongyang Li
  • Department of Computer Science, Institute for Advanced Computer Studies, University of Maryland, USA
  • Joint Center for Quantum Information and Computer Science, University of Maryland, USA

Funding

  • Gilyén, András: Supported by ERC Consolidator Grant QPROGRESS and partially supported by QuantERA project QuantAlgo 680-91-034.
  • Li, Tongyang: Supported by IBM PhD Fellowship, QISE-NET Triplet Award (NSF DMR-1747426), and the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams program.

Acknowledgements

A.G. thanks Ronald de Wolf, Ignacio Cirac and Yimin Ge for useful discussion. T.L. thanks Xiaodi Wu and Nengkun Yu for useful discussion.

References

  1. Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh. A unified maximum likelihood approach for estimating symmetric properties of discrete distributions. In \icml34th, pages 11-21, 2017. URL: http://proceedings.mlr.press/v70/acharya17a.html, URL: http://arxiv.org/abs/1611.02960.
  2. Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In \nips28, pages 3591-3599, 2015. URL: http://papers.nips.cc/paper/5839-optimal-testing-for-properties-of-distributions, URL: http://arxiv.org/abs/1507.05952.
  3. Jayadev Acharya, Ibrahim Issa, Nirmal V. Shende, and Aaron B. Wagner. Measuring Quantum Entropy. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 3012-3016, 2019. URL: http://arxiv.org/abs/1711.00814.
  4. Dorit Aharonov and Amnon Ta‐Shma. Adiabatic Quantum State Generation. \siamjc, 37(1):47-82, 2007. Earlier version in STOC'03, https://arxiv.org/abs/quant-ph/0301023. URL: http://dx.doi.org/10.1137/060648829.
  5. Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, and Ronald de Wolf. Two new results about quantum exact learnings, 2018. URL: http://arxiv.org/abs/1810.00481.
  6. Srinivasan Arunachalam and Ronald de Wolf. Optimal Quantum Sample Complexity of Learning Algorithms. In çc32nd, pages 25:1-25:31, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2017.25.
  7. Costin Bădescu, Ryan O'Donnell, and John Wright. Quantum state certification. In \stoc51st, pages 503-514. ACM, 2019. URL: http://dx.doi.org/10.1145/3313276.3316344.
  8. Tuğkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld. The complexity of approximating the entropy. \siamjc, 35(1):132-150, 2005. URL: http://dx.doi.org/10.1145/509907.510005.
  9. Tuğkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In \focs42nd, pages 442-451, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959920.
  10. Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing closeness of discrete distributions. \jacm, 60(1):4, 2013. URL: http://dx.doi.org/10.1145/2432622.2432626.
  11. Aleksandrs Belovs. Quantum Algorithms for Classical Probability Distributions, 2019. URL: http://arxiv.org/abs/1904.02192.
  12. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum Amplitude Amplification and Estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics Series, pages 53-74. AMS, 2002. URL: http://dx.doi.org/10.1090/conm/305.
  13. Sergey Bravyi, Aram W. Harrow, and Avinatan Hassidim. Quantum algorithms for testing properties of distributions. \ieeeit, 57(6):3971-3981, 2011. URL: http://dx.doi.org/10.1109/TIT.2011.2134250.
  14. Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum Fingerprinting. \prl, 87(16):167902, 2001. URL: http://dx.doi.org/10.1103/PhysRevLett.87.167902.
  15. Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In \stoc50th, 2018. URL: http://dx.doi.org/10.1145/3188745.3188784.
  16. André Chailloux. A Note on the Quantum Query Complexity of Permutation Symmetric Functions. In \itcs10th, pages 19:1-19:7, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2019.19.
  17. Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. In \icalp46th, 2019. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.28.
  18. Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald de Wolf. New Results on Quantum Property Testing. In \fsttcs30th, page 145, 2010. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.145.
  19. Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant. Optimal algorithms for testing closeness of discrete distributions. In \soda25th, pages 1193-1203, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.88.
  20. Ilias Diakonikolas and Daniel M. Kane. A new approach for testing properties of discrete distributions. In \focs57th, pages 685-694, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.78.
  21. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In \stoc51st, 2019. URL: http://dx.doi.org/10.1145/3313276.3316366.
  22. Oded Goldreich. Introduction to property testing. Cambridge University Press, 2017. Google Scholar
  23. Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, 63(9):5628-5641, 2017. URL: http://arxiv.org/abs/1508.01797.
  24. Yassine Hamoudi and Frédéric Magniez. Quantum Chebyshev’s Inequality and Applications. In \icalp46th, pages 69:1-69:16, 2019. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.69.
  25. Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions. \ieeeit, 61(5):2835-2885, 2015. URL: http://dx.doi.org/10.1109/TIT.2015.2412945.
  26. Reut Levi, Dana Ron, and Ronitt Rubinfeld. Testing properties of collections of distributions. Theory of Computing, 9(1):295-347, 2013. URL: http://dx.doi.org/10.4086/toc.2013.v009a008.
  27. Tongyang Li and Xiaodi Wu. Quantum Query Complexity of Entropy Estimation. \ieeeit, 65(5):2899-2921, 2019. URL: http://dx.doi.org/10.1109/TIT.2018.2883306.
  28. Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3:163, 2019. URL: http://dx.doi.org/10.22331/q-2019-07-12-163.
  29. Ashley Montanaro. Quantum speedup of Monte Carlo methods. \rspa, 471(2181), 2015. URL: http://dx.doi.org/10.1098/rspa.2015.0301.
  30. Ashley Montanaro and Ronald de Wolf. A Survey of Quantum Property Testing. Number 7 in Graduate Surveys. \tocl, 2016. http://arxiv.org/abs/1310.2035, URL: http://dx.doi.org/10.4086/toc.gs.2016.007.
  31. Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000. URL: http://dx.doi.org/10.1017/CBO9780511976667.
  32. Ryan O'Donnell and John Wright. Quantum Spectrum Testing. In \stoc47th, pages 529-538, 2015. URL: http://dx.doi.org/10.1145/2746539.2746582.
  33. Ryan O'Donnell and John Wright. Efficient Quantum Tomography. In \stoc48th, pages 899-912, 2016. URL: http://dx.doi.org/10.1145/2897518.2897544.
  34. Ryan O'Donnell and John Wright. Efficient quantum tomography II. In \stoc49th, pages 962-974, 2017. URL: http://dx.doi.org/10.1145/3055399.3055454.
  35. Liam Paninski. Estimation of entropy and mutual information. Neural Computation, 15(6):1191-1253, 2003. URL: http://dx.doi.org/10.1162/089976603321780272.
  36. Liam Paninski. Estimating entropy on m bins given fewer than m samples. \ieeeit, 50(9):2200-2203, 2004. URL: http://dx.doi.org/10.1109/TIT.2004.833360.
  37. Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. \ieeeit, 54(10):4750-4755, 2008. URL: http://dx.doi.org/10.1109/TIT.2008.928987.
  38. Alfréd Rényi. On measures of entropy and information. In Proceedings of the 4th Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 547-561. University of California Press, 1961. URL: https://projecteuclid.org/euclid.bsmsp/1200512181.
  39. Claude E. Shannon. A Mathematical Theory of Communication. Bell System Technical Journal, 27(3):379-423, 1948. URL: http://dx.doi.org/10.1002/j.1538-7305.1948.tb01338.x.
  40. Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. In \stoc43rd, pages 685-694, 2011. URL: http://dx.doi.org/10.1145/1993636.1993727.
  41. Gregory Valiant and Paul Valiant. The power of linear estimators. In \focs52nd, pages 403-412, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.81.
  42. Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. \ieeeit, 62(6):3702-3720, 2016. URL: http://dx.doi.org/10.1109/TIT.2016.2548468.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact