第一章 量子计算简介 · 人话版

导读

这一章是整本书的"项目 README"：先告诉你量子计算到底想干什么，再把核心数据类型（qubit）和操作（量子门、测量、线路）摆出来，最后用隐形传态和 Deutsch 算法两个"Hello World"演示量子凭什么可能比经典快。作为程序员，你该关心的是：这里的"叠加""纠缠""测量"不是玄学，而是一套可以用复向量、矩阵乘法、概率采样精确描述的计算模型——它扩展了你对"什么是一次计算"的认知边界。读完你会有一套把量子术语翻译成线性代数 + 概率的速查心智模型。

1.1 量子计算和量子信息简介

量子计算就是利用量子系统的几个反直觉特性来处理信息：态可以线性叠加、测量是概率性的、信息以"概率幅"的形式藏着不易直接读取、比特之间能纠缠（非定域关联）、整个系统对环境极其敏感（退相干）。这一节是全景导览，顺带把"可计算性"和"复杂性"这两个 CS 老朋友请出来，引出全书的核心悬念：量子到底比经典强不强。

🧠 类比： 经典比特是一个 bool，量子比特更像一个带权重的概率分布对象，但权重是复数、而且在你 read() 它之前会按特定规则演化。整章都在讲这个"奇怪的数据类型"的 API。

丘奇-图灵论题说的是：图灵机能算的，就是"凭直觉认为能行可计算"的全部——它不是定理，而是一条至今没被推翻的工程经验。关键点在于 $\lambda$ 演算、图灵机这些独立设计的计算模型最后被证明等价。

🧠 类比： 这就像 Python、Lisp、汇编虽然语法天差地别，但计算能力等价（都图灵完备）。不同的人从不同方向造模型，最后殊途同归，这才让人相信"可计算"这个概念是稳的。

复杂性版的丘奇-图灵论题更强硬：它不只问"能不能算"，还问"能不能高效算"。经典版断言概率图灵机能高效模拟任何现实计算模型；量子版则把主角换成量子图灵机。这里埋了一个全书最大的悬念——$\mathrm{BPP} \subsetneq \mathrm{BQP}$ 是否成立。

💡 人话： BPP = 经典电脑（允许抛硬币）能在多项式时间搞定的问题集合；BQP = 量子电脑能在多项式时间搞定的集合。问题是：BQP 是不是严格比 BPP 大？如果是，就说明量子真有经典做不到的快活。

⚠️ 坑： "若证明 BPP $\subsetneq$ BQP，丘奇-图灵论题就被推翻了"——这话只对复杂性版论题成立。原始论题只关心"能不能算"（可计算性），不关心快慢，所以不受影响。别把两个版本搞混。

发展简史里值得记的节点：1980s Feynman 提出用量子机模拟量子系统；1984 BB84 量子密钥分发；1985 Deutsch 算法；1994 Shor 算法（因数分解进了 BQP）；1996 Grover 搜索算法。

🔑 记住： 量子的"威力"来自叠加 + 纠缠 + 干涉三者合力，而不是"同时跑很多份"的朴素并行——这个误解后面 1.4 会专门拆。

1.2 量子比特

qubit 是量子信息的"基本数据类型"。它不是 0 或 1，而是 $\ket{0}$ 和 $\ket{1}$ 这两个基向量的复数线性组合，并且要求总概率归一。

$$\ket{\psi} = \alpha\ket{0} + \beta\ket{1}, \qquad \lvert\alpha\rvert^2 + \lvert\beta\rvert^2 = 1$$

逐项翻译：$\ket{\psi}$ 是这个 qubit 的状态（一个二维复向量）；$\ket{0}$、$\ket{1}$ 是计算基（就是标准基 $(1,0)$ 和 $(0,1)$）；$\alpha,\beta \in \mathbb{C}$ 是概率幅（复数权重）；约束 $\lvert\alpha\rvert^2 + \lvert\beta\rvert^2 = 1$ 表示"读出 0 或 1 的概率加起来是 1"。

📐 怎么看： 把 qubit 态写成一个两行的列向量 $\ket{\psi} = \begin{pmatrix}\alpha\\\beta\end{pmatrix}$：第一行是基态 $\ket{0}$ 的振幅，第二行是 $\ket{1}$ 的振幅。计算基本身就是两个"独热"列向量 $\ket{0} = \begin{pmatrix}1\\0\end{pmatrix}$、$\ket{1} = \begin{pmatrix}0\\1\end{pmatrix}$。所以 $\alpha\ket{0}+\beta\ket{1} = \alpha\begin{pmatrix}1\\0\end{pmatrix}+\beta\begin{pmatrix}0\\1\end{pmatrix} = \begin{pmatrix}\alpha\\\beta\end{pmatrix}$，跟你按分量拼一个二维数组完全一样。

