



@article {2557,
	title = {Quantum Coupon Collector},
	journal = {Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics},
	volume = {158},
	year = {2020},
	month = {2/18/2020},
	pages = {10:1-10:17},
	abstract = {<p>We study how efficiently a k-element set S\&sube;[n] can be learned from a uniform superposition |S\&rang; of its elements. One can think of |S\&rang;=\&sum;i\&isin;S|i\&rang;/|S|\&minus;\&minus;\&minus;\&radic; as the quantum version of a uniformly random sample over S, as in the classical analysis of the {\textquoteleft}{\textquoteleft}coupon collector problem.\&$\#$39;\&$\#$39; 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\&minus;k=O(1) missing elements then O(k) copies of |S\&rang; suffice, in contrast to the Θ(klogk) random samples needed by a classical coupon collector. On the other hand, if n\&minus;k=Ω(k), then Ω(klogk) 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\&rang;. 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.</p>},
	doi = {10.4230/LIPIcs.TQC.2020.10},
	url = {https://arxiv.org/abs/2002.07688},
	author = {Srinivasan Arunachalam and Aleksandrs Belovs and Andrew M. Childs and Robin Kothari and Ansis Rosmanis and Ronald de Wolf}
}
