QEC Workshop | 3 Clifford 群

Posted on Edited on Word count in article: 4.9k Reading time ≈ 18 mins.

Abstract. 本文收录于 合集（量子计算文章选读）。本节介绍 Clifford 群。这个群是 Pauli 群的正规化子。它的重要结构是 $\check{\textsf{C}}_n\cong \textsf{Sp}(2n, \mathbb{Z}_2)$，这使得 Clifford 门组成的电路可以被经典高效模拟，相应的也可以用来实现所有 stabilizer code 的 Encoder。

前面几节我们已经掌握了 stabilizer 集合和稳定子码。现在我们往前走一步：考虑全体码字 $|\psi\rangle\in \mathcal{T}(\textsf{S})$。编完码之后，我们希望在上面做一个门 $U\in \textsf{U}(2^n)$。这会将码字集合映射到 $U(\mathcal{T}(\textsf{S}))$。然后，我们希望继续用 stabilizer formalism 对这个集合进行纠错，因此需要探究稳定住它的 unitary 有哪些。当即可以观察到的事实是，若 $\textsf{M}\in \textsf{S}$ 稳定住原本的码字，那么 $M’ = UMU^\dagger$ 稳定住 $U(\mathcal{T}(\textsf{S}))$：
$$
M’U|\psi\rangle = UMU^\dagger U|\psi\rangle = UM|\psi\rangle = U|\psi\rangle
$$

也就是说，$\textsf{S}$ 的共轭 $U\textsf{S}U^\dagger$ 稳定住了 $U|\psi\rangle$ 是显而易见的事实。在实现 fault tolerant 时，我们希望直接利用这一点：直接让 $U\textsf{S}U^\dagger$ 就是 $U(\mathcal{T}(\textsf{S}))$ 的 stabilizer 集合。这首先要求 $U\textsf{S}U^\dagger$ 还是 Pauli 群的子群，其次 $\textsf{S}(U(\mathcal{T}(\textsf{S}))) = U\textsf{S}U^\dagger$（而不是真子集，即 $U$ 保证 $U(\mathcal{T}(\textsf{S}))$ 还是 stabilizer code）。因此，本节分析满足上述要求的酉变换集合，即所谓的 Clifford 群。

首先我们定义 Clifford 群，按照上方要求中最本质的一条，我们将 Clifford 群定义为 Pauli 群的正规化子：

定义 1（Clifford Group）. 令
$$
\textsf{C}_n = \{U\in \textsf{U}(2^n) : U\textsf{P}_n U^\dagger = \textsf{P}_n\} \label{eq:stabilizer-state}
$$

Clifford 群这个术语来历不明，切莫为其困扰。

可以验证，$\textsf{P}_n$、$H$、$\operatorname{CNOT}$ 都是 Clifford 群的元素。定义以下两个变种 Clifford group：
$$
\begin{align}
\hat{\textsf{C}}_n &= \textsf{C}_n / \{e^{\mathrm{i}\theta}I\} \\
\check{\textsf{C}}_n &= \hat{\textsf{C}}_n / \hat{\textsf{P}}_n
\end{align}
$$

代数结构

两个变种定义分别反映了 Clifford 群的两方面结构：

  1. Clifford 群模掉相位之后，任意两个商群中的元素对应 Pauli 群上不同的共轭作用。
  2. Clifford 群模掉 Pauli 群之后，任意两个商群中的元素对应 Pauli 群上本质不同的共轭作用（认为两个共轭作用本质相同，若它们作用于每个 $P$ 都只差相位），进而同构于辛群 $\textsf{Sp}(2n, \mathbb{Z}_2)$。

定理 1.1. 对于 $U, V\in \textsf{C}_n$，有

$$
UPU^\dagger = VPV^\dagger
$$

对于一切 $P\in \textsf{P}_n$ 都成立当且仅当 $U / \{e^{\mathrm{i}\theta}I\} = V / \{e^{\mathrm{i}\theta}I\}$。

证明. 两边左乘 $V^\dagger$ 右乘 $V$ 知道只用证明

$$
UPU^\dagger = P \quad \Leftrightarrow \quad U = e^{i\theta}I.
$$