🔢 算例： 取 $\alpha=\tfrac{1}{\sqrt2},\ \beta=\tfrac{i}{\sqrt2}$，即 $\ket{\psi}=\begin{pmatrix}1/\sqrt2\\i/\sqrt2\end{pmatrix}$。先验归一：$\lvert\alpha\rvert^2+\lvert\beta\rvert^2 = \tfrac12+\lvert i/\sqrt2\rvert^2 = \tfrac12+\tfrac12 = 1$ ✓。测量概率：得 $\ket{0}$ 的概率 $\lvert\alpha\rvert^2=\tfrac12$，得 $\ket{1}$ 的概率 $\lvert\beta\rvert^2=\tfrac12$。注意 $\beta$ 带的那个 $i$（相位）在概率里被模方吃掉了，但它把这个态推到了 Bloch 球赤道的另一处——干涉时才显形。

🧠 类比： 一个 qubit 态 = 一个长度为 1 的二维复数数组 [α, β]，满足 |α|² + |β|² == 1。计算基 $\{\ket{0},\ket{1}\}$ 就是这个二维复向量空间的标准正交基（ONB），跟你写 Vector2(x, y) 里的 x/y 轴一个意思。

⚠️ 坑： $\alpha,\beta$ 是复数不是实数概率；真正的概率是它们的模方 $\lvert\alpha\rvert^2$、$\lvert\beta\rvert^2$。复数里那部分"相位"信息在测量概率上看不见，但在干涉时至关重要——这是量子算法的命根子。

如果想统一描述纯态和混合态，用密度矩阵 $\rho$：

$$\rho = \ketbra{\psi}{\psi}, \qquad \Tr(\rho) = \lvert\alpha\rvert^2 + \lvert\beta\rvert^2 = 1$$

这里 $\ketbra{\psi}{\psi}$ 是态向量和它的共轭转置的外积（一个 $2\times2$ 矩阵）；$\Tr$ 是求迹（对角线元素求和），迹为 1 就是概率归一的另一种写法。

📐 怎么看： $\rho=\ketbra{\psi}{\psi}$ 是列向量乘行向量（外积），结果是个 $2\times2$ 矩阵：$\rho = \begin{pmatrix}\alpha\\\beta\end{pmatrix}\begin{pmatrix}\alpha^* & \beta^*\end{pmatrix} = \begin{pmatrix}\lvert\alpha\rvert^2 & \alpha\beta^*\\ \alpha^*\beta & \lvert\beta\rvert^2\end{pmatrix}$。对角线两项 $\lvert\alpha\rvert^2,\lvert\beta\rvert^2$ 正是测得 $\ket{0}$、$\ket{1}$ 的概率（叫"布居"）；非对角线两项 $\alpha\beta^*,\alpha^*\beta$ 叫"相干项"，编码了叠加的相位关系——混合度越高它们越衰减。

🔢 算例： 取等权叠加 $\ket{+}=\tfrac{1}{\sqrt2}(\ket{0}+\ket{1})$，即 $\alpha=\beta=\tfrac{1}{\sqrt2}$。代入得 $\rho = \begin{pmatrix}1/2 & 1/2\\ 1/2 & 1/2\end{pmatrix} = \tfrac12\begin{pmatrix}1&1\\1&1\end{pmatrix}$。检验 $\Tr(\rho)=\tfrac12+\tfrac12=1$ ✓。对比"最大混合态" $\rho=\tfrac12\begin{pmatrix}1&0\\0&1\end{pmatrix}$——两者对角线一样（测量都是 50/50），但纯叠加态的非对角项不为零，这正是"量子叠加"和"经典掷硬币"在数学上的分水岭。

🧠 类比： 密度矩阵 $\rho$ = 纯态上的一个概率分布（加权集合）。如果你确定系统就是某个 $\ket{\psi}$，那是"纯态"；如果你只知道"50% 是这个态、50% 是那个态"（经典不确定性叠加在量子不确定性之上），那是"混合态"。$\rho$ 把这两层不确定性统一打包，就像用一个 WeightedSet<State> 同时表达确定值和概率分布。

Bloch 球：把单 qubit 纯态画成单位球面上的一个点。

$$\ket{\psi} = \cos(\theta/2)\ket{0} + e^{i\phi}\sin(\theta/2)\ket{1} \;\longleftrightarrow\; r = (\sin\theta\cos\phi,\ \sin\theta\sin\phi,\ \cos\theta)$$

$\theta$ 是纬度角（从北极 $\ket{0}$ 往下量），$\phi$ 是经度角（绕赤道转），$e^{i\phi}$ 是相位因子。Bloch 分量也能从密度矩阵算：$r_i = \Tr(\rho\,\sigma_i)$，其中 $\sigma_i$ 是 Pauli 矩阵。

