TY - JOUR T1 - Quantum Coupon Collector JF - Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics Y1 - 2020 A1 - Srinivasan Arunachalam A1 - Aleksandrs Belovs A1 - Andrew M. Childs A1 - Robin Kothari A1 - Ansis Rosmanis A1 - Ronald de Wolf AB -

We study how efficiently a k-element set S⊆[n] can be learned from a uniform superposition |S⟩ of its elements. One can think of |S⟩=∑i∈S|i⟩/|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 Θ(klogk) random samples needed by a classical coupon collector. On the other hand, if n−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⟩. 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.

VL - 158 U4 - 10:1-10:17 UR - https://arxiv.org/abs/2002.07688 U5 - 10.4230/LIPIcs.TQC.2020.10 ER -