从比特到量子比特：计算模型的范式迁移

计算模型的变化往往不是“把旧机器加速一点”，而是改变了可表达的状态与可实现的变换的集合，从而改写了“什么问题在合理资源内可解”。经典计算从图灵机到布尔电路，本质上围绕着比特（bit）与确定性的逻辑演算展开；量子计算则引入量子比特（qubit）与复振幅，使“路径的相位相加”成为一种可编程资源。量子计算的优势因此并非来自更高主频的 CPU，而来自一种新的可达干涉结构：算法通过设计幺正演化，让错误路径的振幅相互抵消、正确路径的振幅相互增强，最终在测量这一随机过程上获得显著偏好。

1. 比特、布尔电路与“计算就是函数计算”

1.1 比特：离散信息的最小单元

经典比特只有两个取值：$0$ 与 $1$。在工程实现上可以是电压高低、磁畴方向或晶体管导通状态；在数学上它是集合 $\{0,1\}$ 的元素。一个 $n$ 比特寄存器的状态是长度为 $n$ 的比特串 $x\in\{0,1\}^n$。

经典确定性计算可抽象为函数： $$ f:\{0,1\}^n\to\{0,1\}^m $$ 算法就是在资源约束（时间/空间/电路规模）下实现所需的 $f$ 或近似版 $f$。

1.2 布尔电路：组合逻辑与可组合性

布尔电路由逻辑门（AND/OR/NOT 等）与连线组成。电路深度近似对应并行时间，电路规模（门数）近似对应运算量。一个重要特性是：一般布尔函数不可逆。例如 AND 门输入 $(0,1)$ 和 $(0,0)$ 都映射到 $0$，信息在映射中丢失。

这件事在经典计算里通常不显山露水，因为经典器件允许耗散，逻辑不可逆不阻止实现函数。但当我们进入量子世界时，“不可逆”将直接与物理可实现性冲突：封闭系统的量子演化必须是可逆的幺正变换。

1.3 一个对照：经典可逆计算并非噱头

经典计算也能被改写成可逆形式。典型例子是 Toffoli 门（受控受控非门，CCNOT），它在三比特上作用： $$ (a,b,c)\mapsto (a,b,c\oplus (a\land b)) $$ Toffoli 与 NOT 足以实现任意经典可逆电路；再结合“保留输入 + 写输出 + 清理辅助位（uncomputation）”的套路，可以把一般的不可逆计算嵌入到可逆计算中（代价是更多辅助位与额外门数）。这一点将在后续构造量子算术、量子 oracle 时反复出现：你会频繁看到“先算出来，再反算回去”，这不是形式主义，而是为保持整体幺正性付出的工程成本。

> 引申：Landauer 原理指出擦除 1 bit 信息在热力学上有最低能耗代价；可逆计算在理论上可以把能耗压到任意低。量子计算要求幺正可逆并不只是“数学洁癖”，它与物理的能量与信息守恒结构一致。

2. 从比特到量子比特：状态空间的跃迁

2.1 量子比特不是“概率比特”

直觉上，很多人把 qubit 误认为“同时是 0 和 1 的概率混合”。但 qubit 的关键差异在于它携带相位，并允许不同计算路径的振幅相干叠加。概率只能相加，而振幅（复数）先相加后取模平方，因而会出现增强与抵消。

一个单量子比特的纯态写作 $$ |\psi\rangle=\alpha|0\rangle+\beta|1\rangle,\quad \alpha,\beta\in\mathbb{C},\ |\alpha|^2+|\beta|^2=1. $$ 测量时输出 $0$ 的概率是 $|\alpha|^2$，输出 $1$ 的概率是 $|\beta|^2$。注意：$\alpha$、$\beta$ 本身不是概率，而是可干涉的复振幅。

2.2 向量表示：从“值”到“态矢”