观察式 \eqref{eq:stabilizer-state} 可以知道，如果 $|\psi\rangle$ 是 $\textsf{S}$ 的 stabilizer state（回忆 补充内容 第四节提过这个定义），那么 $U|\psi\rangle$ 是 $U\textsf{S}U^\dagger$ 的公共特征值。而 $UPU^\dagger = P$，所以说 $U|\psi\rangle$ 还是 $\textsf{S}$ 的公共特征值。

对于 $j\in [2^n]$，构造如下 stabilizer 生成元：$M_i = (-1)^{j_i} Z_i$。其中 $j_i$ 表示 $j$ 在二进制数的第 $i$ 位。则可知 $|j\rangle$ 是该 stabilizer 集合的 stabilizer state。上一段的 argument 表明必然有 $U|j\rangle = e^{\mathrm{i}\theta_j}|j\rangle$。至此我们知道 $U$ 必然是对角阵，其 $2^n$ 个对角元都形如 $e^{\mathrm{i}\theta_j}|j\rangle$。

对于 $j\in [2^{n - 1}]$ 和 $i\in [n]$，构造如下 stabilizer 生成元：
$$
M_t = \begin{cases}
(-1)^{j_t} Z_t & t < i, \\
X_i & t = i, \\
(-1)^{j_{t - 1}} Z_t & t > i.
\end{cases}
$$

可知 $|\psi_{ij}\rangle = |j_{1\ldots i - 1}\rangle|+\rangle|j_{i\ldots n - 1}\rangle$ 是其 stabilizer state。必须有 $U|\psi_{ij}\rangle = e^{\mathrm{i}\theta}|\psi_{ij}\rangle$。稍加讨论发现，这蕴含对于 $j\in [2^{n - 1}]$ 和 $i\in [n]$，有 $\theta_{j_1\cdots j_{i-1} 0 j_{i}\cdots j_{n - 1}} = \theta_{j_1\cdots j_{i-1} 1 j_{i}\cdots j_{n - 1}}$。当 $i, j$ 遍历其取值范围，这会将所有的 $\theta$ 都连接起来，从而得到 $U = e^{\mathrm{i}\theta}I$。

$\blacksquare$

现在来考察 $\check{\textsf{C}}_n$ 的结构。首先我们观察商掉 Pauli 群意味着什么。对于 $U, V\in \hat{\textsf{C}}_n$，$U / \hat{P}_n = V / \hat{P}_n$ 当且仅当 $U^\dagger V \in \hat{\textsf{P}}_n$。那么有对于任意的 $P\in \textsf{P}_n$
$$
(UPU^\dagger)(VPV^\dagger)^\dagger = (-1)^{c(U^\dagger V, P)} UPP(U^\dagger V)V^\dagger = (-1)^{c(U^\dagger V, P)}I
$$

也就是说，如果 $U / \hat{P}_n = V / \hat{P}_n$，则它们对应的共轭作用只差一个相位。其实反过来也是一样：如果 $UPU^\dagger = \pm P$ 对于每个 $P\in \textsf{P}_n$ 都成立，那么确实有 $U = e^{\mathrm{i}\theta}Q$（其中 $Q\in \textsf{P}_n$）：

定理 1.2. 若 $UPU^\dagger = \pm P$ 对于任意 $P\in \textsf{P}_n$ 都成立，那么存在 $Q\in \textsf{P}_n, \theta\in \mathbb{R}$ 使得 $U = e^{\mathrm{i}\theta}Q$。

证明. $UP = (-1)^{c_P}U^\dagger$ 且 $U\in \textsf{P}_n$ 这个约束条件限制在 $X_1, \ldots, X_n, Z_1, \ldots, Z_n$ 上面就对应一个二元辛形式的线性方程组，这个方程组显然有解，这个解便是 $Q$。再结合定理 1.2，如果存在一个别的 $U’$ 给出了同样的共轭作用，那么 $U’$ 和 $Q$ 必然只差全局相位，结论得证。

$\blacksquare$

