BQP：量子计算机到底能解什么

一台量子计算机造得再大，也解不了停机问题。这不是工程差距，是计算模型的边界：量子计算机与图灵机算得出同样的东西，差别只在要多少步。

一张包含关系，不是一条直线

把判定问题按所需资源分类，量子计算机对应 BQP：存在量子线路，在多项式步内给出答案，并且答错的概率有界。经典的对应物是 P 与 BPP。

已知的包含关系是 P ⊆ BPP ⊆ BQP ⊆ PSPACE。最后一步值得多看一眼：量子线路的振幅可以在多项式空间内算出来（沿计算路径求和，时间指数级），所以量子能算的不会超出多项式空间。NP 是「答案能快速验证」的问题；NP ⊆ PSPACE，但 NP 与 BQP 谁包含谁，两个方向都没有证明。这张图上的几条边，其实是问号。

加速是相对的

说「量子加速」，先得说清跟谁比。Shor 算法 的快，是相对于已知最好的经典分解算法；Grover 算法 给的是平方级加速——查询次数从 N 降到 √N，运行时间也同样按 √N 次神谕调用增长，不是指数级加速。换一个更强的经典基线，倍数就会缩水。

判断一个任务有没有可能加速，可以问三个问题。第一，最好的经典算法有多好？如果经典已经是多项式，量子多半拿不到指数优势。第二，问题里有没有量子能吃下的结构？已知的加速来源很集中：周期与相位、干涉、局域哈密顿量的演化。第三，数据怎么进去、答案怎么出来？读入 n 比特要 n 步，一次测量只给一个采样；瓶颈若在输入输出，量子部分再快也没用。

这三个问题不能保证加速，只能帮你排掉明显不成立的说法。