量子加速边界澄清:Aaronson-Ambainis 猜想并不限制 Shor 类超多项式加速

thomasahle · x · 2026-11-07

一条科普表述称,Scott Aaronson 和 Andris Ambainis 把「量子计算机何时能多项式级快于经典计算机」的问题关联到一个关于多项式的猜想:除非输入满足特殊条件(如 Shor 算法中的指数结构),否则量子机至多多项式加速。thomasahle 指出这种说法有点好笑:Aaronson-Ambainis 的含义是经典算法对输入函数的查询次数至多多项式级,但对因数分解而言读入输入本身就只需线性时间,AA 猜想并没有对计算本身的超多项式量子加速给出任何限制。