量子霸权实现了吗？

周一 · 知古通今|周二 · 牧夫专栏

周三 · 太空探索|周四·观测指南

周五·深空探索|周六·茶余星话|周日·视频天象

作者：雷丰图、杨承霖

校对：牧夫天文校对组

后期：西藏老农民

责任编辑：王启儒

参考文献：

http://dx.doi.org/10.1137/S0097539795293172 https://arxiv.org/pdf/1703.07748v2

https://doi.org/10.1038/s41586-024-08449-y

什么是量子计算机

要理解量子计算机与经典计算机的差异，我们首先需要阐述量子比特（qubit）与经典比特（bit）之间的关系。

经典比特通过控制电流的变化来表示二进制信息，其中高电流代表“1”，低电流代表“0”。类似地，量子比特是通过控制电子、光子或中性原子等微观粒子的不同自由度（例如能级、偏振、位置等）来实现的，用以表示二进制信息。在微观尺度上，这些状态并不像经典比特那样是确定的“0”或“1”，而是处于“0”和“1”的叠加态。所谓的叠加态意味着在进行正交测量时，系统有一定概率坍缩为“0”或“1”。但由于量子测量的根本随机性，我们无法确定测量前量子比特的状态就是“0”或“1”。我们只能说，量子比特处于一种状态，其中包含“0”的概率为x%，而“1”的概率为y%。

因此，量子比特所能表示的信息是所有可能的“0”和“1”概率的线性组合，这与经典比特的两种确定状态形成了鲜明对比。

利用传统的0,1存储与量子比特的叠加态存储

Credit: 中科院半导体所

正是量子比特的这种独特性质，使得计算机科学家能够开发出一系列量子算法，这些算法能够解决那些对于传统计算机而言难以简化的复杂问题。例如，Shor算法将质因数分解问题的时间复杂度从指数级降低到多项式级，以及“九章”量子计算机在处理高斯玻色子取样问题时的卓越表现。在这些算法中，与我们日常生活联系最为紧密的当属Shor算法。

目前，全球广泛采用的加密技术是1977年提出的RSA加密算法，该算法基于选择两个大质数p和q，然后使用它们的乘积n作为公钥。传统计算机没有任何算法能够直接从乘积n推导出大质数p和q，加之RSA算法的加密过程极为复杂，这使得RSA算法被广泛应用于安全通信和数字签名等领域。

迄今为止，最快的经典质因数分解方法是通用数域筛法，其时间复杂度为指数级。而Shor算法在1996年的提出，将时间复杂度降至多项式级，极大地缩短了破解RSA加密所需的时间，从而对RSA加密的安全性构成威胁。

以中国的“九章”光量子计算机为例，它在处理5000万个样本的高斯玻色子取样问题时仅耗时200秒，而最快的传统计算机则需要6亿年。在其他优化或量子模拟场景中，量子算法相较于传统算法所展现出的巨大优势被称为“量子霸权”。能够实现这些算法的计算机被称为量子计算机。2000年，David P. DiVincenzo提出了广泛认可的量子计算机五原则，包括：

1. 拥有可控的量子比特，并具备可扩展性。

2. 能够将量子比特初始化到一个简单的量子态。

3. 能够在较长时间内保持量子相干性。

4. 能够执行通用的量子逻辑门操作。

5. 能够进行单量子比特的测量。

破解RSA加密的关键就在于破解私钥D，但随着D长度的增大，破解难度也会呈指数级上升，而现今的RSA使用的N长度通常为2048比特。经典算法破解需要极长的时间和算力。

Credit: 博客园MargoHu

挑战

既然量子算法在某些特定问题上展现出了对经典算法的压倒性优势，我们不禁要问，未来的计算机是否会完全被量子计算机所取代？从目前的发展趋势来看，量子计算机在大多数应用场景中还无法替代传统计算机，而且在日常生活中，使用传统计算机仍然是性价比最高的选择。

尽管Ethan Bernstein和Umesh Vazirani在理论上证明了量子图灵完备性——即存在一种量子图灵机能够有效地模拟任何其他可能的量子图灵机——但可编程量子计算机的实现仍然任重道远。更不用说，要建造一台能够实际运行Shor算法的量子计算机，目前看来还遥不可及。

当前主流的量子计算机根据量子比特的实现方式可以分为光子、超导、中性原子和离子阱等多种类型。遗憾的是，这些技术虽然各有优势——例如光子量子比特的长相干性、超导量子比特的易普适逻辑门——但也各自面临着难以克服的挑战——比如光子量子比特之间的纠缠困难、超导量子比特需要极低温度运行、离子阱量子比特的可靠性依赖于激光操控的精度等。这意味着，迄今为止，我们提到的五点原则还无法同时得到满足，满足其中任何一点都需要在其他性能上做出妥协。

Credit: 墨子沙龙Sheldon

前景

在2024年11月，谷歌宣布了其最新的超导量子芯片“Willow”，这款芯片拥有101个量子比特。尽管这款芯片本身并不代表量子计算机在计算能力上的新突破——与中国的“祖冲之三号”超导量子计算机的105个量子比特相比，Willow在量子比特数量上并不占优——谷歌的真正突破在于其应用于Willow的表面码技术，该技术成功突破了表面码阈值。表面码是一种通过n×n个物理量子比特来代表一个逻辑量子比特的编码方式，通过冗余设计实现对逻辑量子比特计算过程的纠错。如果表面码的错误率高于表面码阈值，意味着编码过程中“越纠越错”，即增加n会导致逻辑量子比特的错误率进一步提高。相反，低于表面码阈值的编码可以通过增加冗余（扩大n）来降低逻辑量子比特的错误率。因此，谷歌此次的成就在于量子纠错领域的质的飞跃，而非计算能力的量的提升。

那么，这一质的突破对我们有何影响？遗憾的是，在未来几十年内，我们可能还无法直接感受到其影响。以Shor算法为例，为了实际应用该算法进行大整数分解，需要将每个逻辑量子比特的错误率降低到远低于一万亿分之一。根据谷歌此次发布的表面码数据推测，至少需要1000个物理量子比特来构成一个逻辑量子比特才能达到这一错误率（破解RSA加密大致需要2万个逻辑量子比特）。这对于当前的超导技术而言，资源消耗是难以承受的。

既然量子计算在短期内无法取代通用计算机在我们日常生活中的地位，也无法立即重塑密码学领域，那么量子计算的发展是否还值得投入？答案是肯定的。抛开各种量子算法及其解决的复杂数学问题不谈，经典计算机在不久的将来也将面临量子力学的挑战。正如《三体：黑暗森林》中描述的，超级计算机的发展陷入停滞。在晶体管尺寸逼近纳米级别的今天，量子隧穿等量子效应将在10年内对这些接近微观尺寸的晶体管产生严重影响，引发各种计算问题。解决这些量子效应的干扰也是量子计算研究的重要课题之一。因此，尽管量子计算看似遥不可及，实际上它已经近在咫尺。

——The End——

『天文湿刻』 牧夫出品

微信公众号：astronomycn

NGC 2264 是一个由年龄在 100 万到 500 万之间的年轻恒星组成的星团。因其形状而得昵名 “圣诞树星团”。Image Credit: X-ray: NASA/CXC/SAO; Optical: Clow, M.; Image Processing: NASA/CXC/SAO/L. Frattare and K. Arcand

Credit: Daniel Korona

谢谢阅读