文章总结： 本文系统阐述量子算法复杂度分析的基础框架，重点比较量子与经典算法在查询复杂度、时间复杂度等维度的差异。核心观点指出量子优势的本质在于资源增长规律的不同，而非绝对速度提升。文章通过Deutsch、Simon、Grover、Shor等算法案例，说明量子计算在特定结构化问题中可实现指数级加速，但无法解决所有NP问题。关键结论强调算法评估需统一标准（如黑盒查询次数），并澄清常见误解。 综合评分： 85 文章分类： 技术标准,量子计算,算法分析,计算复杂度

---

【量子计算】计算复杂度基础：为量子算法建立统一赛场

原创

Litt1eQ Litt1eQ

Coder小Q

2026年4月27日 08:30 山东

在小说阅读器读本章

去阅读

【量子计算】计算复杂度基础：为量子算法建立统一赛场

上一节我们已经看到，量子计算并不是把  台经典计算机并排摆在一起，而是把信息编码进叠加态、相位和干涉里。可是一旦真正进入量子算法，马上就会遇到一个更根本的问题：量子算法“更快”，这个“更快”到底是怎么算的？

如果不先把这个问题说清楚，后面的 Deutsch 算法、Grover 算法、Shor 算法就很容易被混成一句模糊的话：“量子计算机很厉害。”但这句话几乎没有信息量。节省 1 次查询、把  次搜索降到  次、把亚指数时间降到多项式时间，这三件事都叫“更快”，可它们的意义完全不同。[1][2]

这一篇的任务，就是先把比赛规则讲清楚。我们会建立三层语言：

1. 用时间复杂度描述“随着输入规模增大，算法会变慢到什么程度”；
2. 用查询复杂度描述“在量子算法里，怎样把经典和量子放到同一个赛场上比较”；
3. 用这些语言给 Part 4 画一张地图，知道 Deutsch、Simon、Grover、Shor 各自到底快在哪里。

贯穿整篇的基本原则可以浓缩成一句话：

❝

算法的难易，主要看输入规模变大时资源如何增长；而在量子算法里，最常用的统一货币，是调用黑盒的次数。

0. 先看目的地：量子算法到底在比什么

初学者最常见的三个误解，几乎都和“比赛规则”没有先讲清楚有关。

第一个误解是：“量子计算机一次能同时算出  个答案，所以当然快。” 这句话只说对了一半。叠加态确实能把许多输入一起送进同一个量子电路，但测量时你只能读出一个结果。真正有用的，不是“一次读出全部答案”，而是把许多函数值编码进相位，再用干涉提取某个整体性质。

第二个误解是：“量子计算机比经典计算机快  倍。” 这句话连问题都没说清楚。脱离具体任务，谈“快多少”没有意义。搜索问题、因数分解问题、函数判定问题，用的不是同一种加速。

第三个误解是：“量子计算机能解决所有经典困难问题。” 这也不对。Grover 算法确实能加速无结构搜索，但它把  降到的是 ，仍然是指数时间。量子计算带来巨大改观的，是某些带结构的问题，而不是一切困难问题。

因此，正确的问题不是“量子计算机有多神”，而是：

❝

对某个具体问题，量子算法比最好的经典算法究竟少用了什么资源？

在 Part 4 里，我们会反复遇到下面几种对比：

| 问题 | 经典资源 | 量子资源 | 这说明了什么 | | — | — | — | — | | Deutsch（） | 2 次查询 | 1 次查询 | 最小规模的量子查询优势 | | Deutsch-Jozsa（精确判定） | 次查询 | 1 次查询 | 干涉可以制造极强的精确分离 | | Simon | 指数级查询 | 多项式级查询 | 结构化问题上的真正指数优势 | | Grover 搜索 | 次查询 | 次查询 | 无结构搜索只能拿到平方根加速 | | Shor 因数分解 | 已知最好经典算法为亚指数时间 | 量子多项式时间 | 结构性问题可以出现现实重要的巨大加速 |

