1.3 量子优势的边界：防区画在哪里

1.3 量子优势的边界：防区画在哪里

本节摘要：量子优势不是全域的。本节把当前有证据、有争议、明确无望的三类区域画成一张边界图，用可运行的代码演示"平方加速遇上常数因子"的真实代价，并解释复杂性类 BQP 在整个版图中的位置，给后续章节一个共同的问题清单。

凌晨两点，采购委员会的一道难题

凌晨两点，一家材料研发公司的算力评审会上还在争论。团队申请预算接入云量子计算平台，理由是"要模拟催化剂分子的电子结构"；财务顾问反对，理由是"同样的活，经典集群便宜一千倍"。双方都在说事实，分歧在于他们用的是同一张地图——而这张地图上其实画着泾渭分明的防区：有些问题量子机器有结构性优势，有些问题量子机器与经典机器打平，还有些问题量子机器明显更糟（你得先把脆弱的量子态准备出来，这本身就昂贵）。会开到天亮也没有结论，因为没人把边界画出来。本节就来做这件事。

一、复杂性类：给地形分级

要把边界画准，得用复杂性理论的语言。经典侧，P 是经典计算机多项式时间可解的问题集，BPP 是允许小概率出错的随机算法版 P；量子侧，BQP（有界错误量子多项式时间）是量子计算机多项式时间可解、错误率可压到任意小的问题集。几个关键判断是领域共识：P 包含于 BQP，因为量子机可以模拟经典机，量子计算至少不比经典差；BQP 与 NP 的关系未知，主流猜想是既不包含也不被包含——也就是说，量子计算大概率不能解决全部 NP 完全问题，旅行商、背包这类问题在量子机上仍然没有一般性的高效解法。

这一点值得展开，因为它是最常见的误区。叠加给了"同时尝试所有答案"的表象，但测量只给一次抽样，提取答案必须靠干涉结构，而干涉结构只在问题的代数性质与傅里叶类变换对得上号时才能搭出来。肖尔算法成功，正因为分解在数学上等价于求周期，而求周期有量子傅里叶变换这把现成的钥匙；布尔满足性问题没有这种周期结构可利用，格罗弗算法只能提供平方根级别的通用加速——从指数时间降到指数的平方根，仍然不可用。

图 1-3：量子优势防区边界图

二、演练：平方加速的真实折扣

格罗弗算法把无结构搜索从 n 次查询降到平方根量级，听起来干脆利落。但量子门的操作成本比经典指令高几个数量级，优势要扣除这笔常数折扣之后还剩多少，决定了它何时可用。下面的演算把这笔账算给你看。

# grover_breakeven.py：平方加速在门成本折扣下的盈亏平衡点
import math

def classical_queries(n: int) -> int:
    return n  # 无结构搜索：平均查一半，最坏查完

def grover_queries(n: int) -> int:
    # 迭代次数约为 pi/4 * sqrt(n)，每次迭代代价约等于数次经典查询的等效能耗
    return math.ceil(math.pi / 4 * math.sqrt(n))

def breakeven(n: int, qubit_gate_penalty: float) -> float:
    """qubit_gate_penalty：一次量子门相对一次经典操作的代价倍数"""
    return classical_queries(n) / (grover_queries(n) * qubit_gate_penalty)

print(f"{'条目数':>10} {'经典查询':>10} {'格罗弗迭代':>10} {'百倍代价下比值':>14}")
for n in [1_000, 1_000_000, 10**9, 10**12, 10**15]:
    ratio = breakeven(n, 100.0)
    print(f"{n:>12} {classical_queries(n):>12} {grover_queries(n):>12} {ratio:>16.1f}")
​

输出显示：数据库里只有一百万条记录时，即使不考虑纠错开销，百倍门代价也把平方加速吃得干干净净；条目数到千万亿量级，比值才勉强回本。结论不是格罗弗算法没用，而是它的用武之地在"搜索空间巨大、且无法建索引"的场景——比如破解密钥（密钥空间是人为做到巨大的）而非查询业务数据库。演示优势实验走的正是这条路：2019 年悬铃木芯片的随机线路采样、2020 年光量子体系的高斯玻色采样，都是刻意挑选"经典模拟极难、量子制备可行"的窄任务，证明了物理原理，但不构成实用优势。把演示当成应用，是采购会上常见的第二类错误。

三、四类优势问题的清单与现状

把学界共识收拢成一张表，后续章节会反复引用它。

读这张表要带着两个提醒。其一，"当前状态"一列区分了原理优势与工程可行：分解问题的指数加速早在 1994 年就被证明，但需要数百万物理比特的容错机才能威胁真实的密钥长度——原理与工程之间隔着整个第 4 章。其二，模拟问题排第一不是偶然：它不需要你把经典难题硬塞进量子框架，量子态的态空间天然就是问题的解空间，防区与地形重合，这是第 6 章把它列为头号战果区的底层原因。

四、把边界图带回你的工作

回到开头那场凌晨两点的争论，现在可以给出评审结论的框架了。问题落在防区一（材料分子模拟正是如此）：值得立项，但要按第 4、6 章的路线图预期时间尺度，近期目标是积累算法与人才，不是立刻省钱。问题落在防区二：先做经典启发式算法的极限测算，确认经典方法真的撞墙，再谈量子方案，且预算里要给误差缓解留出大头（第 5 章会解释为什么）。问题在防区外：直接否掉，这是对预算负责。

这套判断框架不需要你记住任何具体算法的名字，只需要记住边界的画法：看问题的代数结构是否与量子干涉对得上号，看加速的量级是否扛得住门操作的成本折扣。下一章我们转入敌情剖析——在把任何问题送上量子机之前，先搞清楚退相干是如何一步步吃掉你的态的。

本节要点回顾

• BQP 的位置：包含 P、与 NP 的关系未知，量子计算不是万能加速器，NP 完全问题没有已知的一般量子解法。
• 干涉决定一切：加速来自算法搭出的干涉结构，而非"同时尝试所有答案"的表象。
• 平方加速要打折：门操作常数代价可以吃掉格罗弗式优势，搜索空间不够大就不回本。
• 演示不等于应用：优越性实验是刻意挑选的窄任务，证明了物理，未证明商业价值。
• 边界判据：代数结构对不对得上、加速量级扛不扛得住折扣，这两问即可完成立项初筛。