Optimal lower bounds for Quantum Learning via Information Theory

arXiv:2301.02227v3 Announce Type: replace-cross
Abstract: Although a concept class may be learnt more efficiently using quantum samples as compared with classical samples in certain scenarios, Arunachalam and de Wolf (JMLR, 2018) proved that quantum learners are asymptotically no more efficient than classical ones in the quantum PAC and Agnostic learning models. They established lower bounds on sample complexity via quantum state identification and Fourier analysis. In this paper, we derive optimal lower bounds for quantum sample complexity in both the …

abstract arxiv class concept cs.cc cs.it cs.lg information math.it quant-ph quantum samples theory type via