📐 怎么看： 这条公式是"态向量 ↔ 球面坐标"的字典。给定 $(\theta,\phi)$：$\theta$ 决定 $\ket{0}/\ket{1}$ 的权重（$\cos\tfrac\theta2$ 配 $\ket{0}$、$\sin\tfrac\theta2$ 配 $\ket{1}$），$\phi$ 只动 $\ket{1}$ 前面的相位 $e^{i\phi}$。右边 $r=(\sin\theta\cos\phi,\ \sin\theta\sin\phi,\ \cos\theta)$ 就是把这个态投影到 $x/y/z$ 三根轴上的期望值（即 $\langle\sigma_x\rangle,\langle\sigma_y\rangle,\langle\sigma_z\rangle$）。

🔢 算例： ① $\ket{0}$：取 $\theta=0$，则 $\cos0=1,\ \sin0=0$，态就是 $\ket{0}$，坐标 $r=(0,0,\cos0)=(0,0,1)$——正北极。② $\ket{+}=\tfrac{1}{\sqrt2}(\ket{0}+\ket{1})$：取 $\theta=\tfrac\pi2,\ \phi=0$，则 $\cos\tfrac\pi4=\sin\tfrac\pi4=\tfrac{1}{\sqrt2}$ ✓，坐标 $r=(\sin\tfrac\pi2,0,\cos\tfrac\pi2)=(1,0,0)$——赤道上 $+x$ 方向。③ $\ket{1}$：取 $\theta=\pi$，坐标 $r=(0,0,\cos\pi)=(0,0,-1)$——正南极。

💡 人话： 一个单 qubit 纯态恰好对应球面上一个点。北极是 $\ket{0}$、南极是 $\ket{1}$、赤道上是各种等权叠加。两个参数 $(\theta,\phi)$ 就能定位它，跟用经纬度定位地球上一点完全一样。

🧠 类比： 纯态 = 球面上的点（$\lVert r\rVert = 1$）；混合态 = 球内部的点（$\lVert r\rVert < 1$）；最大混合态 $\rho = I/2$ = 正球心（完全不知道任何信息）。半径越小，信息越"糊"。

制备任意态 = 旋转：任意 qubit 态 $\ket{\psi}$ 都能找到某个幺正变换 $U \in U(2)$ 使 $\ket{\psi} = U\ket{0}$，几何上就是把北极的 $\ket{0}$ 绕某根轴转到目标点。

🔑 记住： 制备一个态 = 从 $\ket{0}$ 出发在 Bloch 球上旋转。而且实现同一目标的转轴/转角不唯一——条条大路通罗马。

测量：在计算基下测 $\ket{\psi} = \alpha\ket{0} + \beta\ket{1}$，得 $\ket{0}$ 的概率是 $\lvert\alpha\rvert^2$，得 $\ket{1}$ 的概率是 $\lvert\beta\rvert^2$。测完态就塌缩到对应的基态。想在别的基（比如测 $\sigma_x$）测量，等价于"先旋转到那个基，再做计算基测量"。

🧠 类比： 测量 = 从概率分布里采样一次，然后变量就被钉死了。像 x = random.choice([0,1], p=[|α|², |β|²])，但副作用是：采样之后这个 qubit 就永久变成你采到的那个基态了（塌缩），再读还是同一个值。一次性随机变量，读完即定值。

⚠️ 坑： 测量是破坏性的、不可逆的。它不像读一个普通变量那样"无副作用"。叠加里那些丰富的复数幅信息，一测就塌缩没了，只剩一个经典比特。所以算法要在测量之前用干涉把有用信息攒到对的地方。

多比特与 Bell 基：$n$ 个比特张成 $2^n$ 维空间，基矢从 $\ket{00\dots0}$ 到 $\ket{11\dots1}$。其中四个最大纠缠的两比特态叫 Bell 基：

$$\ket{\Phi^\pm} = \frac{\ket{00} \pm \ket{11}}{\sqrt{2}}, \qquad \ket{\Psi^\pm} = \frac{\ket{01} \pm \ket{10}}{\sqrt{2}}$$

📐 怎么看： 两比特态是 $2^2=4$ 维列向量，分量顺序约定为 $\ket{00},\ket{01},\ket{10},\ket{11}$。所以 $\ket{\Phi^+}=\tfrac{1}{\sqrt2}(\ket{00}+\ket{11}) = \tfrac{1}{\sqrt2}\begin{pmatrix}1\\0\\0\\1\end{pmatrix}$：只有"两个都 0"和"两个都 1"两项非零、且等权。而 $\ket{\Psi^-}=\tfrac{1}{\sqrt2}(\ket{01}-\ket{10}) = \tfrac{1}{\sqrt2}\begin{pmatrix}0\\1\\-1\\0\end{pmatrix}$ 则把权重压在"两个不同"的分量上。

