借用宇宙母机的算力（下）

作者先问量子机器适合什么任务。他借游戏红石电路说明：不必先解决世界本体问题，也可以利用已验证规律构造计算设备；但游戏比喻不能证明宇宙存在一台供我们调用的主机。

原书以找最大数、数独和旅行商引入 P、NP。输入规模 n 是描述问题所需的长度，不一定是问题的主观难度；线性时间 O(n) 本身就是多项式时间的一种，而不是比多项式时间更低的独立类别。多项式算法也可能因次数或常数很大而在实践中昂贵。

NP 表示‘是’实例的证据可被多项式时间验证，不是‘非多项式’的缩写，更不是已经证明求解都很慢。所有 P 判定问题也在 NP 中；P 是否等于 NP 是公开难题，不能把‘目前未找到快速算法’当作已经证明不可能。

作者用数独说明验证和寻找答案的不同。给定一个填好的棋盘，检查每行、每列与小格是否满足规则通常比自己从头构造答案直接；然而固定尺寸的普通数独只有有限多种题目。复杂度分类要先定义可随规模增长的广义数独版本。

旅行商问题问访问给定城市后回到起点的最短路线。若改成判定问题：是否存在长度不超过给定上限的路线？对于一般问题，该判定版本是 NP 完全问题；寻找最短路线是相应的优化问题。实际应用中的地图、距离关系和可接受误差会改变最适合的方法。

精确算法、近似算法和启发式各有用途：后者可很快给出有用路线，但一般不保证找到全局最短。NP 完全并不表示每个实例都难，也不表示已经证明所有经典或量子算法的最坏运行时间必然是指数。

书中让入侵者给蚂蚁编号，从许多入口同时找迷宫出口；若真有足够多蚂蚁和观察能力，能够缩短等待，却要付出并行资源。作者再把量子叠加比成无数蚂蚁，设想把所有答案一次跑完并直接找出正确入口。这个故事抓住了对多个可能性统一演化的直觉，却容易漏掉测量和搜索本身的成本。

量子算法需要设计可逆操作和干涉，让目标答案的概率被提高，再测量并验证；一次测量不会把所有分支的答案同时交出来。对具有唯一目标的无结构黑箱搜索，Grover 算法以大约 √N 次查询达到高成功概率，而经典黑箱搜索一般需要与 N 同阶的查询。这里的黑箱是能判断候选是否满足条件的操作，不是免费提供的解答。

例如 N=100 万时，平方根为 1000；这是查询数量级比较，具体常数、构造黑箱、量子门、纠错与输出验证仍要计入。它不是一步读遍所有入口，也不意味着所有 NP 问题都得到多项式时间算法。

原书以两个大质数相乘容易、从乘积找出因数困难为例，说明公开密钥密码中的不对称结构。困难程度依具体参数与最佳已知算法衡量，不是已经证明分解属于 NP 完全。RSA 与大整数分解有关；椭圆曲线体系常依赖离散对数难题。知道公钥并不等于知道私钥。

Shor 量子算法在理想可扩展容错模型中可高效处理整数分解及相关离散对数问题，因此足够强的量子机器将威胁相应公钥加密、密钥交换与数字签名。原书只把 Shor 写作针对 RSA 的算法，容易漏掉椭圆曲线离散对数；同时这不意味着所有密码和哈希都会以同样方式失效。

对称密钥搜索及哈希相关任务的量子攻击应分别分析；Grover 的平方根查询优势并非瞬间破解所有哈希，真实代价还取决于电路、并行与目标。NIST 于 2024 年公布 ML-KEM 等后量子密码标准，目标是抵御已知经典与量子攻击；标准化与部署迁移本身仍需时间和实际工程。

作者引用橡树岭 Frontier：2022 年 TOP500 报告其 HPL 基准约 1.102 EFlop/s，峰值约 1.686 EFlop/s。这是指定浮点基准与理论峰值，不是任意搜索或密码任务的通用速度；2022 的排名也不能当作今天的排行榜。

书中又提到 IBM 2023 年发布的 Condor 处理器有 1121 个超导物理量子比特。这是当时具体芯片的物理数量，并不等同 1121 个纠错后的逻辑比特，也不能单凭数量认定它在所有任务上最强。书中 2021 年设备表比较了不同平台的比特数、双比特门保真度和时间，是历史截面，而非同一条件下的完整性能排名。

Webber 等研究估算：在他们设定的表面码、1 微秒纠错周期、10 微秒反馈和 10⁻³ 物理门错误率下，一小时内攻击比特币使用的 256 位椭圆曲线签名相关难题约需 3.17 亿物理量子比特；同模型的一天时限约需 1300 万。它们是特定架构与时间目标的资源估算，不是所有硬件的必然下限，也不能由此精确预测哪一年发生。

原书担心量子态脆弱、环境干扰和纠错开销，这些是实际工程的重要问题。退相干通常指系统与环境关联后，局部可观察的相干受到抑制；它不等同于‘只要发生测量就解除所有纠缠并得到唯一结果’。设备还可能出现门操作、读出、泄漏和串扰等错误。

纠错把逻辑信息编码在多个物理比特的联合状态中，反复测量辅助信息以识别错误，再进行处理；这些中途测量不是直接读取并复制未知量子态。它们证明‘量子计算过程中绝不能测量’并不普遍。容错要求错误率、连接和纠错周期等条件，并消耗额外比特与时间。

门模型量子计算使用离散的逻辑步骤，物理控制可能依赖连续信号；模拟量子模拟器也是另一类架构。不能因控制信号连续就认定所有量子计算只是低精度模拟电路。经典数字计算同样有噪声、错误和纠错，只是所受限制及纠错方式不同。

作者用彩票山比喻人们对量子计算的期待，也提醒读者不要把每一次芯片比特数增加都当作实用突破。这个提醒有价值，但‘量子比特每增加一位，实际算力必然翻倍’并不成立：量子态空间的维度增长，并不保证能高效制备、利用并读出所需答案。

评价量子优势要固定任务、输入规模、精度、成功率和基准；比较应包含输入准备、算法门数、纠错、输出抽样及经典基准的改进。特定采样任务上的实验表现、可重复的科学计算优势和商业应用收益是不同主张，不能用一个替代另一个。

原书引述布雷默曼极限并给出 10⁹³ 的地球信息处理估算，这是基于特定质量、时间和物理假设的历史数量级推算，而不是已证明自然界的一切知识都不能超过这个数，也不是只有量子计算才受益或能接近它。理论界限与实际设备性能之间仍有很大距离。

原书设想利用量子计算模拟药物分子与人体蛋白质，进而缩短研发时间；也提到材料、物流、气候、金融和人工智能。这些是值得研究的问题，但药物能否安全有效还要经过实验、临床试验和监管，不能把分子模拟速度直接当作临床成功概率或寿命增长。

某些量子化学和材料模型与量子系统的表示天然相关，是重要研究方向；能否在某项任务取得可用优势仍取决于算法、误差、规模以及经典方法。类似地，量子机器学习的训练加速不能只凭比特数推断，数据装载、输出和模型训练成本都必须计算。

原书还推测大脑大量使用量子计算，以及量子 AI 轻易达到更大模型规模；这些并非该章提供的实验证据。把可能性与已实现成果分开，既能保留作者的期待，也能判断一项新闻究竟回答了什么问题。