摘要
量子计算研究的核心挑战之一在于,能否在具有实际应用意义的近期限量子电路中找到量子优势。基于此,本文在概率近似正确(PAC)分布学习框架下,利用浅层量子电路假设证明了无条件的量子优势。我们确定了一个有意义的生成式分布学习问题,其中使用单量子比特和双量子比特门的常数深度量子电路(QNC^0)优于常数深度有界扇入经典电路(NC^0)作为假设类。因此,我们证明了浅层量子电路相对于浅层经典电路的PAC分布学习分离。我们通过利用Bene Watts和Parham关于浅层电路采样任务的无条件量子优势的最新成果,将其提升到超平面学习问题,并确定非局域关联是量子优势的起源。