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.

Adversary method, Coupon collector, Quantum algorithms, Quantum learning theory
15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

Arunachalam, S, Belovs, A, Childs, A.M, Kothari, R, Rosmanis, A, & de Wolf, R.M. (2020). Quantum coupon collector. In Leibniz International Proceedings in Informatics, LIPIcs. doi:10.4230/LIPIcs.TQC.2020.10