在本书中默认使用计算基（computational basis）： $$ |0\rangle=\begin{pmatrix}1\\0\end{pmatrix},\quad |1\rangle=\begin{pmatrix}0\\1\end{pmatrix}. $$ 于是 $$ |\psi\rangle=\begin{pmatrix}\alpha\\\beta\end{pmatrix}. $$ 复数与线性代数并非装饰，它们是量子可编程性的核心：门操作是线性算子，组合门就是矩阵乘法，算法的“结构”体现在相位如何积累与相互抵消。

2.3 全局相位与物理等价

态矢整体乘一个相位 $e^{i\gamma}$ 不改变任何测量概率： $$ |\psi\rangle \sim e^{i\gamma}|\psi\rangle. $$ 这称为全局相位不可观测。但相对相位可观测，因为它影响干涉。例如 $$ \frac{|0\rangle+|1\rangle}{\sqrt2}\quad\text{与}\quad \frac{|0\rangle-|1\rangle}{\sqrt2} $$ 测量在计算基下概率相同，都是 $(1/2,1/2)$，但经过同一个门（如 Hadamard）后表现截然不同，这就是相对相位“可计算”的入口。

3. 测量：把量子态变成随机变量

3.1 Born 规则：概率来自模平方

对单比特在计算基上做投影测量，随机变量 $X\in\{0,1\}$ 满足： $$ \Pr[X=0]=|\alpha|^2,\quad \Pr[X=1]=|\beta|^2. $$ 测量后的态会塌缩到对应本征态（这里是 $|0\rangle$ 或 $|1\rangle$）。这意味着：你不能“直接读出 $\alpha,\beta$”，你只能通过重复制备同一态并多次测量来估计概率或期望值。

3.2 统计视角：用抽样估计概率与误差

若重复测量 $N$ 次，观察到 $1$ 的次数为 $k$，则经验概率 $$ \hat p=\frac{k}{N} $$ 在大样本下满足近似正态，其标准差（标准误）约为 $$ \mathrm{SE}(\hat p)\approx \sqrt{\frac{p(1-p)}{N}}. $$ 这解释了量子实验与量子算法里频繁出现的“shots”（采样次数）：测量是随机的，你需要用样本数换精度。后续我们会看到，很多量子算法的复杂度不只来自门数，还来自测量估计所需的样本数（如振幅估计、相位估计及其变体）。

4. 幺正演化：为什么量子门必须可逆

4.1 线性与范数守恒

封闭量子系统的演化由幺正矩阵 $U$ 描述： $$ |\psi'\rangle = U|\psi\rangle,\quad U^\dagger U=I. $$ 幺正性保证内积与范数守恒，从而保证总概率守恒。它也是“可逆”的数学表达：$U^{-1}=U^\dagger$。

与之对应，经典不可逆门（如 AND）无法直接成为量子门；要在量子电路里实现它，必须把它嵌入到更大维度的可逆变换中（例如用 Toffoli，并保留输入与辅助位）。

4.2 干涉的工程含义：让振幅相加而非概率相加

量子算法常被一句话概括为“并行探索所有路径”。更准确的说法是：量子态在希尔伯特空间中演化，算法设计的目标是让正确答案的振幅在终点处具有更大模长。关键在于相位控制——同样大小的振幅，如果相位相反会抵消，如果相位相同会叠加。

一个最小的干涉例子是 Hadamard 门 $H$： $$ H=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}. $$ 它满足 $H^2=I$。若从 $|0\rangle$ 出发： $$ |0\rangle \xrightarrow{H} \frac{|0\rangle+|1\rangle}{\sqrt2}\xrightarrow{H} |0\rangle. $$ 看起来像“做了两次随机化又回到确定态”，但这里没有随机：中间态并非概率混合，而是相干叠加，第二个 $H$ 利用相对相位把 $|1\rangle$ 路径抵消掉。经典随机比特做不到“随机后再确定地回到 0”。

5. 多比特：张量积与纠缠

5.1 张量积：状态空间指数扩张