🔢 算例： 对 $\ket{\Phi^+}=\tfrac{1}{\sqrt2}(\ket{00}+\ket{11})$ 在计算基测量两比特：得 $00$ 的概率 $\lvert\tfrac{1}{\sqrt2}\rvert^2=\tfrac12$，得 $11$ 的概率 $\tfrac12$，而得 $01$ 或 $10$ 的概率都是 $0$（这两个分量振幅为零）。所以两比特测出来必然相同。再看局部：只盯第一个比特，它得 $0$ 或 $1$ 各占 $\tfrac12$（像随机硬币），可一旦读了它，第二个比特的结果就被瞬间锁定——这就是纠缠的"关联藏在全局、单看局部却是随机"。

🧠 类比： $n$ 比特的状态空间是 $2^n$ 维——这就是经典模拟量子为什么贵：50 个 qubit 就要 $2^{50}$ 个复数才能存下完整态向量。多比特基矢的构造是各比特基的笛卡尔积 / 张量积（Kronecker 积），跟嵌套循环枚举所有组合一个道理。

💡 人话： 拿 $\ket{\Phi^+} = (\ket{00}+\ket{11})/\sqrt{2}$ 来说：在计算基下测量这两个比特，总是得到相同结果（要么都 0、要么都 1），而且各占一半概率。两个比特的命运被锁死在一起了——这就是纠缠。

⚠️ 坑： 纠缠态写不成两个单比特态的张量积（$\ket{\Phi^+} \ne \ket{a}\otimes\ket{b}$）。这正是纠缠的数学定义。别以为"强关联"就是经典相关，纠缠的关联强度超出任何经典模型能解释的范围（Bell 不等式）。

🔑 记住： 单 qubit 纯态 ↔ Bloch 球面点；信息藏在复数幅里，测量只吐出一个概率性的比特；Bell 态是纠缠的招牌——局部测量结果强关联、不可分解。

1.3 量子计算

量子计算 = 用一串幺正门组成的线路去操纵 qubit，最后测量。这一节给出门的"指令集"：单比特门、多比特门、通用门集合，加上线路的"语法规则"，最后用隐形传态做综合 demo。

单比特门 ∈ U(2)：每个单比特门都是一个保持向量长度（归一）的幺正变换，也就是一个 $2\times2$ 幺正矩阵。绕任意轴 $n = (x,y,z)$ 旋转角度 $\theta$：

$$R_n(\theta) = \cos(\theta/2)\,I - i\sin(\theta/2)\,(n\cdot\sigma)$$

$I$ 是单位矩阵，$\sigma = (\sigma_x,\sigma_y,\sigma_z)$ 是 Pauli 矩阵三件套，$n\cdot\sigma = n_x\sigma_x + n_y\sigma_y + n_z\sigma_z$。$R_x,R_y,R_z$ 就是取轴为 $x/y/z$ 的特例。

📐 怎么看： $R_n(\theta)=\cos\tfrac\theta2\,I-i\sin\tfrac\theta2\,(n\cdot\sigma)$ 把"绕轴 $n$ 转 $\theta$"拆成两块之和：$\cos\tfrac\theta2\,I$ 是"原地不动"的成分，$-i\sin\tfrac\theta2\,(n\cdot\sigma)$ 是"沿轴翻转"的成分。注意转角是 $\theta/2$ 而不是 $\theta$——这是 qubit（旋量）的招牌特征：态要转满 $4\pi$ 才回到原样。

🔢 算例： 取轴 $n=z$，则 $n\cdot\sigma=\sigma_z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$。代入：$R_z(\theta) = \cos\tfrac\theta2\begin{pmatrix}1&0\\0&1\end{pmatrix}-i\sin\tfrac\theta2\begin{pmatrix}1&0\\0&-1\end{pmatrix} = \begin{pmatrix}\cos\tfrac\theta2-i\sin\tfrac\theta2 & 0\\ 0 & \cos\tfrac\theta2+i\sin\tfrac\theta2\end{pmatrix} = \begin{pmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{pmatrix}$。可见 $R_z$ 只给 $\ket{0},\ket{1}$ 各挂一个相反的相位——在 Bloch 球上就是绕 $z$ 轴自转，难怪改不了测量概率（模方不变）。

🧠 类比： 幺正变换 = 可逆无损变换（保范数、保内积）。在编程里就像一个一定能 undo 的纯变换：$U^\dagger U = I$，逆就是它的共轭转置，没有信息丢失。这跟有损的 hash() 或会塌缩的测量正好相反。

💡 人话： 单比特门就是"在 Bloch 球上把状态点转一下"。$R_x(\theta)$ 绕 x 轴转 $\theta$，以此类推。门不改变球的半径（纯态还是纯态），只改朝向。

几个常用门：

• Hadamard ($H$)——叠加制造机：$H\ket{0} = (\ket{0}+\ket{1})/\sqrt{2}$，$H\ket{1} = (\ket{0}-\ket{1})/\sqrt{2}$。
• 相位门 $S = \operatorname{diag}(1, i)$、$T$ 门 $= \operatorname{diag}(1, e^{i\pi/4})$（又叫 $\pi/8$ 门）：只给 $\ket{1}$ 分量加一个相位。

📐 怎么看： Hadamard 矩阵 $H=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ 的列就是"基态被映到哪里"：第 1 列 $\tfrac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix}$ 是 $\ket{0}$ 的去向（等权正叠加 $\ket{+}$），第 2 列 $\tfrac{1}{\sqrt2}\begin{pmatrix}1\\-1\end{pmatrix}$ 是 $\ket{1}$ 的去向（带负号的叠加 $\ket{-}$）。一般地，矩阵元 $M_{ij}$ 读作"输入基态 $\ket{j}$、输出落到 $\ket{i}$ 的振幅"——这条规则对所有量子门通用。相位门 $S=\begin{pmatrix}1&0\\0&i\end{pmatrix}$、$T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}$ 是对角阵，只在 $\ket{1}$ 的去向（右下角）盖一个相位章，$\ket{0}$ 原封不动。

