Quantum Coupon Collector

We study how efficiently a k-element set S\subset[n] can be learned from a uniform superposition |S〉=\sum_{i\in S} |i〉/\sqrt{|S|} of its elements. One can think of |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 Theta(k log(k)) random samples needed by a classical coupon collector. On the other hand, if n−k=Omega(k), then Omega(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.

This is joint work with Srinivasan Arunachalam, Aleksandrs Belovs, Andrew Childs, Robin Kothari, and Ansis Rosmanis (https://arxiv.org/abs/2002.07688)