量子101（Shor's algorithm）

经典比特：一个确定的开关#

经典计算机里，信息的最小单位是比特（bit），它只有两个取值：0 或 1。可以把它想成一个电灯开关，任一时刻要么开、要么关，不存在中间状态。一个字节是 8 个比特，能表示 $2^8=256$ 种确定的组合，但在任一瞬间它只处于其中一种。

叠加：量子比特可以处于「中间状态」#

量子计算的最小单位是量子比特（qubit）。它同样有两个基本状态，记作 $|0\rangle$ 和 $|1\rangle$（这个尖括号记号后面会解释），但它还可以处于两者的叠加（superposition）：一种同时含有 $|0\rangle$ 成分和 $|1\rangle$ 成分的状态。

叠加不是「不知道它是 0 还是 1」这种主观的无知，而是一种客观存在的物理状态。一个常用的类比是旋转中的硬币：当它高速旋转时，问「现在是正面还是反面」没有意义——它处在一种正反交织的状态里，直到落定的那一刻才成为确定的一面。真实的量子比特比硬币更彻底：叠加是它真正的状态，而不只是我们看不清。

经典比特和量子比特的区别可以并排来看：前者永远落在 0 或 1 两个点上，后者可以处在连接这两点的整个「状态空间」中的任意位置。

测量：一看就「坍缩」#

叠加带来一个反直觉的后果：无法直接读出叠加态的全部信息。对量子比特做测量（measurement），结果只会是 0 或 1 两者之一，绝不会读到「一半 0 一半 1」。测量还会不可逆地改变状态本身——原本的叠加瞬间坍缩（collapse）成测到的那个确定值，之前的叠加信息就此丢失。

关键在于，测到 0 还是 1 是概率性的。叠加态里 $|0\rangle$ 和 $|1\rangle$ 各自成分的大小，决定了测到对应结果的概率。旋转的硬币落定时是正是反带有随机性，量子测量与之相似，只是这种随机性是量子力学内在的，而非源于我们的信息不足。

纠缠：两个量子比特的强关联#

当两个量子比特发生纠缠（entanglement）时，它们的状态无法再被分开描述，只能作为一个整体来刻画。最典型的例子是这样一种两比特态：测量结果要么同时是 00，要么同时是 11，各占一半，而且永远不会出现 01 或 10。

这意味着：单独看每一个比特，测量结果都是随机的 0 或 1；但只要测了其中一个，另一个的结果就被瞬间确定了。哪怕把两个纠缠的粒子分隔到很远，这种关联依然存在。需要强调的是，这并不能用来超光速传递信息——因为每一方看到的都只是随机结果，只有事后把两边的记录对照起来，才能发现它们完全相关。纠缠是量子计算区别于经典计算的核心资源之一。

量子比特用什么做成#

量子比特不是抽象概念，而要用真实的量子系统来承载，只要这个系统有两个可区分的量子态即可。常见的物理实现包括：

• 超导电路：把超导回路中的电流状态当作 $|0\rangle$ 和 $|1\rangle$，是目前 IBM、Google 等公司的主流路线，需要在接近绝对零度的环境下工作。
• 囚禁离子：用电磁场把离子悬在真空中，以其能级作为量子态，用激光操控。
• 光子：用光的偏振方向（比如水平/垂直）编码量子比特。

不同实现各有优劣，但对上层的算法而言，它们都抽象成同一个数学对象——一个量子比特。本文不深入硬件细节。

澄清一个常见误解#

一种流行的说法是「量子计算机能同时尝试所有可能的答案，所以快」。这句话既对又危险。对的部分是：$n$ 个量子比特的叠加态确实能同时包含 $2^n$ 种可能。危险的部分是：测量只会随机塌缩到其中一种，无法把这 $2^n$ 个答案一次全读出来——如果算法只是「把所有答案叠加起来然后测量」，得到的和随机猜没有区别。

量子加速的真正来源不是「并行尝试」，而是干涉（interference）：通过精心设计的操作，让错误答案对应的概率相互抵消、正确答案对应的概率相互增强，最后测量时大概率读到正确答案。这一点是理解肖尔算法的钥匙，后面会反复回到它。

需要的数学：复数、向量、概率#

• 复数：形如 $a+bi$，其中 $i^2=-1$。量子态的成分是复数，复数的模平方 $|a+bi|^2 = a^2+b^2$ 会用来算概率。
• 向量与内积：量子态就是向量，量子门就是作用在向量上的矩阵。会算矩阵乘向量就够了。
• 概率：一组非负数加起来等于 1。测量各结果的概率满足这个约束。

用向量表示量子比特：狄拉克符号#

量子力学用狄拉克符号（Dirac notation）书写量子态，一个态写成 $|\psi\rangle$，读作「ket psi」。两个基本状态就是两个正交的单位向量：

