2020-06-01
Quantum coupon collector
Publication
Publication
We study how efficiently a k-element set S ? [n] can be learned from a uniform superposition |Si of its elements. One can think of |Si = Pi?S |ii/p|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 |Si suffice, in contrast to the T(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 |Si. 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.
Additional Metadata | |
---|---|
, , , | |
IBM , Microsoft Quantum, Redmond, USA , Microsoft Research, Redmond, USA | |
doi.org/10.4230/LIPIcs.TQC.2020.10 | |
Leibniz International Proceedings in Informatics, LIPIcs | |
Quantum algorithms and applications , Progress in quantum computing:Algorithms, communication, and applications , Quantum Software Consortium (024.003.037) | |
15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020 | |
, , | |
Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
Arunachalam, S., Belovs, A., Childs, A., Kothari, R., Rosmanis, A., & de Wolf, R. (2020). Quantum coupon collector. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020 (pp. 10:1–10:17). doi:10.4230/LIPIcs.TQC.2020.10 |