Document Open Access Logo

Quantum Coupon Collector

Authors Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf

PDF

File

Thumbnail PDF
PDF
LIPIcs.TQC.2020.10.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum algorithms
  • Adversary method
  • Coupon collector
  • Quantum learning theory

Metrics

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

Abstract

We study how efficiently a k-element set S⊆[n] can be learned from a uniform superposition |S> of its elements. One can think of |S>=∑_{i∈S}|i>/√|S| as the quantum version of a uniformly random sample over S, as in the classical analysis of the "coupon collector problem." We show that if k is close to n, then we can learn S using asymptotically fewer quantum samples than random samples. In particular, if there are n-k=O(1) missing elements then O(k) copies of |S> suffice, in contrast to the Θ(k log k) random samples needed by a classical coupon collector. On the other hand, if n-k=Ω(k), then Ω(k log k) quantum samples are necessary.
More generally, we give tight bounds on the number of quantum samples needed for every k and n, and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through |S>. Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.

Cite As Get BibTex

Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf. Quantum Coupon Collector. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.TQC.2020.10

Author Details

Srinivasan Arunachalam
  • IBM Research, Yorktown Heights, NY, USA
Aleksandrs Belovs
  • Faculty of Computing, University of Latvia, Riga, Latvia
Andrew M. Childs
  • Department of Computer Science, Institute for Advanced Computer Studies, University of Maryland, College Park, MD, USA
  • Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD, USA
Robin Kothari
  • Microsoft Quantum, Redmond, WA, USA
  • Microsoft Research, Redmond, WA, USA
Ansis Rosmanis
  • Graduate School of Mathematics, Nagoya University, Japan
Ronald de Wolf
  • QuSoft, Amsterdam, The Netherlands
  • CWI, Amsterdam, The Netherlands
  • University of Amsterdam, The Netherlands

Funding

  • Arunachalam, Srinivasan: Part of this work was done while a PhD student at CWI supported by ERC Consolidator Grant 615307-QPROGRESS, and a postdoc at MIT funded by the MIT-IBM Watson AI Lab under the project Machine learning in Hilbert space.
  • Belovs, Aleksandrs: Supported by the ERDF project number 1.1.1.2/I/16/113.
  • Childs, Andrew M.: Supported by the Army Research Office (grant W911NF-20-1-0015); the Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams and Accelerated Research in Quantum Computing programs; and the National Science Foundation (grant CCF-1813814).
  • Rosmanis, Ansis: Supported by the JSPS International Research Fellowship program and by the JSPS KAKENHI Grant Number JP19F19079.
  • de Wolf, Ronald: Partially supported by ERC Consolidator Grant 615307-QPROGRESS (which ended Feb 2019), and by the Dutch Research Council (NWO) through Gravitation-grant Quantum Software Consortium 024.003.037, and QuantERA project QuantAlgo 680-91-034.