一个一般的单量子比特态是它们的线性组合：

其中 $\alpha,\beta$ 是复数，称为概率幅（probability amplitude，简称振幅）。它们必须满足归一化条件：

概率幅与测量#

测量这个态时，得到 0 的概率是 $|\alpha|^2$，得到 1 的概率是 $|\beta|^2$。归一化条件保证这两个概率加起来正好是 1。

举例来说，$|\psi\rangle = \tfrac{1}{\sqrt{2}}|0\rangle + \tfrac{1}{\sqrt{2}}|1\rangle$ 是一个均匀叠加态：$|\alpha|^2 = |\beta|^2 = \tfrac{1}{2}$，测量时各有一半概率得到 0 或 1。这个态很重要，通常记作 $|+\rangle$。

振幅是复数而非普通概率，这一点至关重要。概率永远非负，无法相互抵消；而复数振幅有正负、有相位，可以相加成更大，也可以相消为零。这正是干涉的数学基础。

布洛赫球：把量子态画在球面上#

单量子比特的状态可以完全画在一个球面上，这就是布洛赫球（Bloch sphere）。任意单比特纯态都能写成：

其中 $\theta$（0 到 $\pi$）和 $\varphi$（0 到 $2\pi$）恰好是球面上一点的两个角度坐标。于是：

• 北极是 $|0\rangle$，南极是 $|1\rangle$。
• 赤道上的点都是 $|0\rangle$ 和 $|1\rangle$ 各占一半的均匀叠加态，只是相位 $\varphi$ 不同，比如 $|+\rangle$ 和 $|-\rangle$。
• 从北极到南极的连续变化，对应叠加中 $|1\rangle$ 成分从 0 增加到 1。

布洛赫球把抽象的复数振幅变成了一个直观的几何对象：一个量子比特的状态就是球面上的一个箭头，而后面要讲的量子门，作用就是让这个箭头在球面上转动。下面的动画展示了几个典型状态在球面上的位置，以及门操作如何让它旋转。

需要注意，布洛赫球只能表示单个量子比特。一旦涉及多个比特（尤其是纠缠），这个简单的几何图像就不够用了。

多个量子比特：维度的指数爆炸#

$n$ 个量子比特的状态生活在一个 $2^n$ 维的复向量空间里。两个比特的基是四个状态 $|00\rangle, |01\rangle, |10\rangle, |11\rangle$，一般态是它们的叠加：

需要四个复数振幅来描述。三个比特需要 8 个，$n$ 个比特需要 $2^n$ 个。这个指数增长是量子计算潜力的根源：仅仅 300 个量子比特，其状态空间的维度就超过了可观测宇宙中的原子总数，经典计算机根本无法逐一存储这些振幅。多个基本状态组合的方式，用的是向量的张量积（tensor product），记作 $\otimes$，但入门阶段只需记住维度按 $2^n$ 增长即可。

纠缠态的数学#

有了多比特记号，就能精确写出前面提到的纠缠态，它叫贝尔态（Bell state）：

它只有 $|00\rangle$ 和 $|11\rangle$ 两个成分，各占一半，所以测量必然得到 00 或 11。它的关键特征是无法被拆成两个单比特态的乘积——你找不到 $|\psi_A\rangle$ 和 $|\psi_B\rangle$ 使得 $|\Phi^+\rangle = |\psi_A\rangle \otimes |\psi_B\rangle$。不可分解正是纠缠的数学定义。相反，$\tfrac{1}{\sqrt 2}(|00\rangle+|01\rangle)$ 就可以分解成 $|0\rangle\otimes\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)$，因此它不是纠缠态。

量子门是作用在态上的旋转#

量子门就是作用在状态向量上的矩阵。但不是任意矩阵——它必须是幺正矩阵（unitary matrix，满足 $U^\dagger U = I$）。幺正的物理意义是：它保持向量长度不变，因而始终维持归一化条件 $|\alpha|^2+|\beta|^2=1$。在布洛赫球上，幺正操作恰好对应球面上的旋转：门不改变箭头的长度，只改变它的方向。

幺正还有一个直接后果：量子门可逆。每个量子门都有对应的逆操作，把状态转回去。这和经典的与门、或门不同（它们会丢信息、不可逆）。

常见的单量子比特门#

• X 门（对应经典的 NOT）：交换 $|0\rangle$ 和 $|1\rangle$。

• Z 门（相位翻转）：给 $|1\rangle$ 加一个负号，$|0\rangle$ 不变。它在布洛赫球上是绕竖轴旋转。

• 阿达马门（Hadamard，简称 H 门）：制造叠加，是量子算法里最常用的门。

它把确定态变成均匀叠加态：

注意 $H|1\rangle$ 里那个负号：$|+\rangle$ 和 $|-\rangle$ 测量结果的概率完全一样（都是 50/50），区别只在相位。这个看不见的相位差，正是干涉能否发生的关键。

