随机预言机下存在量子多项式可解、经典不可解的 NP 搜索问题

StefanoGogioso · x · 2026-11-10

Stefano Gogioso 指出,理解 Aaronson 与 Ambanis 争论的关键在于 Yamakawa 和 Zhandry 的论文《Verifiable Quantum Advantage without Structure》(arXiv:2204.02063):相对随机预言机,存在属于 FBQP(量子多项式时间可解)但不在 FBPP(经典概率多项式时间可解)中的 NP 搜索问题。这意味着存在对经典敌手是单向/抗碰撞、却容易被量子敌手求逆的函数;把随机预言机替换为具体的密码学哈希函数,即可得到 Minicrypt 下可信的实例化。被引用的补充说明:Yamakawa 与 Zhandry 还证明,对搜索型(而非判定型)问题,在相关设定下随机输入上也可获得指数级量子查询加速。