🔢 算例（H 作用在基态上）： $H\ket{0} = \tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix} = \tfrac{1}{\sqrt2}\begin{pmatrix}1\cdot1+1\cdot0\\1\cdot1+(-1)\cdot0\end{pmatrix} = \tfrac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix} = \tfrac{\ket{0}+\ket{1}}{\sqrt2}$。同理 $H\ket{1} = \tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix} = \tfrac{1}{\sqrt2}\begin{pmatrix}1\\-1\end{pmatrix} = \tfrac{\ket{0}-\ket{1}}{\sqrt2}$。矩阵乘法就是"用矩阵的每一行去点乘那个列向量"。

🔢 算例（H 自逆 / 相位门）： 再来一发 $H$ 能复原：$H\ket{+} = \tfrac12\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}1\\1\end{pmatrix} = \tfrac12\begin{pmatrix}2\\0\end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix} = \ket{0}$，印证 $H^2=I$。相位门 $S\ket{1} = \begin{pmatrix}1&0\\0&i\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix} = \begin{pmatrix}0\\i\end{pmatrix} = i\ket{1}$，只把 $\ket{1}$ 乘上 $i$；而 $S\ket{0}=\ket{0}$ 不变。

🧠 类比： $H$ 是几乎所有量子算法的"第一行代码"：把确定的 $\ket{0}$ 砸成 50/50 的等权叠加，开启量子并行的入口。把它想成"初始化一个均匀概率分布"。

任意单比特门可以做 z-y-z 分解：

$$U = e^{i\alpha}\, R_z(\beta)\, R_y(\gamma)\, R_z(\delta)$$

也就是说任何 $U(2)$ 元素都能拆成一个全局相位 $e^{i\alpha}$ 加三次固定轴旋转，$(\alpha,\beta,\gamma,\delta)$ 是四个角（旋量空间里的欧拉角）。群关系记作 $(SU(2)\ltimes U(1))/2 = U(2)$。

🧠 类比： 这就像 3D 图形里"任意旋转 = 三个欧拉角（绕 z-y-z）"，量子版只是把实旋转换成 $SU(2)$ 上的旋转。编译器把高级 U 拆成硬件能执行的三条旋转指令，就靠这个分解。

多比特门（作用在 $U(2^n)$ 上）：

• CNOT（受控非）：控制位是 1 时翻转目标位。它是纠缠的生成器。
• SWAP：交换两比特，且 SWAP = 三个 CNOT 级联。
• Toffoli (CCNOT)：双控制非门，是经典可逆计算的通用门。

📐 怎么看： 两比特门是 $4\times4$ 矩阵，行列都按 $\ket{00},\ket{01},\ket{10},\ket{11}$ 排。CNOT（控制位在前、目标位在后）写作 $\mathrm{CNOT}=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}$：上半的 $\ket{00},\ket{01}$（控制位=0）是单位块、原样不动；下半 $\ket{10},\ket{11}$（控制位=1）那个 $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ 子块，正是在目标位上做 $X$（翻转）。所以它就是"控制位为 1 才翻目标位"的置换矩阵。

🔢 算例（CNOT 与造 Bell 态）： $\mathrm{CNOT}\ket{10}$：$\ket{10}=\begin{pmatrix}0\\0\\1\\0\end{pmatrix}$，乘出来取到矩阵第 3 列 $\begin{pmatrix}0\\0\\0\\1\end{pmatrix}=\ket{11}$——控制位 1、目标位被翻成 1。而 $\mathrm{CNOT}\ket{00}=\ket{00}$（控制位 0，不动）。把 $H$ 加在前面就造出纠缠：先 $H$ 作用在第一比特，$\ket{00}\to\tfrac{1}{\sqrt2}(\ket{00}+\ket{10})$，再 $\mathrm{CNOT}$ 把 $\ket{10}\to\ket{11}$，得到 $\tfrac{1}{\sqrt2}(\ket{00}+\ket{11})=\ket{\Phi^+}$——一个 Bell 态。