多比特门：CNOT 与纠缠#

单比特门无法制造纠缠，需要能让两个比特相互作用的门。最基本的是受控非门（CNOT，controlled-NOT）：它有一个控制比特和一个目标比特，当控制比特是 $|1\rangle$ 时翻转目标比特，是 $|0\rangle$ 时什么都不做。

CNOT 加上前面的 H 门，就足以制造贝尔态：先用 H 把控制比特变成叠加，再用 CNOT 把这份叠加「传染」给目标比特，两个比特就纠缠在一起了。

量子线路#

一段量子程序通常画成量子线路（quantum circuit）：每条横线代表一个量子比特随时间的演化（从左到右），线上的方块是依次作用的门，末端的表盘符号表示测量。制造贝尔态的线路如下。

从左到右读：两个比特都从 $|0\rangle$ 出发；H 门把第一个比特变成 $|+\rangle$；CNOT 以第一个比特为控制、第二个为目标，产生纠缠；最后测量两个比特，得到的结果高度相关——要么 00，要么 11。

干涉：量子算法真正的引擎#

回到前面强调的干涉。因为振幅是带符号（更一般地，带相位）的复数，同一个结果可以通过不同路径到达，这些路径的振幅会叠加：同号的相互增强（相长干涉，constructive），异号的相互抵消（相消干涉，destructive）。

设计良好的量子算法，会安排让所有「错误答案」的路径振幅相互抵消、趋近于零，而「正确答案」的路径振幅相互增强。这样最终测量时，读到正确答案的概率被放大。下面的动画用两个振幅箭头演示相长与相消：方向一致时合成箭头更长（概率更大），方向相反时相互抵消（概率趋零）。

这解释了为什么量子计算不是「同时算所有答案」那么简单：真正的技巧在于用干涉把噪声消掉、把信号留下。

用 Qiskit 写第一个量子程序#

上面的概念可以直接写成代码。Qiskit 是 IBM 开源的量子编程框架，用 Python 描述量子线路，并能在本地模拟器或真实量子硬件上运行。

先看一个最小的叠加例子：一个量子比特，做 H 门，再测量。

1
from qiskit import QuantumCircuit, transpile
2
from qiskit_aer import AerSimulator
3

4
qc = QuantumCircuit(1, 1)   # 1 个量子比特，1 个经典比特存测量结果
5
qc.h(0)                     # 对第 0 个比特做 Hadamard，制造均匀叠加
6
qc.measure(0, 0)            # 测量，把结果写进经典比特
7

8
sim = AerSimulator()
9
qc = transpile(qc, sim)
10
counts = sim.run(qc, shots=1024).result().get_counts()
11
print(counts)   # 约 {'0': 512, '1': 512}：一半 0、一半 1

运行 1024 次（每次叫一个 shot），大约一半得到 0、一半得到 1，正好对应 $|+\rangle$ 态 50/50 的测量概率。

把它扩展成贝尔态，只要加一个比特和一个 CNOT。

1
from qiskit import QuantumCircuit, transpile
2
from qiskit_aer import AerSimulator
3

4
qc = QuantumCircuit(2, 2)
5
qc.h(0)                     # 第 0 个比特进入叠加
6
qc.cx(0, 1)                 # CNOT：控制位 0，目标位 1 —— 制造纠缠
7
qc.measure([0, 1], [0, 1])
8

9
sim = AerSimulator()
10
qc = transpile(qc, sim)
11
counts = sim.run(qc, shots=1024).result().get_counts()
12
print(counts)   # 约 {'00': 512, '11': 512}，几乎没有 '01' 和 '10'

结果只有 00 和 11、各占一半，这正是纠缠的实验特征：两个比特单独看都是随机的，但永远一致。量子编程的思维方式由此可见一斑——你不是在写「if-else」式的逐步指令，而是在设计一段幺正演化 + 一次测量，让想要的结果以高概率出现。

问题：大整数分解与 RSA#

把两个大素数相乘很容易，但反过来，给定它们的乘积去还原这两个素数（整数分解），却极其困难。今天广泛使用的 RSA 公钥加密正是建立在这个不对称之上：公钥是一个大合数 $N$（几百位十进制数），只有知道它的素因子才能解密。已知最好的经典算法（一般数域筛法，GNFS）是亚指数时间的，分解一个 2048 位的 $N$ 需要的时间长到实际不可行。整个互联网的安全，某种程度上依赖于「没人能快速分解大数」这个假设。

肖尔算法打破了这个假设。

核心思想：把「分解」变成「找周期」#

肖尔算法最关键的一步，是把「分解 $N$」这个看似孤立的难题，归约成一个「找周期」的问题——而找周期恰好是量子计算擅长的。

具体做法：随机选一个与 $N$ 互素的整数 $a$，考察函数

