QEC Workshop | 3 更多工具：Clifford 群，一些 Bound

Posted on 2026-02-07 Edited on 2026-03-06

Abstract. 本文收录于合集（量子纠错研讨班学习笔记）。本节内容分成两大部分：一类共轭作用下保持 Pauli 群不变的酉变换——Clifford 门，并指出 Clifford 门没有量子优越性；以及几个 Bound。

Clifford 群
量子纠错码的上下界

Clifford 群

Clifford 群及其对称性

现在，我们想要在编码后的逻辑比特上做门。假设现在你有一个态 $|\psi\rangle$，你在上面做了一个门 $\mathcal{U}$ 得到 $\mathcal{U}|\psi\rangle$。容易预见，此时的 Stabilizer 集合应当发生某些改变：$|\psi\rangle$ 是 $\mathcal{M}$ 的特征向量并不意味着 $\mathcal{U}|\psi\rangle$ 亦然。然而，$\mathcal{U}|\psi\rangle$ 是 $\mathcal{UMU}^\dagger$ 的特征向量。要保证 Stabilizer 变化后（$S’ = \mathcal{U}S\mathcal{U}^\dagger$）还是合法的 Stabilizer，最简单粗暴的办法就是保持它不变，此时我们能做的门的集合只能是 $S$ 的正规化子。

我们研究最大的可能的这种子群。

定义 1.1.1（Clifford Group）. $P_n$ 为 $n$ 阶 Pauli 群。Clifford 群 $C_n$ 为 $\mathrm{SU}(2^n)$ 中，$P_n$ 的正规化子。

$$
C_n = \{\mathcal{U}\in \mathrm{SU}(2^n) : \forall \mathcal{P}\in P_n, ~ \mathcal{UPU}^\dagger \in P_n\}
$$

你可以验证，$\mathcal{X}, \mathcal{Y}, \mathcal{Z}, \mathcal{H}, \mathcal{CNOT}, \mathcal{R}_{\pi / 4}, e^{i\theta}\mathcal{I}$ 等都是 Clifford 群的元素，可以证明这些一并构成 Clifford 群的生成元。

Clifford 群有一些变种的记号，你可以模掉相位乃至 Pauli 算符之间的差异（$\hat{P}_n = P_n / \{\pm \mathcal{I}, \pm i\mathcal{I}\}$），记

$$
\begin{aligned}
\hat{C}_n = C_n / \{e^{i\theta}\mathcal{I}\} \\
\check{C}_n = C_n / \hat{P}_n
\end{aligned}
$$

这三个群，在后面都叫做 Clifford 群，具体是哪个不妨基于语境推导。能够模掉全局相位的道理是若 $\mathcal{U}’ = e^{i\theta} \mathcal{U}$，则 $\mathcal{U}\in C_n \Leftrightarrow \mathcal{U}’\in C_n$。事实上，全局相位是仅有的不影响共轭作用的因素：

定理 1.1.1. 设 $\mathcal{U}$ 和 $\mathcal{V}$ 是两个具有相同共轭作用的酉变换，即对于任意的 Pauli 群元素 $\mathcal{P}$ 有

$$
\mathcal{UPU}^\dagger = \mathcal{VPV}^\dagger
$$

则必有 $\mathcal{U} = e^{i\theta}\mathcal{V}$，对于某个 $\theta$。

证明. 不失一般性可以假设 $\mathcal{V} = \mathcal{I}$ 然后证明 $\mathcal{U} = e^{i\theta}\mathcal{i}$。这意味着，对于任意一个 Stabilizer 集合，$\mathcal{U}$ 将其共轭到相同的 Stabilizer，并且保证所有本征态的本征值不变。考虑这样一些生成元生成的 Stabilizer 集合（$i = 1, 2, …, n$）：$(-1)^{j_i}\mathcal{Z}_i$，其中 $\mathcal{Z}_i$ 是给张量积第 $i$ 个分量作用 $\mathcal{Z}$ 的算子，$j_i$ 表示 $j$ 二进制第 $i$ 位。注意到这个 Stabilizer 仅有的本征态是 $e^{i\theta}|j\rangle$，这组基决定了 $\mathcal{U}$ 的矩阵表示必然是 $\mathrm{diag}(e^{i\theta_1}, …, e^{i\theta_{2^n}})$。

