Quantum Coupon Collector

We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle$ of its elements. One can think of $|Srangle=sum_{iin S}|irangle/sqrt{|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 $|Srangle$ suffice, in contrast to the $Theta(klog k)$ random samples needed by a classical coupon collector. On the other hand, if $n-k=Omega(k)$, then $Omega(klog 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 $|Srangle$. 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.