🧠 类比： CNOT 就像 if control: target ^= 1，但因为它作用在叠加态上，能把两个比特纠缠起来（$H$ + CNOT 就造出 Bell 态）。Toffoli if (a and b): c ^= 1 是可逆版的 AND，用它能把任意经典布尔电路塞进量子线路。

通用门集合：一组能以任意精度模拟任何幺正变换的门，比如 $\{H, T, \mathrm{CNOT}\}$。精度要求越高，需要的门越多（Solovay-Kitaev 定理给出量级）。

🧠 类比： 通用门集 = 量子世界的图灵完备指令集。就像 NAND 门能搭出任何经典电路、几条 RISC 指令能跑任何程序，$\{H,T,\mathrm{CNOT}\}$ 能逼近任何量子计算。"任意精度"对应浮点逼近：位数越多越准，但代价是更多指令。

量子线路的语法规则（违反就报错）：

⚠️ 坑： 量子线路有三条铁律—— ① 无环：线路必须是有向无环图，不能有回路（不像经典电路可以有反馈）； ② 禁止扇入：多根线合并成一根 = 不可逆，违反幺正性； ③ 禁止扇出：把一根线复制成多根 = 克隆未知态，违反不可克隆定理。

Worked Example：量子隐形传态

目标：把 Alice 手里的未知态 $\ket{\psi} = \alpha\ket{0} + \beta\ket{1}$ 传给远端 Bob，而双方谁都不知道 $\alpha,\beta$。

1. 共享纠缠：Alice 的比特 2 和 Bob 的比特 3 预先制备成 Bell 态 $\ket{\Phi^+}$。三比特总态是 $\ket{\psi}\otimes\ket{\Phi^+}$。
2. Alice 本地操作：对她的比特 1、2 做 CNOT$(1\to2)$，再对比特 1 做 $H$，然后在计算基下测量比特 1、2，得到两个经典比特 $(m_1,m_2)\in\{00,01,10,11\}$。
3. 经典通信：Alice 把 $(m_1,m_2)$ 通过经典信道（线路图里画成双横线）发给 Bob。
4. Bob 纠正：Bob 根据收到的 $(m_1,m_2)$ 对自己的比特施加 $I$ / $X$ / $Z$ / $XZ$ 之一，就还原出 $\ket{\psi}$。

💡 人话： 无论 Alice 测出哪种结果，Bob 按对应的"纠正指令"操作后，手里一定是原来的 $\ket{\psi}$。那两个经典比特就是告诉 Bob "该用四把钥匙里的哪一把"。

🧠 类比： 这是一次 LOCC（本地操作 + 经典通信）。像分布式系统里：双方先共享一个"纠缠密钥对"（预置资源），Alice 本地算出一个 2-bit 校正码发给 Bob，Bob 用它把自己手里那半解码成原对象。传过去的只有 2 个经典比特，不是态本身。

⚠️ 坑： 隐形传态既不超光速也不违反不可克隆—— ① 它依赖经典信道传 $(m_1,m_2)$，经典通信受光速限制，所以信息传递不超光速； ② Alice 的原比特在第 2 步测量时已被破坏，世界上任意时刻只有一份 $\ket{\psi}$，没有"复制"。

🔑 记住： 单比特门 = Bloch 球旋转（任意门 z-y-z 拆成三转）；CNOT 是纠缠之源、SWAP = 3×CNOT、Toffoli 通用于经典可逆计算；通用门集 + 任意精度逼近 = 量子的"图灵完备"；隐形传态 = 纠缠资源 + 2 经典比特，传态不传物质。

1.4 量子算法

量子算法靠"量子并行 + 干涉"提取经典难以高效获取的全局信息。这一节先讲怎么在量子机上跑经典计算，再讲量子并行的真相，然后用 Deutsch 算法做最小范例，最后总结三大算法家族。

量子机上的经典计算：

• Landauer 原理：擦除一比特信息有最小能量代价 $kT\ln 2$；而可逆计算可以规避这笔开销。
• 可逆替代：任何不可逆的经典逻辑门都能用可逆量子门等效实现（比如用 Toffoli 模拟 AND/NAND）。
• 用量子测量的概率性，可以模拟概率经典计算机。

🧠 类比： Landauer 原理像"删数据要发热"。可逆计算的思路：别真删，把信息搬到辅助比特上留着（最后再 uncompute 清理）。这跟函数式编程"不可变 + 不丢信息"的精神一脉相承。

量子并行：量子机能在同一个幺正变换里同时算出函数 $f(x)$ 在许多不同 $x$ 上的值——它们以叠加态的形式共存。

$$U_f:\ \ket{x}\ket{y} \;\longrightarrow\; \ket{x}\ket{y \oplus f(x)}$$