再考虑这样一些生成元生成的 Stabilizer 集合：$\mathcal{X}_1$ 和 $(-1)^{j_{i - 1}}\mathcal{Z}_{i}$，这个 Stabilizer 仅有的本征态是 $e^{i\phi_j}|+\rangle|j\rangle$。第一维的 $|+\rangle$ 将约束 $e^{i\theta_j} = e^{i\theta_{2^{n - 1} + j}}$。类似地，你把 $\mathcal{X}_1$ 换成 $\mathcal{X}_i$，就可以证明所有 $\theta$ 确实都相等。

$\blacksquare$

注意 Clifford 群中元素给出的共轭作用实际上是 Pauli 群的自同态，并且也保持群中对易 / 反对易性质不变：记 $c(\mathcal{P}, \mathcal{Q})$ 满足 $\mathcal{PQ} = (-1)^{c(\mathcal{P}, \mathcal{Q})}\mathcal{QP}$，有

$$
(\mathcal{UPU}^\dagger)(\mathcal{UQU}^\dagger) = \mathcal{UPQU}^\dagger = (-1)^{c(\mathcal{P}, \mathcal{Q})}\mathcal{UQPU}^\dagger = (-1)^{c(\mathcal{P}, \mathcal{Q})}(\mathcal{UQU}^\dagger)(\mathcal{UPU}^\dagger)
$$

回忆上一节定义 2.1 声明的对称辛形式。既然 Clifford 群元素给出的共轭是 Pauli 群的自同态，那么作用这个共轭必然会给 Pauli 群元素的对称辛形式做线性变换。换言之有

$$
v(\mathcal{P}) = \mathbf{M}v(\mathcal{UPU}^\dagger)
$$

综合 Clifford 共轭保持对易 / 反对易性质不变和对易性与对称辛形式辛内积之联系得到 $\mathbf{M}$ 是 $\mathbb{Z}_2$ 上的辛矩阵：

$$
\forall \boldsymbol{v}, \boldsymbol{w}\in \mathbb{Z}_2^{2n}, (\mathbf{M}\boldsymbol{v})^\top \Lambda (\mathbf{M}\boldsymbol{w}) = \boldsymbol{v}^\top \Lambda \boldsymbol{w} \quad \Rightarrow \quad \mathbf{M}^\top \Lambda \mathbf{M} = \Lambda, \qquad \text{where }\Lambda = \begin{pmatrix}
& \mathbf{I} \\
\mathbf{I} &
\end{pmatrix}
$$

故得到 Clifford 群与辛群 $\textsf{Sp}(2n, \mathbb{Z}_2)$ 之间至少存在一个同态。事实上我们接下来还将看到任意一个辛群中的矩阵（将其任意取全局相位提升至一个 $\textsf{P}_n$ 到 $\textsf{P}_n$ 的同态）都可以对应一个 Clifford 共轭：

定理 1.1.2. 设 $M$ 是 $\textsf{P}_n\rightarrow \textsf{P}_n$ 的群同态，记 $M(\mathcal{X}_i) = \overline{\mathcal{X}}_i, M(\mathcal{Z}_i) = \overline{\mathcal{Z}}_i$，满足

$$
c(\overline{\mathcal{X}}_i, \overline{\mathcal{X}}_j) = c(\overline{\mathcal{Z}}_i, \overline{\mathcal{Z}}_j) = 0, \qquad c(\overline{\mathcal{X}}_i, \overline{\mathcal{Z}}_j) = \delta_{ij}
$$

则存在一个酉变换 $\mathcal{U}$，使得 $M$ 正是 $\mathcal{U}$ 的共轭作用。根据 $M$ 是 $\textsf{P}_n\rightarrow \textsf{P}_n$ 的群同态，$\mathcal{U}$ 必然是 Clifford 群的元素。

构造. 直接照如下方法构造 $\mathcal{U}$ 的矩阵表示

求 $|\psi_0\rangle$，使得 $|\psi_0\rangle$ 是全部 $\overline{\mathcal{Z}}_i$ 的本征值为 $+1$ 的本征态，这个态存在唯一性显然。
对于任意的 $b = 0, 1, …, 2^{n - 1}$，定义 $\overline{\mathcal{X}}(b) = \prod_i (\overline{\mathcal{X}}_i)^{b_i}$。令 $|\psi_b\rangle = \overline{\mathcal{X}}(b)|\psi_0\rangle$。
有 $\mathcal{U}_{ab} = \langle a|\psi_b\rangle$。