值得注意的是，Deutsch-Jozsa 的“ 次对  次”说的是经典确定性最坏情况。如果允许经典随机算法带极小错误概率，Deutsch-Jozsa 可以用常数次抽样解决。[1] 这件事并没有削弱它的历史地位，反而提醒我们：比较算法之前，必须先把比较标准说清楚。

这一点和量子计算关系极大。因为从下一篇开始，我们不只是要看电路长什么样，还要看它到底在什么意义上更快。

1. 算法的快慢，不看这一次跑了几秒

1.1 翻电话簿：增长趋势才是关键

假设你要在一本电话簿里找某个人的名字。

如果电话簿是乱序的，你最直接的办法只能是从头往后翻。最坏情况下，要翻完整本，也就是大约  次检查。这叫线性搜索，复杂度是 。

如果电话簿已经按姓名排好序，方法就完全不同了。你可以先翻到中间，看目标名字在字母序里应该在前半本还是后半本；这样每看一次，搜索范围都会缩小一半。最坏情况下，只需要大约  次检查。这就是二分搜索，复杂度是 。

拿具体数字看会更直观：

• 当  时，线性搜索最坏要看  条，二分搜索只要  次左右；
• 当  时，线性搜索最坏要看一百多万条，二分搜索也只要  次左右。

问题规模增加了  倍，线性搜索的工作量也几乎增加了  倍；而二分搜索只多看了大约  次。算法的差距，不是从第一步就决定性的，而是随着规模增大被越拉越开。

这就是复杂度分析的出发点：

❝

我们关心的不是某一次运行花了几秒，而是输入规模变大时，所需步骤会按什么规律增长。

1.2 “输入规模”到底是什么

这里还要补一个很重要的细节：输入规模并不总是“那个数本身有多大”。

如果问题是“给定整数 ，判断它是否有非平凡因子”，那么输入给算法的不是一个抽象的“巨大的 ”，而是一串比特。一个十进制数有多难处理，关键不在于它数值上有多大，而在于要写下它需要多少位。

例如：

• 数字  的二进制写法是 ，需要  位；
• 数字 ，二进制写法需要  位。

所以当我们说“Shor 算法对输入长度是多项式时间”时，这里的输入长度通常指的是表示整数所需的比特数，也就是大约 ，而不是整数  的数值本身。[2][7]

这个区分在量子算法里尤其关键。因为一旦说不清“规模”是什么，就会把“对  多项式”和“对  多项式”混为一谈，而这两者差了整整一个指数。

1.3 为什么不用“秒”来衡量

如果我们只说“这个程序跑了 0.3 秒”，其实什么本质信息都没有说明。原因很简单：

• 不同机器的主频不同；
• 同一台机器换了更好的实现，常数项就会变化；
• 过几年硬件升级，绝对秒数还会整体下降。

复杂度分析故意把这些机器细节先压下去，只保留最稳定的部分：增长趋势。

这和量子计算的关系也很直接。量子算法真正声称的，不是“量子门比 CPU 指令更快”，而是“当输入规模增大时，所需资源的增长规律不同”。如果增长律不同，优势会随着规模扩大而被放大；如果增长律相同，只是常数稍好，那就只是工程优化，不是复杂度意义上的突破。

2. 大  符号：忽略枝节，抓住增长律

2.1 大  想保留什么，想忽略什么

大  符号的核心思想很简单：

❝

当  足够大时，算法的步骤数主要由最高增长阶决定。

例如：

• 和  都写作 ；
• 写作 ；
• 也仍然是 。

它故意忽略三类东西：

1. 常数系数；
2. 低次项；
3. 机器与实现细节。

不是因为这些东西永远不重要，而是因为当  真的很大时，它们往往决定不了问题的命运。决定命运的是增长阶。

2.2 常见复杂度放到同一张表里

下面这张表最值得反复看。为方便比较， 默认取 。

| 复杂度 | | | | | | — | — | — | — | — | | | 3.3 | 6.6 | 10.0 | 19.9 | | | 10 | 100 | 1000 | | | | 33 | 664 | 9966 | | | | 100 | | | | | | 1024 | | 约 | 大到没有实际意义 |

