量子科技中心_量科网

该研究团队首次证明了量子算法在高效证明搜索中的计算难度下限。研究表明，基于标准格密码学假设"带错误学习"(LWE)问题，任何量子算法都无法弱自动化𝖳𝖢⁰-Frege证明系统。这一成果拓展了[KP98](《信息与计算》1998)、[BPR00](《SIAM计算期刊》2000)以及Bonet、Domingo、Gavaldà、Maciel和Pitassi(《计算复杂性》2004)的研究脉络——前人已证明若RSA加密体系或Diffie-Hellman密钥交换协议安全，则经典算法分别无法弱自动化Extended Frege、𝖳𝖢⁰-Frege和𝖠𝖢⁰-Frege系统。据研究人员所知，这是量子计算与命题逻辑证明搜索领域的首次交叉研究成果。