两个量子比特的基是 $$ |00\rangle,|01\rangle,|10\rangle,|11\rangle $$ 一般态为 $$ |\psi\rangle=\sum_{x\in\{0,1\}^2}\alpha_x|x\rangle,\quad \sum_x|\alpha_x|^2=1. $$ $n$ 比特的态矢维度是 $2^n$，这意味着描述一般量子态需要指数数量的参数。量子计算的强大与困难都在这里：它能在指数维空间里做结构化的幺正变换，但我们只能通过测量读出有限信息。

5.2 纠缠：不能分解为局部态的乘积

若两比特态可写成 $$ |\psi\rangle=|\phi\rangle\otimes|\chi\rangle $$ 则称其为可分离（separable）。否则就是纠缠态。经典代表是 Bell 态： $$ |\Phi^+\rangle=\frac{|00\rangle+|11\rangle}{\sqrt2}. $$ 它无法写成单比特态的张量积。测量第一个比特得到 0 时，第二个必为 0；得到 1 时，第二个必为 1。这种关联不是经典“共享随机数”能完整模拟的（在更一般场景下会违反 Bell 不等式）。在量子算法与量子通信中，纠缠是资源：它允许非局部关联与更强的干涉结构。

6. 量子电路模型：门、线路图与通用性

6.1 量子门与常用记号

本书默认如下符号约定（纸书与电子版会沿用同一套，便于跨格式检索）：

• **态矢**：用 $|\cdot\rangle$（ket）表示列向量，用 $\langle\cdot|$（bra）表示其共轭转置。
• **计算基排序**：$|00\cdots 0\rangle$ 到 $|11\cdots 1\rangle$ 按二进制从小到大排序。
• **张量积顺序**：$|a\rangle\otimes|b\rangle$ 记作 $|ab\rangle$，左边是高位（更靠上/更靠左的量子线）。
• **电路时间方向**：从左到右；量子比特从上到下编号 $q_0,q_1,\dots$。

常用单比特门（矩阵形式）： $$ X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\ Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\ Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix},\ H=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}. $$ 相位门： $$ S=\begin{pmatrix}1&0\\0&i\end{pmatrix},\ T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}. $$

受控门以 CNOT 为代表，其作用是 $$ |a,b\rangle\mapsto|a,a\oplus b\rangle. $$

6.2 “通用门集”的意义

量子门集 $\mathcal{G}$ 若能（在给定精度 $\epsilon$ 下）逼近任意 $n$ 比特幺正变换，则称为通用。实践中常用的通用集合包括：

• $\{H,T,\mathrm{CNOT}\}$（离散门集，适合容错纠错框架）
• 所有单比特旋转 + CNOT（连续门集，适合理想化电路与编译）

通用性并不意味着“实现任意 $U$ 都高效”，只是保证“原则上能表达”。效率取决于编译开销与问题结构，这是量子算法设计的核心：用很少的门实现很强的干涉结构。

7. 三种量子计算模型：等价但工程侧重点不同

量子计算常见三种描述：

1. 量子电路模型（Quantum Circuit）：最主流，适合算法设计与复杂度分析。 2. 量子图灵机（Quantum Turing Machine, QTM）：更接近可计算性理论，用于证明“量子可计算”与复杂度类的性质。 3. 测量型量子计算（Measurement-Based Quantum Computing, MBQC）：先制备大规模纠缠资源态（如 cluster state），再通过自适应测量驱动计算，适合某些硬件架构与容错方案。

它们之间在多项式资源开销下是等价的：你可以把一个模型中的计算编译到另一个模型中。理解这一点的价值在于工程取舍：电路模型更便于描述门序列；MBQC 更强调“纠缠资源 + 测量脚本”；QTM 更适合做理论边界讨论。

```mermaid graph TD A[量子电路模型] -->|多项式开销编译| B[量子图灵机] B -->|多项式开销编译| C[测量型计算 MBQC] C -->|多项式开销编译| A ```

> 侧边栏（电子版可点开）：MBQC 的“自适应测量”本质上把门的选择延迟到测量结果出来之后，这种“经典控制 + 量子资源态”的混合编程方式，在后续讨论容错与编译时会再次出现。