这张表里最重要的分界线，是多项式时间和指数时间。

如果一个算法需要 、、，哪怕规模增大后会变慢，它至少还在“可以靠更好的算法和更快的机器继续推进”的范围里。 如果一个算法需要  或 ，那么规模每增加一点点，代价都会暴涨得非常快。

当  时， 只有 ，而  已经是  量级。这里不是“稍微慢一点”，而是“一个还可以想办法跑，一个已经完全脱离现实”。

换句话说：

❝

多项式和指数的差别，不是速度快慢的差别，而是“问题规模还能不能继续扩展”的差别。

2.3 为什么计算机快 1000 倍，也救不了指数时间

很多初学者会说：指数时间虽然大，但硬件不是一直在进步吗？ 问题在于，硬件提升对不同增长律的帮助完全不一样。

假设你有一台机器，最多能承受  步操作。对于两种算法：

• 若算法复杂度是 ，那么它最多能处理大约 ；
• 若算法复杂度是 ，那么它最多能处理大约 。

现在机器快了  倍，可以承受  步：

• 对  来说，可处理规模变成 ；
• 对  来说，可处理规模只变成 。

从  提到 ，听起来也增长了 50%，但别忘了这是指数问题里的输入长度。对很多实际任务来说，新增这  位规模并不能改变“依然不可做”的本质。

这和量子计算的主线关系非常紧。我们后面关心的，不是量子电路把常数优化了多少，而是它有没有把增长律从“本来不可做”改成“规模扩大后仍能做”。

3. 从“能算出来”到“能很快验证”：P 与 NP

3.1 为什么复杂度类通常谈判定问题

复杂度理论最常把问题写成“是/否”形式，这叫判定问题（decision problem）。

比如：

• “这个整数是偶数吗？”
• “这张图里从 A 到 B 有路径吗？”
• “这个布尔公式有满足它的赋值吗？”

这么做不是因为理论家只关心“是/否”，而是因为很多搜索问题、优化问题，都可以先翻译成判定问题。例如旅行商问题可以先问：“是否存在一条总长度不超过  的路线？” SAT 直接就是一个判定问题。

3.2 P：经典计算机能高效解决的问题

如果一个判定问题可以由经典确定性算法在多项式时间内解决，我们就说它属于 P 类（Polynomial time）。[2]

一些直观的例子是：

• 判断偶数：只看最低位；
• 判断一个列表是否已排序：逐一比较相邻元素，复杂度 ；
• 判断图中是否有路径：宽度优先搜索可在多项式时间内完成；
• 判断一个数是否为素数：今天我们已知它属于 P。[9]

P 的直觉含义不是“瞬间算完”，而是“随着规模增大，代价按多项式增长”。

3.3 NP：候选答案可以快速验证的问题

NP 类（Nondeterministic Polynomial time）的直觉是：

❝

也许“找到答案”很难，但如果有人把候选答案递给你，你可以在多项式时间内检查它对不对。

一个具体例子是“给定整数 ，它是否有非平凡因子？” 把它写成判定问题后，就可以清楚地区分“找”和“验”。

例如取 。

• 如果你自己去找因子，可能要试很多除数；
• 但如果有人告诉你“试试 ”，你只需要检查  是否整除。

算一下就知道：

于是“ 有非平凡因子吗？”这个判定问题，至少满足“答案给你以后，验证很快”。

这正是 NP 的直觉来源：验证容易，不代表寻找也容易。[2]

3.4 P 与 NP 的关系，为什么会这么重要

P 中的任何问题也都在 NP 里。理由很直接：如果你本来就能很快算出答案，那么把这个答案再检查一遍，只会更容易。

于是问题变成：

❝

会不会所有“容易验证”的问题，其实也都“容易求解”？

这就是著名的  vs  问题。绝大多数计算机科学家都相信 ，但直到今天仍然没有严格证明。[2]