$\ket{x}$ 是输入寄存器，$\ket{y}$ 是输出寄存器，$\oplus$ 是异或（模 2 加）。如果输入是叠加态 $\sum_x \ket{x}$，那一次 $U_f$ 就把所有 $f(x)$ 一起算了。

📐 怎么看： $U_f$ 是个置换门（不改振幅大小、只重排基态）。它把输入寄存器 $\ket{x}$ 当索引读、把输出寄存器 $\ket{y}$ 改成 $\ket{y\oplus f(x)}$。用异或而不是直接覆盖，是为了可逆：再作用一次 $U_f$ 就还原（$y\oplus f(x)\oplus f(x)=y$），满足幺正性。注意 $\ket{x}$ 那一路自始至终没被动过——这样才不破坏叠加。

🔢 算例： 设输出寄存器初始为 $\ket{0}$，输入喂等权叠加 $\tfrac{1}{\sqrt2}(\ket{0}+\ket{1})$，总态 $\tfrac{1}{\sqrt2}(\ket{0}+\ket{1})\ket{0}$。一次 $U_f$：$\ket{0}\ket{0}\to\ket{0}\ket{0\oplus f(0)}=\ket{0}\ket{f(0)}$，$\ket{1}\ket{0}\to\ket{1}\ket{f(1)}$，于是得到 $\tfrac{1}{\sqrt2}(\ket{0}\ket{f(0)}+\ket{1}\ket{f(1)})$——一次操作就把 $f(0)$ 和 $f(1)$ 同时算进了同一个态。但直接测量只能随机塌缩到其中一支，所以还需要干涉，见下面 Deutsch。

⚠️ 坑： 量子并行不是免费午餐！所有 $f(x)$ 确实叠在一个态里，但你直接测量只能随机拿到其中一个——还塌缩掉其余全部。所以"同时算 $2^n$ 个值"本身没用，必须靠后续干涉把"全局性质"提炼到能测出来的地方。这就是为什么"量子 = 大规模并行"是个误导性说法。

🧠 类比： 想象你 map(f, all_inputs) 得到一个超大结果数组，但 API 只允许你 sample() 一次就销毁整个数组。光并行 map 没意义，你得设计一种"归约 + 相消"（干涉）让你想要的那个全局答案脱颖而出。

Worked Example：Deutsch 算法

问题：给定 $f:\{0,1\}\to\{0,1\}$，判断它是常数型（$f(0)=f(1)$）还是平衡型（$f(0)\ne f(1)$）。经典做法要求两次值（算 $f(0)$ 和 $f(1)$ 再比），量子只要一次。

1. 制备 $\ket{0}\ket{1}$，两个比特各过一个 $H$，得到 $(\ket{0}+\ket{1})(\ket{0}-\ket{1})/2$。
2. 作用一次 $U_f$。由于第二比特处在 $\ket{-} = (\ket{0}-\ket{1})/\sqrt{2}$，发生相位回踢，给第一比特挂上 $(-1)^{f(x)}$ 的相位因子。
3. 对第一比特再过一个 $H$ 然后测量：测得 $\ket{0}$ ⇒ 常数型，测得 $\ket{1}$ ⇒ 平衡型。

🔢 算例（常数型 $f\equiv0$）： 第 1 步后两比特处于 $\tfrac{1}{\sqrt2}(\ket{0}+\ket{1})\otimes\ket{-}$，其中 $\ket{-}=\tfrac{1}{\sqrt2}(\ket{0}-\ket{1})$。第 2 步 $U_f$ 触发相位回踢，第一比特挂上 $(-1)^{f(x)}$：因 $f(0)=f(1)=0$，两支都乘 $(-1)^0=+1$，第一比特仍是 $\tfrac{1}{\sqrt2}(\ket{0}+\ket{1})=\ket{+}$。第 3 步对它再做 $H$：$H\ket{+}=\ket{0}$（见上面 H 自逆算例），测得 $\ket{0}$ ⟹ 判定常数型 ✓。若换成平衡型 $f(x)=x$，两支相位变成 $+1,-1$，第一比特成 $\tfrac{1}{\sqrt2}(\ket{0}-\ket{1})=\ket{-}$，而 $H\ket{-}=\ket{1}$，测得 $\ket{1}$ ⟹ 平衡型。

💡 人话： Deutsch 问的根本不是 $f(0)$ 或 $f(1)$ 各自是多少，而是 $f(0)\oplus f(1)$ 这一个全局比特（相等还是不等）。量子线路通过相位回踢把这个全局信息编码进相位，再用 $H$ 做干涉读出来，所以一次 $U_f$ 就够。

🧠 类比： 相位回踢就像把答案藏进"符号位"而不是"数值位"。经典你得分别求两个值再对比（两次调用）；量子直接问"它俩的异或"，一次调用搞定——因为你不需要知道每个值，只需要它们的关系。

