2026-07-24T02:23:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12069 2024-03-06T10:49:12Z ddc:004 open_access

Quantum Coupon Collector Arunachalam, Srinivasan Belovs, Aleksandrs Childs, Andrew M. Kothari, Robin Rosmanis, Ansis de Wolf, Ronald Quantum algorithms Adversary method Coupon collector Quantum learning theory 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 Θ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Srinivasan Arunachalam and Aleksandrs Belovs and Andrew M. Childs and Robin Kothari and Ansis Rosmanis and Ronald de Wolf 2020 Is Part Of LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2020.10 urn:nbn:de:0030-drops-120692 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.10 eng https://creativecommons.org/licenses/by/3.0/legalcode