证明方法为首先验证 $|\psi_b\rangle$ 构成标准正交基（于是知道 $\mathcal{U}$ 是酉变换），然后验证 $\mathcal{UZ}_i\mathcal{U}^\dagger|\psi_b\rangle$ 和 $\overline{\mathcal{Z}_i}|\psi_b\rangle$ 结果相同，对于 $\mathcal{X}$ 那边也一样，即可。

$\blacksquare$

至此我们证明了 Clifford 群具有辛对称性：

定理 1.1.3. $\check{C}_n \cong \textsf{Sp}(2n, \mathbb{Z}_2)$。

$\blacksquare$

Clifford 群的经典模拟

Clifford 群元素的描述并不需要过多的比特。上一节所述的 Clifford 群同构于辛群表明，惟须给定一个 Pauli 群元素的象（也是一个 Pauli 群元素）及其全局相位即可断定该 Clifford 群元素，所需惟 $2n(2n + 1)$ 个比特。相对地，$\textsf{U}(2^n)$ 中的元素需要 $2^{2^n}$ 个实参数方可刻画。因此，虽然引入 Clifford 群的初衷是其具有便于进行量子纠错的性质，但关于 Clifford 群的最为重要的结果给出了遗憾的事实：一切 Clifford 门组成的量子线路都可以被经典模拟。我们逐步推导这一结论。

定理 1.2.1. 若一个电路由 Clifford 门复合而成：$\mathcal{U} = \prod_{i = m}^1 \mathcal{U}_i$（此处倒着乘是为了让 $\mathcal{U}_1$ 作为首个作用的门），其中 $\mathcal{U}_i \in \textsf{C}_n$，并已知它可以被它对 Pauli 群生成元的作用刻画：$\mathcal{U}_i : \mathcal{X}_j \mapsto U_i(\mathcal{X}_j), \mathcal{Z}_j \mapsto U_i(\mathcal{Z}_j)$。则整个电路对一个 Pauli 群中元素的共轭作用可用经典多项式复杂度算法求出。

构造. 算法正是源于节首语所言：表示 Clifford 群中元素所需的比特数目仅为 $2n(2n + 1)$，以及共轭作用具有的同态性，因此 $U_i(U_{i - 1}(…U_1(\mathcal{X}_j)))$ 容易从 $U_{i - 1}(…U_1(\mathcal{X}_j))$ 推出。

$\blacksquare$

我们进一步考虑一个 Clifford 电路作用在一个给定的初态上的效果。当然，这个初态应当是某个 Stabilizer 的 $+1$ 本征态。

定理 1.2.2. 若一个电路由 Clifford 门复合而成：$\mathcal{U} = \prod_{i = m}^1 \mathcal{U}_i$，其中 $\mathcal{U}_i \in \textsf{C}_n$，并已知它可以被它对 Pauli 群生成元的作用刻画：$\mathcal{U}_i : \mathcal{X}_j \mapsto U_i(\mathcal{X}_j), \mathcal{Z}_j \mapsto U_i(\mathcal{Z}_j)$。再考虑一个由 $\mathcal{M}_1, …, \mathcal{M}_{n - k}$ 生成的、编码了 $k$ 个逻辑比特的 Stabilizer $\textsf{S}$，其上方可以完成逻辑门 $\overline{\mathcal{X}}_j, \overline{\mathcal{Z}}_j$（对于 $j = 1, 2, …, k$）。则整个电路对这个 Stabilizer Code 的作用可以用经典多项式复杂度算法求出。

构造. 同上所述，你可以追踪全部稳定子生成元和逻辑门的变化。

$\blacksquare$

最后我们来考察 Pauli 测量，现在要测量当前的态（属于某个 Stabilizer $\textsf{S}$ 的本征态）关于 $\mathcal{P}$ 的本征值。这里首先需要写一些直觉：

如果你测量一个 $\textsf{S}$ 中的元素，那么态会保持原样；
如果你测量一个 $N(\textsf{S})\setminus \textsf{S}$ 中的元素，那么态会被确定性地投影到一边，可能的态数量除以 $2$，可见 Stabilizer 的大小翻倍（生成元个数加一）；
如果你测量这之外的元素，那么态会被随机地投到两个特征子空间中，可能的态数量并没有变，但是空间发生了变化，可见 Stabilizer 的大小不变，但是生成元变化。

如果不能想象这三种情况，推荐考虑一个单比特线路，Stabilizer 取作 $\{\mathcal{I}\}$ 和 $\{\mathcal{I}, \mathcal{Z}\}$。