🔑 记住： 量子加速的本质直觉——当经典为得到答案被迫获取了超过答案所需的信息量（存在"计算冗余"）时，量子有加速潜力。Deutsch 只想要 1 比特全局信息，经典却被迫算了 2 个局部值。推广到 $n$ 位函数就是 Deutsch-Jozsa 算法。

三大算法家族：

复杂性视角：因数分解 $\in \mathrm{BQP}$。量子威力的核心开放问题是：是否存在某些问题量子能高效解、而经典概率图灵机不能？即是否 $\mathrm{BPP} \subsetneq \mathrm{BQP}$（普遍相信成立，但尚未证明）。

🔑 记住： 量子并行单独不够用，优势来自干涉提取全局信息 + 削减信息冗余；三大家族 = QFT 类 / 搜索类 / 模拟类；BPP vs BQP 是悬而未决的世纪难题。

1.5 量子信息处理实验

理论再漂亮，也得在真实物理系统上把量子态制备出来、操控好、测得准，还要压住噪声。这一节给实验直觉、容错前景和主流硬件平台。

Stern-Gerlach 实验是自旋测量的原型。它揭示了一个核心现象：测量是不对易的。对级联的 Z-X-Z 测量，前一次测 X 会"洗掉"之前测 Z 得到的信息。

🧠 类比： 测量不对易就像两个操作 measureZ() 和 measureX() 不满足交换律：measureZ(); measureX(); measureZ() 最后那次 Z 的结果可能跟第一次不同——因为中间的 X 测量把 Z 信息重置了。顺序很重要，这和经典"读变量不改变量"截然不同。

状态/过程层析 (tomography)：通过大量重复测量来反推一个未知量子态 $\rho$ 或未知量子过程长什么样。

🧠 类比： 因为单次测量只给 1 比特、还会塌缩，想知道完整的 $\rho$ 就得拿很多份相同的态、在不同基下反复测，再用统计拟合重建——像用大量采样去估计一个隐藏概率分布。

阈值定理 (threshold theorem)：只要把量子噪声压到某个阈值以下，工程上就能实现任意规模的容错量子计算。这是大规模量子计算可行性的理论支柱。

🔑 记住： 阈值定理 = "只要单门错误率够低，就能用纠错把它无限放大到任意规模而不失控"。它是量子计算从玩具走向实用的理论保证。

规模三阶段：小规模 = 量子通信（QKD）；中等规模 = NISQ（含噪、无完整纠错的中等比特机，我们现在所处的阶段）；大规模 = 容错通用量子计算（依赖阈值定理）。

物理实现平台（没有单一最优解，各有取舍）：光学系统、超导线路（含 transmon）、离子阱、冷原子、NV 色心、核磁共振 (NMR)、任意子（拓扑）。

⚠️ 坑： 别问"哪个平台最好"——超导快但相干时间短、离子阱准但慢、光学好传输但难做双比特门……每个平台都是不同的工程取舍组合，目前没有公认赢家。

🔑 记住： 噪声是头号敌人；阈值定理给出"够低就能纠错放大"的希望；当下处于 NISQ 阶段（比特数在涨但缺完整容错）。

1.6 量子信息

量子信息论研究信息的"量子版"基本极限：量子态怎么编码、传输、压缩、保护，以及量子带来的新资源（纠缠）。它是经典信息论的直接推广。

经典信息论的两个基本问题（出发点）：

1. 信源压缩极限——一个信息源最多能压到多小？答案是 Shannon 熵。
2. 可靠传输极限——含噪信道上能以多高速率可靠传输？答案是信道容量。

🧠 类比： 第一个问题是 gzip 的理论下界（无损压缩能压到多少）；第二个是"这条丢包的网络链路，在保证可纠错的前提下最高有效带宽是多少"。Shannon 把这俩都给出了精确公式。

量子信息论把这些问题搬到量子世界，基本目标有三：

• 识别量子信息处理中的基本资源（如纠缠、相干）。
• 给出量子态压缩、量子信道传输的极限（Schumacher 压缩、量子信道容量）。
• 在含噪环境下保护量子信息（量子纠错）。

💡 人话： 把经典信息论里的每个概念做"量子升级"：比特 → qubit，Shannon 熵 → von Neumann 熵，无损压缩 → Schumacher 压缩。骨架一样，只是底层数据类型换成了量子的。

🔑 记住： 量子信息论 = 经典信息论的推广（比特换 qubit、Shannon 熵换 von Neumann 熵）；纠缠是经典没有的新资源（支撑隐形传态、超密编码）；测量的概率性和不可克隆定理共同塑造了量子信息独有的极限。

🔑 整章一句话： qubit 是归一化的二维复向量、量子门是可逆幺正变换、测量是带塌缩的概率采样、纠缠是不可分解的强关联；量子的真正威力来自叠加 + 纠缠 + 干涉三者合力，而 BPP 是否真的小于 BQP，至今仍是这个领域最大的悬念。