文章基本信息
- 标题：Quantum Coupon Collector
- 本地全文：下载
- 作者：Srinivasan Arunachalam ; Aleksandrs Belovs ; Andrew M. Childs 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：158
- 页码：10:1-10:17
- DOI：10.4230/LIPIcs.TQC.2020.10
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：We study how efficiently a k-element set SâS[n] can be learned from a uniform superposition S> of its elements. One can think of S>=â^'_{iâ^^S} i>/â^S 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 Î~(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 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.
- 关键词：Quantum algorithms; Adversary method; Coupon collector; Quantum learning theory
