Back to Search
Start Over
Quantum coupon collector
- Publication Year :
- 2020
-
Abstract
- 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.
Details
- Database :
- OAIster
- Notes :
- application/pdf, English
- Publication Type :
- Electronic Resource
- Accession number :
- edsoai.on1366582575
- Document Type :
- Electronic Resource
- Full Text :
- https://doi.org/10.4230.LIPIcs.TQC.2020.10