Proper vs Improper Quantum PAC learning
Ashwin Nayak Pulkit Sinha
A basic question in the PAC model of learning is whether proper learning is
harder than improper learning. In the classical case, there are examples of
concept classes with VC dimension $d$ that have sample complexity
$\Omega\left(\frac d\epsilon\log\frac1\epsilon\right)$ for proper learning with
error $\epsilon$, while the complexity for improper learning is O$\!\left(\frac
d\epsilon\right)$. One such example arises from the Coupon Collector problem.
  Motivated by the efficiency of proper versus improper learning with quantum
samples, Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC 2020)
studied an analogue, the Quantum Coupon Collector problem. Curiously, they
discovered that for learning size $k$ subsets of $[n]$ the problem has sample
complexity $\Theta(k\log\min\{k,n-k+1\})$, in contrast with the complexity of
$\Theta(k\log k)$ for Coupon Collector. This effectively negates the
possibility of a separation between the two modes of learning via the quantum
problem, and Arunachalam et al.\ posed the possibility of such a separation as
an open question.
  In this work, we first present an algorithm for the Quantum Coupon Collector
problem with sample complexity that matches the sharper lower bound of
$(1-o_k(1))k\ln\min\{k,n-k+1\}$ shown recently by Bab Hadiashar, Nayak, and
Sinha (IEEE TIT 2024), for the entire range of the parameter $k$. Next, we
devise a variant of the problem, the Quantum Padded Coupon Collector. We prove
that its sample complexity matches that of the classical Coupon Collector
problem for both modes of learning, thereby exhibiting the same asymptotic
separation between proper and improper quantum learning as mentioned above. The
techniques we develop in the process can be directly applied to any form of
padded quantum data. We hope that padding can more generally lift other forms
of classical learning behaviour to the quantum setting.