这个函数是周期性的：存在一个最小的正整数 $r$（称为 $a$ 模 $N$ 的阶，即周期），使得 $a^r \equiv 1 \pmod N$，之后 $f$ 的取值就开始循环。一旦求出这个周期 $r$，在满足条件时就能用初中就学过的最大公约数算法（辗转相除法）算出 $N$ 的因子。

为什么找到周期就能分解？如果 $r$ 是偶数，那么 $a^r - 1 = (a^{r/2}-1)(a^{r/2}+1)$ 能被 $N$ 整除。只要 $a^{r/2} \not\equiv \pm 1 \pmod N$，那么 $\gcd(a^{r/2}-1,\ N)$ 和 $\gcd(a^{r/2}+1,\ N)$ 就是 $N$ 的非平凡因子。（如果 $r$ 是奇数或不满足条件，换一个 $a$ 重试即可，成功概率很高。）

一个具体的例子：分解 15#

取 $N=15$，随机选 $a=7$。计算 $f(x)=7^x \bmod 15$：

取值序列 $1,7,4,13,1,7,4,13,\dots$ 每 4 步循环一次，所以周期 $r=4$。

$r=4$ 是偶数，$a^{r/2}=7^2=49\equiv 4 \pmod{15}$，且 $4 \not\equiv \pm 1$。于是：

得到 $15 = 3 \times 5$。分解完成。这里的关键观察是：整个过程里唯一「难」的一步，是求出周期 $r$；其余都是经典的、快速的算术。

量子部分：用傅立叶变换「听出」周期#

经典地找周期 $r$ 并不比直接分解容易——你可能要逐个试很多 $x$。量子计算机的做法完全不同，它一步到位地利用了叠加和干涉：

1. 叠加：用一排 H 门，把输入寄存器制备成所有 $x$ 的均匀叠加，即一次性「装入」全部输入。
2. 一次计算填满全表：对这个叠加态整体计算 $f(x)=a^x \bmod N$，结果是一个把每个 $x$ 和对应 $f(x)$ 关联起来的巨大叠加态。这一步利用了量子并行，但正如前面强调的，此时还不能直接读出任何有用信息。
3. 量子傅立叶变换（quantum Fourier transform，QFT）：这是画龙点睛的一步。QFT 是一种利用干涉提取「频率」的操作，作用在上述叠加态上时，会让振幅集中到与周期 $r$ 相关的特定位置——所有与周期不匹配的成分相互抵消（相消干涉），匹配的成分相互增强（相长干涉）。
4. 测量：此时测量输入寄存器，以高概率得到一个与 $1/r$ 相关的数值；再用经典的连分数算法处理它，就能还原出周期 $r$。

一个恰当的比喻：$f(x)$ 像一段含有固定节拍的声音，QFT 就像人耳（或频谱分析仪），它不去听每个瞬间的音符，而是直接「听出」整段声音的节拍频率。周期信息本来弥散在整个叠加态里，QFT 通过干涉把它汇聚成一个可测量的尖峰。

整体流程#

肖尔算法是一个量子—经典混合算法：绝大部分是经典的预处理和后处理，只有「找周期」这一段核心子程序跑在量子计算机上。

复杂度与意义#

肖尔算法的时间复杂度约为 $O\big((\log N)^3\big)$，即关于输入位数的多项式时间；而最好的经典算法是亚指数时间的。这不是常数倍的提升，而是复杂度量级的根本改变：让原本需要天文数字年份才能完成的分解，理论上缩短到可行的时间。

这直接威胁到 RSA、以及同样依赖类似数学难题的 Diffie–Hellman、椭圆曲线密码。一旦大规模容错量子计算机成为现实，今天绝大部分公钥加密都将被攻破。正因如此，密码学界正在推进后量子密码（post-quantum cryptography）：设计一些即使面对量子计算机也依然难解的新算法来替代现有方案。

现实的距离：NISQ 与纠错#

需要泼一盆冷水：肖尔算法在原理上成立，但要用它分解 RSA-2048 这种真正有威胁的大数，需要成千上万个高质量的逻辑量子比特，稳定运行足够长的时间。而现实中的量子比特极其脆弱，容易受环境噪声干扰而退相干（decoherence），使叠加和纠缠在计算完成前就崩溃。

我们目前处在所谓的 NISQ 时代（Noisy Intermediate-Scale Quantum，含噪中等规模量子），拥有几十到几百个物理量子比特，但错误率高、无法长时间维持。要得到一个可靠的逻辑量子比特，需要用大量物理量子比特通过量子纠错（quantum error correction）来构造，开销巨大。因此，用肖尔算法真正分解 RSA-2048，业界普遍认为还有相当长的路要走。已有的演示（如分解 15、21 这类小数）验证了算法的正确性，但离实用规模还很遥远。