  We study how efficiently a $k$-element set $S\subseteq[n]$ can be learned
from a uniform superposition $|S\rangle$ of its elements. One can think of
$|S\rangle=\sum_{i\in S}|i\rangle/\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 $|S\rangle$
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\rangle$. 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.