知道了这个信息之后我们不难进行以下推理：

  1. 考虑 $\check{\textsf{C}}_n$ 的结构时，由于相位不重要，我们将其作用对象——Pauli 群的诸元素，全部用二元辛形式表示。
  2. $\check{\textsf{C}}_n$ 中任一元素 $U$ 对应的共轭作用会把 Pauli 群元素映射到 Pauli 群元素，忽略相位之后，它可以写作一个 $\mathbb{Z}_2^n \times \mathbb{Z}_2^n$ 上的线性变换 $\mathbf{M}$。不同的 $U$ 必然对应不同的 $\mathbf{M}$。而且，这个 $\mathbf{M}$ 保持对易和反对易性不变（因为它是共轭作用）：取
    $$
    \mathbf{J} = \begin{pmatrix}
    & \mathbf{I} \\
    -\mathbf{I} &
    \end{pmatrix},
    $$
    这个矩阵是辛内积的矩阵表示，即 $\boldsymbol{u}\odot\boldsymbol{v} = \boldsymbol{u}^\top\mathbf{J}\boldsymbol{v}$。于是有 $\mathbf{J} = \mathbf{M}^\top\mathbf{JM}$。回忆全体保持 $\mathbf{J} = \mathbf{M}^\top\mathbf{JM}$ 的矩阵构成辛群 $\textsf{Sp}(2n, \mathbb{Z}_2)$。
  3. 反过来，只要对于任何一个 $\mathbf{M}$，都能找到相应的共轭作用，那么我们就得到了 $\check{\textsf{C}}_n \cong \textsf{Sp}(2n, \mathbb{Z}_2)$。

事实上，3 确实是成立的：

定理 1.3. 设 $M\colon \textsf{P}_n\rightarrow \textsf{P}_n$ 是 Pauli 群上的同态。记 $M(X_i) = \overline{X}_i, M(Z_i) = \overline{Z}_i$，且 $M$ 保持对易性：$c(\overline{X}_i, \overline{X}_j) = c(\overline{Z}_i, \overline{Z}_j) = 0, c(\overline{X}_i, \overline{Z}_i) = \delta_{ij}$。则存在一个酉变换 $U$ 使得 $M$ 正是 $U$ 的共轭作用。

这里要把 $c(\cdot, \cdot)$ 从 Pauli 群完整拓展到酉变换。如果 $U, V$ 既不对易也不反对易，不妨令 $c(u, v) = \bot$。

证明. 直接构造 $U$：

  1. 找到所有 $\overline{Z}_i$ 的一个公共特征向量（特征值都为 $1$） $|\psi_0\rangle$。
  2. 对于 $b\in [2^n]$，令 $\overline{X}(b) = \prod_i (\overline{X}_i)^{b_i}$，其中 $b_i$ 表示 $b$ 的二进制第 $i$ 位。
  3. 令 $|\psi_b\rangle = \overline{X}(b)|\psi_0\rangle$；$U_{ab} = \langle a|\psi_b\rangle$。

这个构造源自基本的线性代数直觉：Unitary 的共轭作用是联系两组标准正交基的坐标变换。$\{|\psi_b\rangle\}$ 这组基之于 $\overline{X}_i, \overline{Z}_i$ 相当于 $\{|a\rangle\}$ 之于 $X_i, Z_i$。联系它们的坐标变换无非是这两组基的 Gram 矩阵，也就是上方构造中的 $U$。验证上方构造确实成立无非以下几个步骤：

  1. $|\psi_0\rangle$ 的存在性。只需要注意到 $\{\overline{Z}_i\}$ 构成一组 stabilizer，于是至少有一个 stabilizer state。
  2. $U$ 的共轭作用确实把 $X_i$ 映射到 $\overline{X}_i$，把 $Z_i$ 映射到 $\overline{Z}_i$。这个验算即可。
$\blacksquare$

至此，我们得到了 $\check{\textsf{C}}_n$ 的结构：