References

  1. S. Aaronson, R. Kothari, W. Kretschmer, and J. Thaler. Quantum lower bounds for approximate counting via Laurent polynomials. arXiv:1904.08914, supersedes arXiv:1808.02420 and arXiv:1902.02398, 2019. Google Scholar
  2. D. Aharonov and A. Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03, page 20–29, 2003. URL: https://doi.org/10.1145/780542.780546.
  3. A. Ambainis, L. Magnin, M. Roetteler, and J. Roland. Symmetry-assisted adversaries for quantum state generation. In 2011 IEEE 26th Annual Conference on Computational Complexity, pages 167-177, June 2011. URL: https://doi.org/10.1109/CCC.2011.24.
  4. S. Arunachalam, S. Chakraborty, T. Lee, M. Paraashar, and R. de Wolf. Two new results about quantum exact learning. In 46th International Colloquium on Automata, Languages, and Programming, ICALP, pages 16:1-16:15, 2019. arXiv:1810.00481. Google Scholar
  5. S. Arunachalam and R. de Wolf. Guest column: A survey of quantum learning theory. SIGACT News, 48(2):41-67, 2017. arXiv:1701.06806. Google Scholar
  6. S. Arunachalam and R. de Wolf. Optimal quantum sample complexity of learning algorithms. Journal of Machine Learning Research, 19, 2018. Earlier version in CCC'17. arXiv:1607.00932. Google Scholar
  7. A. Atıcı and R. Servedio. Improved bounds on quantum learning algorithms. Quantum Information Processing, 4(5):355-386, 2005. quant-ph/0411140. Google Scholar
  8. A. Atıcı and R. Servedio. Quantum algorithms for learning and testing juntas. Quantum Information Processing, 6(5):323-348, 2009. arXiv:0707.3479. Google Scholar
  9. E. Bannai and T. Itō. Algebraic Combinatorics I: Association Schemes. Mathematics lecture note series. Benjamin/Cummings Pub. Co., 1984. Google Scholar
  10. H. Barnum and E. Knill. Reversing quantum dynamics with near-optimal quantum and classical fidelity. Journal of Mathematical Physics, 43:2097-2106, 2002. quant-ph/0004088. Google Scholar
  11. R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. jacm, 48(4):778-797, 2001. Earlier version in FOCS'98. quant-ph/9802049. Google Scholar
  12. A. Belovs. Applications of the Adversary Method in Quantum Query Algorithms. PhD thesis, University of Latvia, 2014. 1402.3858. Google Scholar
  13. A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. JACM, 36(4):929-965, 1989. Google Scholar
  14. G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53-74. AMS, 2002. quant-ph/0005055. Google Scholar
  15. N. H. Bshouty and J. C. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM Journal on Computing, 28(3):1136–-1153, 1999. Earlier version in COLT'95. Google Scholar
  16. C. Godsil. Association schemes. Available at https://www.math.uwaterloo.ca/~cgodsil/assocs/pdfs/Assoc.pdf, 2018. URL: https://www.math.uwaterloo.ca/~cgodsil/assocs/pdfs/Assoc.pdf.
  17. A. B. Grilo, I. Kerenidis, and T. Zijlstra. Learning with Errors is easy with quantum samples. Physical Review Letters A, 99:032314, 2019. arXiv: 1702.08255. Google Scholar
  18. S. Hanneke. The optimal sample complexity of PAC learning. Journal of Machine Learning Research, 17(38):1-15, 2016. arXiv:1507.00473. Google Scholar
  19. S. Hanneke. Personal communication with Srinivasan Arunachalam, February 2018. See also URL: https://cstheory.stackexchange.com/questions/40161/proper-pac-learning-vc-dimension-bounds.
  20. P. Høyer, T. Lee, and R. Špalek. Negative weights make adversaries stronger. In Proceedings of 39th ACM STOC, pages 526-535, 2007. quant-ph/0611054. Google Scholar
  21. T. Lee, R. Mittal, B. Reichardt, R. Špalek, and M. Szegedy. Quantum query complexity of state conversion. In Proceedings of 52nd IEEE FOCS, pages 344-353, 2011. arXiv:1011.3020. Google Scholar
  22. T. Lee and J. Roland. A strong direct product theorem for quantum query complexity. Computational Complexity, 22(2):429-462, 2013. Earlier version in CCC'12. arXiv:1104.4468. Google Scholar
  23. N. Lindzey and A. Rosmanis. A Tight Lower Bound For Non-Coherent Index Erasure. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 59:1-59:37, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.59.
  24. O. Montasser, S. Hanneke, and N. Srebro. VC classes are adversarially robustly learnable, but only improperly. Journal of Machine Learning Research, 99:1-19, 2019. Google Scholar
  25. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge International Series on Parallel Computation. Cambridge University Press, 1995. URL: https://doi.org/10.1017/CBO9780511814075.
  26. A. Rosmanis. Lower Bounds on Quantum Query and Learning Graph Complexities. PhD thesis, University of Waterloo, July 2014. Available at URL: http://hdl.handle.net/10012/8577.
  27. R. Servedio and S. Gortler. Equivalences and separations between quantum and classical learnability. SIAM Journal on Computing, 33(5):1067-1092, 2004. Combines earlier papers from ICALP'01 and CCC'01. quant-ph/0007036. Google Scholar
  28. L. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–-1142, 1984. Google Scholar
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