量子计算擅长什么（又不擅长什么）

一份诚实的加速评分表

让我们先从整个领域里最重要的一句诚实话讲起：量子计算机不是一个能同时核对每个答案的魔法盒子。叠加态确实让许多可能性以振幅的形式同时存在，但你永远无法把它们全部读出来。当你测量时，你只会得到恰好一个结果，其概率由玻恩定则决定。量子算法的全部艺术，就在于安排干涉，让错误答案的振幅相互抵消，而正确答案的振幅增长——*然后*你才去测量。

正因如此，你能得到的加速完全取决于问题的结构，而不是量子比特的原始数量。并不存在一个统一的「量子快 X 倍」的数字。相反，大致可以分为三类：少数问题能获得指数级加速，更宽泛的一类能获得平方级（开平方）加速，而绝大多数问题根本得不到任何有用的加速。判断一个问题落入哪一类，正是「理解量子计算」的大部分含义所在。

PROBLEM TYPE              SPEEDUP            EXAMPLE
-------------------------------------------------------------
structured (periodicity)  exponential        factoring (Shor)
simulating quantum systems exponential*       chemistry, materials
unstructured search        quadratic (sqrt N) database-style search
linear algebra (special)   sometimes large    certain solvers (caveats)
general-purpose computing  none worth it      email, spreadsheets, web
-------------------------------------------------------------
* exponential in the right regime; a classical computer cannot
  efficiently simulate large quantum systems at all.

一份脚踏实地的评分表。一个问题落入哪一类，由它的结构决定，而不是由你拥有多少量子比特决定。

绝佳契合：因数分解、模拟、部分搜索

皇冠上的明珠是Shor 算法。它把因数分解重新表述为寻找周期，并利用量子傅里叶变换通过干涉提取出那个周期，从而以比任何已知经典方法都快指数级的速度分解大数。正是这一结果威胁到了 RSA 和 ECC——但前提是要存在一台大型的、带纠错的量子计算机，而这样的机器目前还不存在。

可能更重要的契合是模拟量子系统本身：分子、催化剂、材料、奇异物态。大自然本质上是量子的，因此经典计算机即便要追踪一个不算大的分子的量子态，也得付出指数级的代价。而量子计算机能够原生地表示这种状态。这正是费曼当初提出量子计算机的初衷，也是诸如 VQE 以及偏向优化的 QAOA 等近期方法的基础。

接下来是搜索。Grover 算法能在一个含 N 个元素的无结构列表中，用大约 sqrt(N) 步而非 N 步找到被标记的项，它借助振幅放大把概率往正确答案上「泵」。这是一个货真价实、可被证明的平方级加速——有价值、适用面广，却也经常被夸大。它并不能让你瞬间完成搜索，而且对许多实际任务来说，运行一台量子计算机的开销会把这点开平方的优势吃掉。

Grover, roughly:

  start:   every item equally likely  (flat amplitudes)
           |x0> |x1> |x2> ... |x*> ...   <- x* is the answer

  repeat ~sqrt(N) times:
     [oracle]  flip the sign of the answer's amplitude
     [diffuse] reflect all amplitudes about their average
               -> answer's amplitude grows, others shrink

  measure -> answer with high probability

  cost: ~sqrt(N) iterations, NOT 1, NOT log(N)

Grover 算法逐步放大正确答案的振幅。它是 sqrt(N)，一种平方级的胜利——而不是一次性的查表。

糟糕契合：大多数日常计算

现在说说诚实的坏消息：计算机每天所做的大部分事情得不到任何有用的量子加速。发邮件、渲染网页、运行电子表格、播放流媒体视频、为客户记录数据库提供服务、训练许多机器学习模型——这些任务要么用经典方法本就高效，要么缺乏量子算法所利用的那种特殊结构（比如隐藏的周期性）。对这些任务而言，量子计算机会比你已经拥有的笔记本电脑更慢、更贵，而且脆弱得多。

此外还有一项高昂的输入/输出税。许多被提出的量子加速都假定你的数据已经载入到了一个量子态中，而把大型经典数据集载入量子比特，其本身的代价就可能和加速所节省的一样多。最后的一次测量只会从一个概率分布中给你一个样本，而不是把里面的所有内容完整读出来。因此，即便核心数学运算更快，把数据送进去、把答案取出来的过程也可能把优势抹平。

量子计算机不是一颗更快的 CPU

有一个该删掉的思维模型：*「量子计算机就像我的 CPU，只是核心多得多。」*并非如此。一个经典核心执行的是许多快速、可靠、可自由复制的操作。量子比特则是另一种生物：它们的状态无法被复制（不可克隆定理），每一个门都必须是可逆的且幺正的，而读取一个量子比特会摧毁它的叠加态。你不是靠把普通指令分摊到更多核心上来编程量子计算机——你是在雕琢振幅，好让干涉揭示出答案。

而且今天的硬件确实脆弱。我们正处于 NISQ 时代——含噪中等规模量子（Noisy Intermediate-Scale Quantum）——在这个时代，量子比特会在微秒到毫秒的尺度上失去其状态（退相干，由 T1 和 T2 刻画），而且每一个门都带有误差。目前还没有大规模的容错量子计算机。像表面码这样的纠错在原理上能解决这个问题，但前提是误差要低于大约 1% 的阈值，且代价极其残酷：每一个可靠的逻辑量子比特需要数千个物理量子比特。正是这种开销，使得 Shor 规模的因数分解仍然要等上数年，而不是一件你买得到的产品。

WRONG picture:                CLOSER picture:

  CPU with 1000 cores           1000 fragile qubits
  -> 1000x more work            -> one carefully tuned
     done in parallel              interference pattern
  -> copy/inspect freely        -> can't copy (no-cloning)
  -> read anytime               -> measure once, state
                                   collapses, get 1 sample

量子计算机是一种不同种类的机器，而不是一颗涡轮增压的 CPU。「更多量子比特」并不等于「更多核心」。

批判地阅读炒作

现在你已经具备了足够的本事，能像怀疑者而不是粉丝那样去读量子计算的新闻标题。那少数几种套路一次又一次地出现，一旦你能把它们叫出名字来，炒作大多就自行瓦解了。目标并不是愤世嫉俗——量子计算是真实的，它在那些狭窄的胜利上确实令人振奋。目标是把狭窄而真实的胜利，与宽泛而虚幻的胜利区分开来。

「一次性尝试所有答案。」不对。叠加态持有许多振幅，但测量只返回一个结果；真正的功夫在于让干涉偏向正确的那一个。把这句话当作整篇文章其余部分的一个危险信号。
「对一切都快指数级。」不对。只有 Shor 类的有结构问题以及量子模拟才能获得指数级加速。Grover 式搜索是平方级的。大多数任务什么也得不到。
「我们有 N 个量子比特，所以它很强大。」要问质量，而不只是数量：门误差、相干时间、连通性，以及它们是含噪的物理量子比特还是经过纠错的逻辑量子比特。少数几个好的量子比特可以胜过许多糟糕的。
「量子如今就能破解一切加密。」不对。破解 RSA 需要一台尚不存在的大型容错机器，而后量子密码学（能抵抗量子攻击的经典算法）已经在部署中了。另外要注意，QKD 是一个独立的、基于物理的概念——它与后量子密码学并不是一回事。
「量子霸权意味着它有用。」未必。一次量子优势演示，可能只是在一个人为构造、毫无实际收益的基准测试上击败了经典机器。永远要问：到底对*什么*有用，又是与*最好的*经典方法相比？