复杂度类 BQP：量子到底能算哪些经典算不了

前情提要：第 10 篇《量子优势到底是什么》里，我们口语地说"在少数具体任务上，量子确实超越了经典"。但"超越"到底落在哪类问题？计算机科学家用几个互相套着的"圈"，把这件事说得一清二楚。这一篇，就画那张家谱。

一、钩子：问题也分"难易族"

别只问"量子快不快"，要先问"对哪类问题"。计算机科学把问题按"求解所需资源"分进不同的复杂度类——就像生物按门纲目科属种归类。看清量子计算机站在哪个"圈"里，才知道它到底能撬动什么。

二、四个最该认识的圈

• P：确定性图灵机在多项式时间内保证算出的问题。比如"两点间最短路径""两个数相乘"。这是"容易"的基准线。
• BPP：允许随机掷硬币、答案以高概率正确的一类。现实里大量算法（比如随机抽样、蒙特卡洛）都在这。经典计算机的实际能力，大体对应 BPP。
• NP：给你一个"答案候选"，能快速验证它对不对的问题。比如"数独有没有解""旅行商有没有更短路线"。注意 NP 问的是"验证快"，不是"求解快"——求解可能极慢。一个世纪级悬案：P 是否等于 NP，至今没人证明。
• BQP：有界错误量子多项式时间——量子计算机在多项式时间里，以高概率算对的问题集合。这是"量子能高效干的"的严格定义。

三、它们怎么套：一条包含链

这四个圈不是平铺的，而是层层包含：

直觉上：P 包含于 BPP（随机不会让简单问题变难），BPP 包含于 BQP（经典随机算法是量子算法的特例，把量子比特只取 0 和 1 就退化成经典随机），BQP 包含于 PSPACE（量子线路每一步都可被经典地用足够空间模拟，只是慢）。

四、关键澄清：BQP 不包住 NP

这里是最容易被误导的地方。既然 Shor 能分解大数、Grover 能加速搜索，是不是量子能解决所有 NP 难题？不是。

目前没有证据表明 BQP 包含 NP，更没有证明 NP 包含于 BQP。像旅行商最优解、数独求解这类 NP 完全问题，量子计算机没有已知的多项式时间算法。Grover 只是把搜索从 N 步降到根号 N 步——是二次加速，不是"指数级通关"。回到第 8 篇《Grover：在干草堆里快速找针》：它快，但远没到"秒杀 NP"的程度。

五、量子边界：能算哪些、不能算哪些

把家谱翻译成人话：

• 量子稳赢经典的：因子分解（第 9 篇 Shor）、离散对数、某些隐藏子群问题——这些有指数级加速，且确实落在 BQP 而大概率不在 BPP 里。
• 量子有中等加速的：无序搜索（Grover，根号 N）、某些组合优化。
• 量子帮不上忙的：所有 P 类问题本就快，量子不会更快；NP 完全问题目前没有量子捷径。
• 更上层：BQP 之上还有 PSPACE、甚至 EXP（指数时间）——那些是量子也"算不动"的更大世界。

所以"量子优势"的准确说法是：它把一部分原本在 BPP 之外（或极慢）的问题，拉进了 BQP 的高效区，而不是把整个计算版图翻个底朝天。

六、小结与预告

这一篇，给第 10 篇的"优势"安了张严格的家谱：

• 四个圈 P 包含于 BPP 包含于 BQP 包含于 PSPACE，量子能力对应 BQP；
• BQP 不包 NP：因子分解、搜索有加速，但旅行商这类 NP 完全问题没有已知量子捷径；
• 量子优势 = 把一部分难题拉进 BQP 高效区，不是推翻整个计算版图。

既然量子的"能算"边界清楚了，下一个自然问题是：这些加速里，哪些已经能跑在真机上、哪些还卡在噪声里？这正是第 11 篇《量子纠错：给易碎的量子打补丁》要接着拆的——而下一篇，我们就去拆那套"拿很多护一个"的数学骨架。

下次见。