在 NP 中，还有一批特别重要的问题，叫 NP 完全（NP-complete）问题。它们可以粗略理解为“NP 里最难的代表”。SAT、3-SAT、旅行商问题的判定版，都是经典例子。

这一步和量子计算有什么关系？关系在于：当人们问“量子计算机能不能解决所有难题”时，真正想问的通常不是“能不能做快一点”，而是“能不能把 NP 完全问题也压到多项式时间”。这正是后面第 6 节要回答的边界问题。

4. 查询复杂度：量子算法最常用的统一货币

4.1 为什么不能直接拿“运行时间”硬比

如果我们只看普通时间复杂度，经典算法和量子算法并不总是容易放到同一把尺子上。

原因可以直接分成三点：

• 经典算法的基本操作是读写 bit、做布尔运算；
• 量子算法的基本操作是量子门、叠加、纠缠和测量；
• 一个量子门到底应该折算成多少“经典步骤”，并没有天然统一的答案。

所以量子算法理论里，最常用的做法不是直接比“总时间”，而是先把问题提炼成“你必须向某个函数问多少次问题”。这个模型叫查询复杂度（query complexity），也叫 oracle 模型。[1][4]

4.2 黑盒：我们只数“问了多少次”

把某个函数  想成一个密封的黑盒。你不知道它内部怎么实现，只能把输入  塞进去，再拿到输出 。

如果你的目标是判断这个函数属于哪一类，或者找出它的某个性质，那么一个自然的问题就是：最少要问这个黑盒几次？

这件事有两个好处：

1. 它把经典和量子都拉到了同一个赛场；
2. 它很适合证明下界，也就是“再聪明也不能少于这么多次”。

在这个框架里，“更快”就有了很明确的含义：为了得到答案，量子算法是否能更少地调用黑盒。

4.3 量子黑盒为什么不是简单的“把答案写出来”

量子 oracle 最容易写错的地方，是把它想成“无论第二个寄存器里原来放了什么，都直接把它改写成函数值”

这看起来很自然：我把输入寄存器放在第一格，把函数值写到第二格，不就行了吗？

问题在于，量子演化必须是可逆的，也就是必须由幺正变换给出。上面这种写法通常不是一一对应的。例如如果 ，那么

两个不同输入被压成同一个输出，这就不可逆了，也不可能是合法的量子门。

正确的量子 oracle 写法是：[1][3]

这里的  是异或。第二个寄存器不是被“覆盖”，而是被“按  控制翻转”。这样就保住了可逆性。

Part 3 已经在叠加态上跑过这个 oracle，结论可以直接搬过来：当输入处于叠加时，一次查询就会把所有  的值一起编码进量子态。比如对恒等函数 ，

编码进量子态并不等于能把所有函数值直接读出来：测量仍然只会给出一个经典结果。量子算法真正利用的是上一章推导过的相位反冲——把辅助位取为  时，oracle 会把  变成前面的正负号 ，于是函数信息进入了振幅而不是某个寄存器。一次 oracle 调用等于“在相位里并行写下  的整张表”，这正是查询复杂度里量子方与经典方能真正分出胜负的地方；下一篇的 Deutsch 算法，就是这张表被一次读成全局性质的最小案例。

4.4 查询复杂度里常见的三种“正确”

讲到这里，还需要把“正确答案”分成三种常见标准：

• 确定性查询复杂度：要求算法每次都 100% 正确；
• 随机查询复杂度：允许经典随机算法带一个很小的错误概率；
• 有界误差量子查询复杂度：允许量子算法以至少  的成功率给出正确答案，这一成功率还可以通过重复运行进一步放大。[1][4]

这也是为什么描述量子优势时，必须连比较标准一起说。 Deutsch-Jozsa 对经典确定性算法有指数级优势；Simon 对经典有界误差查询算法仍有指数级优势；Grover 则是在有界误差模型下，把无结构搜索从  次降到  次。[3][6][8]

5. Part 4 的地图：量子加速并不只有一种

