大误差区间下量子 PAC 学习的无条件优势

研究者证明了在均匀分布与大误差区间下，布尔函数的量子 PAC 学习与经典 PAC 学习之间存在无条件的超多项式分离。针对优势 $\lambda(n) = n^{-\omega(1)}$，多项式时间量子学习器仅需量子随机样本即可输出多项式规模确定性经典电路并达到 $1/2+\lambda(n)$ 的一致度，而经典学习器即便使用成员查询也无法达到同等水平。