首先有两种局部的特殊情况：

$\pm \mathcal{P}\in \textsf{S}$ 答案无非是 $\pm 1$。
$\mathcal{P}\in N(\textsf{S}) \setminus \textsf{S}$，则 $\mathcal{P}$ 必可写作逻辑门 $\overline{\mathcal{X}}_i, \overline{\mathcal{Z}}_i$ 之积。那么此时测量产出必然是原输入比特关于这个逻辑门的测量结果，而投影后的东西是 $\mathcal{P}$ 的本征值为 $\pm 1$ 的本征态，我们需要把 $\pm \mathcal{P}$ 加入 Stabilizer 中。

比较困难的情形是 $\mathcal{P}\notin N(\textsf{S})$，即 $\textsf{S}$ 中存在一个与 $\mathcal{P}$ 反对易的元素 $\mathcal{M}$。注意到

$$
\langle\psi|\mathcal{P}|\psi\rangle = \langle\psi|\mathcal{PM}|\psi\rangle = -\langle\psi|\mathcal{MP}|\psi\rangle = -\langle\psi|\mathcal{P}|\psi\rangle = 0
$$

这表明落在 $1, -1$ 两个特征子空间内的投影模长相等，换言之测出 $\pm 1$ 的可能性均等。假设测出了 $(-1)^b$，那么 $|\psi\rangle$ 将被投影至

$$
|\psi’\rangle = \frac{1}{\sqrt 2}(\mathcal{I} + (-1)^b \mathcal{P})|\psi\rangle
$$

接下来如何更新 $\textsf{S}$？首先考虑 $|\psi’\rangle$ 是哪些东西的本征态，以下是两个比较局部的情况：

我们宣称对于任意与 $\mathcal{P}$ 反对易的 $\mathcal{M}$ 而言，$|\psi’\rangle$ 都不是其本征态。原因是 $|\psi’\rangle$ 是 $(-1)^b\mathcal{P}$ 的本征值为 $+1$ 的本征态，你可以自行反证导出矛盾。
我们宣称对于任意 $\textsf{S}$ 中与 $\mathcal{P}$ 对易的 $\mathcal{M}$ 而言，$|\psi’\rangle$ 都是其本征态。这点你可以自行验证。

剩下一部分情况（$\textsf{S}$ 以外与 $\mathcal{P}$ 对易的 $\mathcal{M}$）是难以通过计算验证的。我们转而计数证明 2 中即包含了全部可能的 Stabilizer：

引理 1.2.3. 令 $\textsf{S}$ 为一个 Stabilizer，$\mathcal{P}\notin N(\textsf{S})$，则 $\textsf{S}$ 中恰有一半元素与 $\mathcal{P}$ 对易。事实上这个结论对于 $\mathcal{N}(\textsf{S}) / \textsf{S}$ 中的每个陪集都成立。

证明. 令 $\mathcal{M}$ 是 $\textsf{S}$ 中一个与 $\mathcal{P}$ 反对易的元素。则有 $\mathcal{N}\leftrightarrow \mathcal{MN}$ 构成了一个 $\textsf{S}$ 中元素之间的两两配对（须注意 $\mathcal{M}^2 = \mathcal{I}$，因为是 Pauli 算符），且两者恰好分别与 $\mathcal{P}$ 对易和与 $\mathcal{P}$ 反对易。

$\blacksquare$

这直接推出了 $\textsf{S}$ 中与 $\mathcal{P}$ 对易的元素和 $(-1)^b\mathcal{P}$ 并起来生成的 Stabilizer $\textsf{S}’$ 和 $\textsf{S}$ 具有相同的大小。这表明测量至少不会导致码字空间变大。实际上，码字空间也不会变小【FIXME：这里需要引理 1.2.3 中关于陪集的论断，并可能需要补充一些关于码字从何而来的直觉，我们在第一章中遗漏了所以看不懂】。

综合以上全部结果得到著名的 Gottesman-Knill 定理：

定理 1.2.3（Gottesman-Knill）. 若一个线路的作用于一个已知的 Stabilizer 的本征态，线路中仅包含以下三种要素：

Clifford 门；
Pauli 测量；
关于测量结果的经典信号的分支。

则存在高效的经典算法模拟出全部的测量结果。

构造. 假设线路的初态是 Stabilizer $\textsf{S}$ 的一个本征态，其中 $\textsf{S}$ 的生成元是 $\mathcal{M}_1, …, \mathcal{M}_{n - k}$，其上可以做逻辑门 $\overline{\mathcal{X}}_i, \overline{\mathcal{Z}}_i, i = 1, …, k$；线路依次调用两种操作之一：