8. Hello Quantum：单比特任意 Bloch 球旋转 + 重复测量估计概率

这一节的目标是给你一个可以立刻运行的最小实践：不依赖量子硬件与大型框架，用 Python + NumPy 写一个 1-qubit 模拟器，完成三件事： 1. 用旋转门 $R_x(\theta),R_y(\theta),R_z(\theta)$ 实现 Bloch 球上的任意旋转； 2. 从态矢计算测量概率； 3. 用重复测量（shots）估计概率，并给出统计误差量级。

8.1 Bloch 球参数化：任意单比特纯态

忽略全局相位后，任意单比特纯态都可写为 $$ |\psi(\theta,\phi)\rangle=\cos\frac{\theta}{2}|0\rangle+e^{i\phi}\sin\frac{\theta}{2}|1\rangle, \quad \theta\in[0,\pi],\ \phi\in[0,2\pi). $$ 这对应 Bloch 球上的一点：$\theta$ 是极角，$\phi$ 是方位角。

8.2 旋转门：用泡利矩阵生成幺正

定义（本书约定）： $$ R_x(\theta)=e^{-i\theta X/2},\ R_y(\theta)=e^{-i\theta Y/2},\ R_z(\theta)=e^{-i\theta Z/2}. $$ 它们的显式矩阵为： $$ R_x(\theta)= \begin{pmatrix} \cos\frac{\theta}{2} & -i\sin\frac{\theta}{2}\\ -i\sin\frac{\theta}{2} & \cos\frac{\theta}{2} \end{pmatrix}, $$ $$ R_y(\theta)= \begin{pmatrix} \cos\frac{\theta}{2} & -\sin\frac{\theta}{2}\\ \sin\frac{\theta}{2} & \cos\frac{\theta}{2} \end{pmatrix}, $$ $$ R_z(\theta)= \begin{pmatrix} e^{-i\theta/2} & 0\\ 0 & e^{i\theta/2} \end{pmatrix}. $$

一个重要事实（会在后续“编译与分解”章节细讲）是：任意单比特幺正（忽略全局相位）都可用 Euler 角分解： $$ U \equiv R_z(\alpha)R_y(\beta)R_z(\gamma). $$

8.3 可运行代码：状态演化与抽样测量

下面代码可直接保存为 `hello_quantum_1q.py` 运行（只需 `numpy`）。

```python import numpy as np

--- 基础对象：基态与常用门 ---

ket0 = np.array([1.0 + 0.0j, 0.0 + 0.0j]) ket1 = np.array([0.0 + 0.0j, 1.0 + 0.0j])

X = np.array([[0, 1], [1, 0]], dtype=complex) Y = np.array([[0, -1j], [1j, 0]], dtype=complex) Z = np.array([[1, 0], [0, -1]], dtype=complex)

def Rx(theta: float) -> np.ndarray: c = np.cos(theta / 2.0) s = np.sin(theta / 2.0) return np.array([[c, -1j * s], [-1j * s, c]], dtype=complex)

def Ry(theta: float) -> np.ndarray: c = np.cos(theta / 2.0) s = np.sin(theta / 2.0) return np.array([[c, -s], [s, c]], dtype=complex)

def Rz(theta: float) -> np.ndarray: return np.array([[np.exp(-1j * theta / 2.0), 0], [0, np.exp(1j * theta / 2.0)]], dtype=complex)

def normalize(state: np.ndarray) -> np.ndarray: norm = np.linalg.norm(state) if norm == 0: raise ValueError("Zero state") return state / norm

def probs_in_comp_basis(state: np.ndarray) -> tuple[float, float]: state = normalize(state) p0 = float(np.abs(state[0]) ** 2) p1 = float(np.abs(state[1]) ** 2)

数值误差修正

p0 = max(0.0, min(1.0, p0)) p1 = max(0.0, min(1.0, p1)) return p0, p1

def measure_comp_basis(state: np.ndarray, shots: int, rng=None) -> dict: if rng is None: rng = np.random.default_rng() p0, p1 = probs_in_comp_basi