推论 1.4. $\check{\textsf{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 门组成的量子线路都可以被经典模拟。我们逐步推导这一结论。

定理 2.1. 若一个电路由 Clifford 门复合而成：$U = U_m\cdots U_1$，其中 $U_i \in \textsf{C}_n$，并已知它可以被它对 Pauli 群生成元的共轭作用刻画：$U_i : X_j \mapsto U_i(X_j), Z_j \mapsto U_i(Z_j)$。则整个电路对一个 Pauli 群中元素的共轭作用可用经典多项式复杂度算法求出。

构造. 从 $1$ 到 $m$ 递推即可：

  1. 初始化 $\overline{X}_i = X_i, \overline{Z}_i = Z_i$；
  2. 枚举 $i = 1, …, m$；
  3. $\qquad$ 计算 $U_i(\overline{X}_j), U_i(\overline{Z}_j)$（将 $\overline{X}_j, \overline{Z}_j$ 写作 $X_j, Z_j$ 的乘积，利用共轭作用是同态即可）
  4. $\qquad$ $\overline{X_j} \leftarrow U_i(\overline{X}_j), \overline{Z}_j \leftarrow U_i(\overline{Z}_j)$。
$\blacksquare$

我们进一步考虑一个 Clifford 电路作用在一个给定的初态上的效果，其中这个初态是某个由 $n$ 个生成元生成的 stabilizer 的 stabilizer state。

定理 2.2. 若一个电路由 Clifford 门复合而成：$U = U_m\cdots U_1$，其中 $U_i \in \textsf{C}_n$，并已知它可以被它对 Pauli 群生成元的作用刻画：$U_i : X_j \mapsto U_i(X_j), Z_j \mapsto U_i(Z_j)$。再考虑一个由 $M_1, …, M_{n - k}$ 生成的、编码了 $k$ 个逻辑比特的 stabilizer $\textsf{S}$，其上方逻辑操作记为 $\overline{X}_j, \overline{Z}_j$（对于 $j = 1, 2, …, k$）。则作用整个电路之后，这个 stabilizer code 的生成元和逻辑操作的形式可以用经典多项式时间算法求出。

构造. 首先你容易追踪生成元的变化：因为作用一个 Clifford 门 $U_i$ 会把 stabilizer 变成 $U_i\textsf{S}U_i^\dagger$，相应地就是对生成元也做共轭作用。逻辑操作的变化也是共轭作用：

$$
U\overline{X}_i |\psi\rangle = (U\overline{X}_iU^\dagger)U|\psi\rangle
$$

所以与用定理 1.6 里面的那个算法类似的结构，你可以追踪 stabilizer 生成元和逻辑操作。

$\blacksquare$

最后我们来考察 Pauli 测量，现在要测量一个满的 stabilizer $\textsf{S}$ 的 stabilizer state $|\psi\rangle$。简单推理发现：如果 $\pm P \in \textsf{S}$，测量结果无非是 $\pm 1$（取决于 $P\in \textsf{S}$ 还是 $-P\in \textsf{S}$），且不会影响被测量的态。比较困难的情形是 $P\notin \textsf{S} \wedge -P\notin \textsf{S}$，即 $\textsf{S}$ 中存在一个与 $P$ 反对易的元素 $M$。注意到测量结果的期望是

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

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

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

接下来如何更新 $\textsf{S}$？$\textsf{S}’ = \textsf{S}(|\psi’\rangle)$，即全体使得 $|\psi’\rangle$ 是其特征值为 $+1$ 的特征向量的 Pauli 群元素。对于一个 $M\in \textsf{S}$，有

  1. 如果 $M$ 和 $P$ 对易，那么 $M|\psi’\rangle = |\psi’\rangle$ 源自平凡的计算，于是 $M\in \textsf{S}’$。
  2. 如果 $M$ 和 $P$ 反对易，那么 $M|\psi’\rangle = |\psi’\rangle$ 推出 $P|\psi\rangle = 0$（矛盾），于是 $M\notin \textsf{S}’$。

对于其他 Pauli 群中的元素，我们没有什么信息验证它是不是 $\textsf{S}’$ 的成员。然而我们可以转而计数与 $P$ 对易的 $M\in \textsf{S}$ 的数量，从而证明情况 1 和 $P$ 直积已然得到一个固定住 stabilizer state $|\psi’\rangle$ 的 stabilizer 集合：

引理 2.3. 令 $\textsf{S}$ 为一个 stabilizer，$P\notin \textsf{N}(\textsf{S})$，则 $\textsf{S}$ 中恰有一半元素与 ${P}$ 对易。

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

$\blacksquare$

这直接推出了 $\textsf{S}$ 中与 $P$ 对易的元素和 $(-1)^b P$ 并起来生成的 stabilizer $\textsf{S}’$ 和 $\textsf{S}$ 具有相同的大小：$2^n$。于是，stabilizer $\textsf{S}’$ 固定住唯一一个 stabilizer state。我们知道它固定住 $|\psi’\rangle$，所以 $|\psi’\rangle$ 就是 stabilizer state。

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

定理 2.4（Gottesman-Knill）. 若一个线路的作用于一个已知的 stabilizer 的 stabilizer state $\textsf{S}$，线路中仅包含以下三种要素：

  1. Clifford 门；
  2. Pauli 测量；
  3. 测量结果作为控制信号；

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

构造. 假设线路的初态是 stabilizer $\textsf{S}$ 的 stabilizer state，其中 $\textsf{S}$ 的生成元是 $M_1, …, M_n$，线路依次调用两种操作之一：

  1. $U_i$，一个 Clifford 群元素，并有定理 1.2.1 中的刻画 $U_i$；
  2. 对 $P_i \in P_n$ 做 Pauli 测量。

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

  1. 初始化，设 $k’ \leftarrow k$，$N_j \leftarrow M_j$（$j = 1, …, n - k$）；
  2. For 每一个操作：
  3. $\qquad$ If 当前操作是门 $U_i$：
  4. $\qquad\qquad$ $U_j \leftarrow U_i(\mathcal{N}_j)$；
  5. $\qquad$ If 当前操作是对 $P_i$ 测量，且 $\pm P_i \in \textsf{S}$（本步骤可调用二元辛形式上的线性基完成）：
  6. $\qquad\qquad$ 输出 $\pm 1$；
  7. $\qquad$ If 当前操作是对 $P_i$ 测量，且 $P_i \notin \textsf{N}(\textsf{S})$：
  8. $\qquad\qquad$ 均匀随机采样 $b$，返回 $(-1)^b$；
  9. $\qquad\qquad$ 在生成元中找 $M$ 使得其与 $\mathcal{P}_i$ 反对易；
  10. $\qquad\qquad$ 枚举 $i = 2, …, n - k’$，若 $[N_i, P_i] = 0$，保持其不变；否则 $N_i \leftarrow MN_i$；
  11. $\qquad\qquad$ $N_1 \leftarrow (-1)^b P$；
$\blacksquare$

Remark. 上述算法可以拓展到 $\textsf{S}$ 的大小为 $n - k$，其中 $k$ 为常数的情形。此时，还需要手动维护当前的态 $|\overline{\psi}\rangle$ 对应的 logical state $|\psi\rangle$、所有的逻辑操作。当 $P\in \textsf{N}(\textsf{S}) \setminus \textsf{S}$ 时，你需要找到 $P$ 对应哪个 logical operation $\overline{O}$，然后手动对 logical state 做 $O$ 基测量。因为 $k$ 是常数，所以你哪怕把 $O$ 和 $|\psi\rangle\langle\psi|$ 乘起来然后暴力算 trace，复杂度也是 $(2^{k})^3$（常数）的，这并不影响算法渐进复杂度。

算法时间复杂度为 $O(n^2 m)$。

Clifford 群生成元

本节证明如下定理：

定理 3.1. 设 $G\in \textsf{C}_n$。则 $G$ 可以被写成 $e^{\mathrm{i}\theta}I, H_i, R_{\pi / 4, i}, \operatorname{CNOT}_{i, j}$ 的乘积。

证明. 首先注意 Pauli 群和全局相位可以被 $O(1)$ 个 $e^{\mathrm{i}\theta}I, H_i, R_{\pi / 4, i}$ 生成：$Z = R_{\pi / 4}^2$，$X = HZH$。于是，我们只需要证明 $H_i, R_{\pi / 4, i}, \operatorname{CNOT}_{i, j}$ 生成了 $\check{\textsf{C}}_n$，后者同构于辛群。于是，写出这几个东西对应的共轭作用对应的线性映射 $M$：

$$
H\rightarrow \left(\begin{array}{c|c}
0 & 1 \\ \hline 1 & 0
\end{array}\right), \qquad
R_{\pi / 4} \rightarrow \left(\begin{array}{c|c}
1 & 0 \\ \hline 1 & 1
\end{array}\right), \qquad
\operatorname{CNOT} \rightarrow \left(\begin{array}{cc|cc}
1 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
\hline
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{array}\right)
$$

要证明的是任何一个 $2n\times 2n$ 的 $0/1$ 辛矩阵：

$$
\mathbf{U} = \left(\begin{array}{c|c}
\mathbf{A} & \mathbf{B} \\
\hline
\mathbf{C} & \mathbf{D}
\end{array}\right) \quad \text{s.t.} \quad \begin{array}{l}
\text{1. $\mathbf{U}$ has full rank;} \\
\text{2. $\mathbf{A}^\top \mathbf{C} + \mathbf{C}^\top \mathbf{A} = 0$} \\
\text{3. $\mathbf{C}^\top \mathbf{B} + \mathbf{A}^\top \mathbf{D} = I$} \\
\text{4. $\mathbf{B}^\top \mathbf{D} + \mathbf{D}^\top \mathbf{B} = 0$} \\
\end{array}
$$

都可以表示成这些东西的乘积。这三个矩阵的形式让人联想到初等变换：以左乘为例

  1. 左乘 $H$ 交换上半部分第 $i$ 行和下半部分第 $i$ 行；
  2. 左乘 $R_{\pi/4}$ 让上半部分第 $i$ 行加到下半部分第 $i$ 行；
  3. 左乘 $\operatorname{CNOT}$ 将上下半的第 $i$ 行同时分别加到对应半区的第 $j$ 行。

此外还可以补充一些辅助操作：

  1. $\textsf{c-}Z = (I\times H)\operatorname{CNOT}(I\times H)$，将上半部分的第 $i$ 行加到下半部分的第 $j$ 行，将下半部分的第 $i$ 行加到上半部分的第 $j$ 行；
  2. $\operatorname{SWAP}_{i, j} = \mathrm{CNOT}_{i, j}\mathrm{CNOT}_{j, i}\mathrm{CNOT}_{i, j}$：分别交换上下两半的 $i, j$ 行。

当然，右乘对应的列操作。用这些操作来构造一切辛矩阵的算法是一个相当显然的变体高斯消元，读者可以自行想象，这里不再赘述，操作数量仅为 $O(n^2)$。

$\blacksquare$

Remark. 一些现代科技可以让这个复杂度除一个 $\log n$。

用 Clifford 电路实现稳定子码的 Encoder

可以看到 Clifford 可以实现 stabilizer 集合之间的变换。而 Encoder 实际上做的是这样一件事情：

  • 一个 Encoder $U$ 把任意的 $|0\rangle^{\otimes (n - k)}|\psi\rangle$ 映射到 $|\overline{\psi}\rangle$（其中 $|\psi\rangle\in \mathcal{H}_{2^k}$）。
  • 前者被生成元为 $Z_1, …, Z_{n - k}$ 的 stabilizer 稳定住。后者被 $M_1, …, M_{n - k}$ 的 stabilizer 稳定住。这要求 $U$ 的共轭作用把 $Z_i$ 映射到 $M_i$。
  • 如果你还想要保证编码之后，对 $|\psi\rangle$ 的操作 $X_i, Z_i$ 恰好还对应对 $|\overline{\psi}\rangle$ 的逻辑操作 $\overline{X}_i, \overline{Z}_i$，这还要求 $U$ 给出的共轭作用把 $X_i$ 映射到 $\overline{X}_i$，把 $Z_i$ 映射到 $\overline{Z}_i$。

上述要求直接给出了 $U$ 的共轭作用的辛矩阵，用上一节中的变体高斯消元必然可以将其转化为一个 Clifford 门组成的线路。

补充材料

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

  • 发表于 FOCS’99 的文章 On Universal and Fault-Tolerant Quantum Computing 证明了 Clifford 群加上任意一个群外元素都构成通用量子门集合，现实中常用 Clifford + Toffoli 或者 Clifford + T；但这些门也构成量子纠错的主要开销。
  • Solovay-Kitaev 定理告诉我们怎么将一个线路以较小代价编译到一个通用的门集上去。