有了前面的语言，现在就能更精确地看 Part 4 的路线了。后面的几篇文章虽然都属于“量子算法”，但它们解决的问题、加速来源和现实意义并不相同。

5.1 Deutsch：最小规模的查询优势

Deutsch 问题只有一个输入比特。经典算法若想确定无误地区分常数函数和平衡函数，必须查询两次；量子算法只要一次。[1]

这个优势很小，却非常重要。因为它第一次严格证明了：量子算法确实可能比经典算法少问问题。

5.2 Deutsch-Jozsa：干涉制造出的精确分离

把 Deutsch 推广到  位后，经典确定性最坏情况需要  次查询，而量子算法仍然只要一次。[3]

不过这里必须保留刚才说过的那句修正：如果允许经典随机算法以很小概率出错，那么经典只需常数次抽样就能高概率区分常数和平衡。[1] 因此 Deutsch-Jozsa 的主要价值，不是“现实中把经典完全碾压”，而是让我们第一次清楚看见：相位编码加干涉，真的能把一个全局性质压缩进一次查询。

5.3 Simon：真正重要的指数级查询优势

Simon 问题比 Deutsch-Jozsa 更接近后来的 Shor。它不是只做一次查询就结束，而是量子部分和经典后处理结合，最终在有界误差查询复杂度意义下实现了从指数到多项式的分离。[4][8]

这也是为什么很多教材都会把 Simon 看成“Shor 的前奏”：这里第一次出现了“隐藏结构可以被量子干涉高效揭示”这条主线。

5.4 Grover：无结构搜索的平方根加速

Grover 处理的是最朴素也最顽固的问题：在  个候选项里找出满足条件的一个，但没有额外结构可以利用。

经典最坏情况下要问  次；Grover 只需  次。[6]

这已经非常厉害。例如：

• 时，经典大约要查一百万次，Grover 只要一千次；
• 时，经典要查一万亿次，Grover 只要一百万次。

但它仍然不是把问题从指数时间变成多项式时间。更重要的是，Grover 的平方根优势在 oracle 模型下已经是最优的，不可能再普遍提升到对数级或常数级。[5]

5.5 Shor：结构性问题上的现实级突破

Shor 算法和前面几篇最大的不同，是它不只是 oracle 模型里的漂亮分离，而是一个针对现实重要问题的完整多项式时间量子算法。[7]

它之所以能做到这一点，不是因为“量子可以暴力并行枚举所有因子”，而是因为因数分解背后隐藏着周期结构，而量子傅里叶变换可以高效提取这种结构。 也就是说，Shor 的成功不是无结构搜索的成功，而是结构性利用的成功。

这张地图的意义在于：以后你看到“量子优势”这四个字时，应该先问一句“是哪一种优势”。只有这样，才不会把“少一次查询”和“把密码学基石打穿”混成同一个概念。

6. 量子计算机能解决 NP 完全问题吗

6.1 BQP：量子多项式时间的边界

如果一个判定问题可以由量子算法在多项式时间内解决，并且成功概率至少保持在 ，我们就说它属于 BQP（Bounded-error Quantum Polynomial time）。[1][4]

可以把 BQP 粗略理解为“量子计算机现实可高效解决的问题集合”。

至少有两件事是清楚的：

• 经典多项式时间问题当然也都能在量子计算机上做，所以 ；
• Shor 说明，BQP 至少包含像整数分解、离散对数这样目前尚无已知经典多项式时间算法的问题。[7]

但更关键的问题是：BQP 和 NP 完全问题之间到底是什么关系？这个问题今天仍然没有定论。

6.2 Grover 能把 NP 完全问题变简单吗

最常见的想法是：SAT 有  个布尔赋值，经典暴力枚举需要  次，那量子不是可以用 Grover 把它降到  吗？

是的，但这里最容易产生一个错觉：指数的一半，仍然是指数。

拿  举例：

• 经典暴力搜索需要  次；
• Grover 之后需要  次。

后者当然小得多，可仍然大到无法实施。假设每步只要  纳秒， 步也大约需要  年，远远超过宇宙年龄。

