Ansis Rosmanis

We prove tight lower bounds for the following variant of the counting problem considered by Aaronson \etal. The task is to distinguish whether an input set $x\subseteq [n]$ has size either $k$ or $k’=(1+\epsilon)k$. We assume the algorithm has access to

We study how efficiently a k-element set S subseteq [n] can be learned from a uniform superposition ket{S} of its elements. One can think of ket{S}=sum_{i in S} ket{i}/sqrt{|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 ket{S} suffice, in contrast to the Theta(k log k) random samples needed by a classical coupon collector. On the other hand, if n-k=Omega(k), then Omega(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 ket{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.

In his seminal work on recording quantum queries [Crypto 2019], Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. Zhandry presented a framework for interpreting various states in the quantum space of the oracle that can be used to provide security proofs in quantum cryptography. In this paper, we introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography. Additionally, we show how this framework can be used to prove that the success probability for a k-query quantum algorithm that attempts to invert a random N-element permutation is at most O(k^2/N).