QEC Workshop | 3+ 理论补充
Abstract. 本文收录于 合集（量子计算文章选读）。本节补充一些可能没什么用的理论，主要包括一些关乎纠错码是否存在的 bound，以及 qudit code。
量子纠错码的上下界
按照以往惯例记 $((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}$ 放缩立即得到欲证形式。
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
$$
前者展开计算无非是欲证形式中的求和。
Quantum Singleton Bound, Linear Programming Bounds
【FIXME】