$\mathcal{U}_i$，一个 Clifford 群元素，并有定理 1.2.1 中的刻画 $U_i$；
对 $\mathcal{P}_i \in \textsf{P}_n$ 做 Pauli 测量。

则对其做经典模拟的完整算法如下：

初始化，设 $k’ \leftarrow k$，$\mathcal{N}_j \leftarrow \mathcal{M}_j$（$j = 1, …, n - k$），$\overline{\mathcal{X}}’_j \leftarrow \overline{\mathcal{X}}_j, \overline{\mathcal{Z}}’_j\leftarrow \overline{\mathcal{Z}}_j$（$j = 1, …, k$），初态为 $|\overline{\psi}\rangle$（对应逻辑态为 $|\psi\rangle$）；
For 每一个操作：
$\qquad$ If 当前操作是门 $\mathcal{U}_i$：
$\qquad\qquad$ $\mathcal{N}_j \leftarrow U_i(\mathcal{N}_j)$，$\overline{\mathcal{X}}_j \leftarrow U_i(\overline{\mathcal{X}}_j)$，$\overline{\mathcal{Z}}_j \leftarrow U_i(\overline{\mathcal{Z}}_j)$；
$\qquad$ If 当前操作是对 $\mathcal{P}_i$ 测量，且 $\pm \mathcal{P}_i \in \textsf{S}$（本步骤可调用二元辛形式上的线性基完成）：
$\qquad\qquad$ 输出 $\pm 1$；
$\qquad$ If 当前操作是对 $\mathcal{P}_i$ 测量，且 $\mathcal{P}_i\in N(\textsf{S})\setminus \textsf{S}$（本步骤可以枚举生成元计算辛内积完成）：
$\qquad\qquad$ 将 $\mathcal{P}_i$ 分解做 $\prod_{j = 1}^{n - k’} N_j^{s_j}\prod_{j = 1}^k {\overline{\mathcal{X}}’}_j^{t_j}{\overline{\mathcal{Z}}’}_j^{u_j}$；
$\qquad\qquad$ 令 $\mathcal{Q} \leftarrow \prod_{j = 1}^k \mathcal{X}_j^{t_j}\mathcal{Z}_j^{u_j}$；
$\qquad\qquad$ 设 $(-1)^b$ 是 $|\psi\rangle$ 在 $Q$ 下的 Pauli 测量结果，输出之；
$\qquad\qquad$ $k’ \leftarrow k’ - 1$，将 $(-1)^b\mathcal{P}_i$ 列入 Stabilizer 生成元；
$\qquad$ If 当前操作是对 $\mathcal{P}_i$ 测量，且 $\mathcal{P}_i \notin N(\textsf{S})$：
$\qquad\qquad$ 均匀随机采样 $b$，返回 $(-1)^b$；
$\qquad\qquad$ 在生成元中找 $\mathcal{M}$ 使得其与 $\mathcal{P}_i$ 反对易；
$\qquad\qquad$ 枚举 $i = 2, …, n - k’$，若 $[\mathcal{N}_i, \mathcal{P}_i] = 0$，保持其不变；否则 $\mathcal{N}_i \leftarrow \mathcal{MN}_i$；
$\qquad\qquad$ $\mathcal{N}_1 \leftarrow (-1)^b\mathcal{P}_i$；
$\qquad\qquad$ 对 ${\overline{\mathcal{X}}’}_i, {\overline{\mathcal{Z}}’}_i$ 也做 15 行中的变换。

$\blacksquare$

补充材料

以下是一些没看懂但是至关重要的内容，这里罗列如下。

David Gottesman 的教材中还涉及 Clifford 群生成元，以及将任意一个 $\check{\textsf{C}}_n$ 元素怎么表示成 $\mathcal{H}, \mathcal{CNOT}$ 之乘积的算法；
发表于 FOCS’99 的文章 On Universal and Fault-Tolerant Quantum Computing 证明了 Clifford 群加上任意一个群外元素都构成通用量子门集合，现实中常用 Clifford + Toffoli 或者 Clifford + T；但这些门也构成量子纠错的主要开销。
Solovay-Kitaev 定理告诉我们怎么将一个线路以较小代价编译到一个通用的门集上去。

量子纠错码的上下界

