Guglielmo Mazzola, Simon Mathis, et al.
APS March Meeting 2021
We study how efficiently a k-element set S ? [n] can be learned from a uniform superposition |Si of its elements. One can think of |Si = Pi?S |ii/p|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 |Si suffice, in contrast to the T(k log k) random samples needed by a classical coupon collector. On the other hand, if n - k = ?(k), then ?(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 |Si. 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.
Guglielmo Mazzola, Simon Mathis, et al.
APS March Meeting 2021
Srinivasan Arunachalam, Penghui Yao
STOC 2022
Charles Hadfield, Sergey Bravyi, et al.
APS March Meeting 2021
Elisa Bäumer, Vinay Tripathi, et al.
APS March Meeting 2024