所以 Grover 带来的核心结论不是“NP 完全问题被解决了”，而是：

❝

对无结构搜索，量子可以把指数底数显著压低，但无法把指数增长直接改造成多项式增长。

这件事对密码学有现实意义。例如对穷举密钥搜索，平方根加速会迫使人们把密钥长度加倍来维持安全边际；但它并不意味着“所有组合爆炸问题都会突然变得容易”。

6.3 为什么大多数人并不期待量子能解决 NP 完全

到目前为止，量子算法最深刻的成功几乎都有一个共同特征：它们抓住了某种特殊结构。

• Deutsch 与 Deutsch-Jozsa 利用的是相位干涉；
• Simon 利用的是隐藏异或结构；
• Shor 利用的是周期结构与傅里叶分析。

而 NP 完全问题最顽固的地方，恰恰在于它们看起来缺少一个统一、可被量子算法普遍榨取的结构。 如果你只能把问题看成“在巨大的候选空间里找一个好答案”，那么 Grover 的平方根加速基本已经把 oracle 模型里能拿到的普适收益榨干了。[5]

因此，主流看法并不是“量子一定能解决 NP 完全”，而是“如果没有额外结构，量子大概率也救不了它们”。 但这里必须诚实地停在“主流看法”上，而不能说成定理：目前没有证明表明 NP 完全问题一定不在 BQP 中。

这也是为什么学习量子算法时，既要看到它的力量，也要看到它的边界。真正严肃的说法从来不是“量子万能”，而是“量子能把某些结构性问题的复杂度改写，但不会自动消灭一切组合爆炸”。

7. 总结：把复杂度语言翻译回量子计算

这一篇表面上在讲复杂度理论，实际上是在给后面的量子算法准备一把统一尺子。

可以把本文压缩成下面四句话：

1. 算法好坏主要看增长趋势，不看某一次运行花了几秒；
2. 大  关心的是最高增长阶，其中最重要的分界是多项式与指数；
3. 查询复杂度把“调用黑盒的次数”当成统一货币，是比较经典与量子算法的标准赛场；
4. 量子优势有不同层次：有的只是小规模查询优势，有的是平方根加速，有的则是像 Shor 那样改写整类问题的可计算性边界。

一句话收尾：

❝

量子算法的优势，不是“同时算完一切”，而是把问题结构写进相位与干涉，从而在正确的复杂度模型里减少所需资源。

下一篇我们就来看这条主线上的第一个具体例子：Deutsch 算法。它的问题规模极小，却把后面整条量子算法路线的骨架都浓缩进去了。你会看到，上一节讲过的相位反冲，并不是一个孤立技巧，而正是“少问一次黑盒”这件事的数学核心。

参考资料

1. Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2010.
2. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
3. David Deutsch and Richard Jozsa, “Rapid Solution of Problems by Quantum Computation,” Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439(1907), 553-558 (1992). https://doi.org/10.1098/rspa.1992.0167
4. Ethan Bernstein and Umesh Vazirani, “Quantum Complexity Theory,” SIAM Journal on Computing 26(5), 1411-1473 (1997). https://doi.org/10.1137/S0097539796300921
5. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani, “Strengths and Weaknesses of Quantum Computing,” SIAM Journal on Computing 26(5), 1510-1523 (1997). https://doi.org/10.1137/S0097539796300933
6. Lov K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 212-219 (1996). https://doi.org/10.1145/237814.237866
7. Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing 26(5), 1484-1509 (1997). https://doi.org/10.1137/S0097539795293172
8. Daniel R. Simon, “On the Power of Quantum Computation,” SIAM Journal on Computing 26(5), 1474-1483 (1997). https://doi.org/10.1137/S0097539796298637
9. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, “PRIMES is in P,” Annals of Mathematics 160(2), 781-793 (2004). https://doi.org/10.4007/annals.2004.160.781

---

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：Coder小Q Litt1eQ Litt1eQ《【量子计算】计算复杂度基础：为量子算法建立统一赛场》