按照以往惯例记 $((n, K, d))_q$ 表示用 $n$ 个物理比特编码了一个 $K$ 维子空间的逻辑比特，码距为 $d$ 的量子纠错码，其中一个量子比特是 $q$ 维复向量，不写默认为 $2$。和经典编码理论一样，量子纠错码也有一些上下界，其中：

上界指出纠错的不可能性；
下界指出纠错码存在的充分条件。

Quantum Gilbert-Varshamov Bound

这是经典 Gilber-Varshamov 界的量子推广。

定理 2.1.1（Quantum Gilbert Varshamov Bound）. 若

$$
2^k\left(\sum_{j = 0}^{d - 1}3^j\binom nj\right) \leq 2^n
$$

则存在 $((n, 2^k, d))$ 纠错码。事实上，存在 $[[n, k, d]]$ Stabilizer Code。

证明. 首先一个重要观察是：对于任意两个错误 $\mathcal{E}, \mathcal{F}\in \textsf{P}_n \setminus \{\mathcal{I}\}$，有相同数量（不妨设这个数为 $C$）的 Stabilizer Code 不能纠正之。这是因为必然存在 Clifford 共轭 $U$，使得 $\mathcal{F} = U(\mathcal{E})$。那么若 $\textsf{S}$ 不能纠正 $\mathcal{E}$，则 $U(\textsf{S})$ 不能纠正 $\mathcal{F}$，这给出了不能纠正 $\mathcal{E}, \mathcal{F}$ 的 Stabilizer Code 之间的双射。那么循证明经典 Gilbert Vashamov Bound 之惯例，设 $B$ 为距离小于 $d$ 的错误总数，$N$ 表示 $[[n, k, \cdot]]$ Stabilizer 的总数，由 Union Bound 可知只要

$$
(B - 1)C < N
$$

则必有一 $[[n, k, \cdot]]$ 码之码距不小于 $d$。现在惟须计算上面各成分的具体数值，$B$ 的计算相当容易：

$$
B = \sum_{i = 0}^{d - 1}\binom nj 3^j
$$

关于 $C, N$，直接算起来非常棘手，所幸有以下方程成立：

$$
C |\textsf{P}_n \setminus \{\mathcal{I}\}| = N |N(\textsf{S}) \setminus \textsf{S}|
$$

其中 $|\textsf{P}_n\setminus \{\mathcal{I}\}| = 4^n - 1$ 显然；根据熟知的结果 $N(\textsf{S}) / \textsf{S}\cong \textsf{P}_k$ 和拉格朗日定理有 $|N(\textsf{S})| = 2^{n + k}$，因此 $|N(\textsf{S}) \setminus \textsf{S}| = 2^{n + k} - 2^{n - k}$。代入得到

$$
2^{n - k}\frac{4^k - 1}{4^n - 1}\sum_{i = 0}^{d - 1}3^j\binom nj < 1
$$

当然实践中用不到这么紧，简明起见再用 $\frac{4^k - 1}{4^n - 1} < 4^{k - n}$ 放缩立即得到欲证形式。

$\blacksquare$

Quantum Hamming Bound

Classic Sphere Packing Bound 的推广，只对非简并的纠错码成立，非常弱智。

定理 2.2.1（Quantum Hamming Bound）. 若存在非简并的 $((n, K, 2t + 1))_q$ 码，则

$$
K\left(\sum_{j = 0}^t (q^2 - 1)^j \binom nj\right) \leq q^n
$$

证明. 【FIXME：这个结论需要补充证明】量子纠错码非简并可以用以下条件刻画：对于任意的两个错误 $\mathcal{E}_a, \mathcal{E}_b$ 和两个码字 $|\psi\rangle, |\phi\rangle$ 有

$$
\langle\psi|\mathcal{E}_a^\dagger\mathcal{E}_b|\phi\rangle = 0, \qquad \text{matrix $C_{ab} = \langle\psi|\mathcal{E}_a^\dagger\mathcal{E}_b|\psi\rangle$ has full rank}
$$

这表明 $\{\mathcal{E}_a|\psi_i\rangle\}$ 构成 $\mathrm{Span}\{|0\rangle, …, |q - 1\rangle\}^{\otimes n}$ 中的一个线性无关组，根据维数关系得到

$$
|\{\mathcal{E}_a|\psi_i\rangle\}| \leq q^n
$$

前者展开计算无非是欲证形式中的求和。

$\blacksquare$

Quantum Singleton Bound, Linear Programming Bounds

【FIXME】