量子科技中心_量科网

单向函数（OWFs）的存在构成了经典密码学中最基本的前提假设。然而在量子密码学中，这种基础性却未必成立[Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]。[Khurana and Tomer 2024]提出的单向谜题（OWPuzzs）为OWFs提供了自然的量子对应物。OWPuzzs的存在意味着PP ≠ BQP[Cavalar等，2025]，但其逆命题仍悬而未决。在经典密码学中，对应问题——能否从P ≠ NP构造出OWFs——是最核心的开放性问题之一，学界长期从学习困难度的视角进行研究。各类学习框架（包括PAC学习）的困难度都与OWFs存在或P ≠ NP相关联。相较之下，此前OWPuzzs始终缺乏类似的特征描述。 该研究团队在本论文中首次基于成熟学习模型——分布学习的困难度——建立了OWPuzzs的完整特征描述。具体而言，研究人员证明：当且仅当规范量子分布学习在平均情况下具有困难性时，OWPuzzs才会存在。由此自然引出的问题是：规范量子分布学习的最坏情况困难度能否从PP ≠ BQP推导获得？若成立且实现规范量子分布学习中从最坏情况到平均情况的困难度归约，则将单凭PP ≠ BQP即可推出OWPuzzs！然而该工作表明，肯定回答该问题将极其困难：若规范量子分布学习的最坏情况困难度具有PP-hard性质（在黑箱归约条件下），则仅需多项式时间层次结构的无限性即可推出SampBQP ≠ SampBPP——这将解决量子优势领域长期悬而未决的难题。 尽管如此，该团队证明PP ≠ BQP等价于另一种经典且被深入研究的学习困难度概念——不可知学习。研究表明：PP ≠ BQP当且仅当基于KL散度的不可知量子分布学习具有困难性。作为副产品，该工作还获得了一个关于量子优势的有趣推论：证明针对PPTΣ₃P学习者的统计距离不可知量子分布学习困难性，可推出SampBQP ≠ SampBPP。这是首次从学习理论标准自然框架的困难度假设出发，构建出基于采样的量子优势。更重要的是，不可知学习的困难性属于最坏情况类型，因此该成果成为首个完全基于最坏情况困难度假设构建的采样量子优势范例。