



01627nas a2200193   4500008004100000245002900041210002900070260001400099300001500113490000800128520112700136100002801263700002301291700002301314700001901337700002001356700002001376856003701396       2020                        eng d00aQuantum Coupon Collector0 aQuantum Coupon Collector  c2/18/2020  a10:1-10:170 v1583 a<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 ``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>1 aArunachalam, Srinivasan1 aBelovs, Aleksandrs1 aChilds, Andrew, M.1 aKothari, Robin1 aRosmanis, Ansis1 ade Wolf, Ronald  uhttps://arxiv.org/abs/2002.07688