Gottesman–Knill 定理与稳定子模拟

形式陈述

取整数 $n\ge1$ 。输入纯稳定子态以 $n$ 个独立带符号生成元的表给出；Clifford 操作以 $H,S,\mathrm{CNOT}$ 电路给出，或先提供其多项式规模的这类分解。从这个输入开始，允许Clifford 门、Pauli 测量、稳定子辅助态初始化，以及依赖已有测量结果的高效经典前馈。对这样的多项式规模电路，Gottesman–Knill 定理保证存在经典多项式时间算法，按其真实分布采样测量输出。[1,2]

纯稳定子态是稳定子码中逻辑维数为1的情形：由 $n$ 个独立、两两对易、不生成 $-I$ 的 Hermitian Pauli $g_1,\ldots,g_n$ 唯一指定。它们的共同 $+1$ 本征态就是当前状态。

每行可写为

g=(-1)^r i^{x\cdot z}X^xZ^z, \qquad x,z\in\mathbb F_2^n,\quad r\in\mathbb F_2.

$x\cdot z$ 在指数中按整数求和。这一约定使每个局部 $(x_j,z_j)=(1,1)$ 对应 $Y$ ， $r$ 记录真正的整体正负号。 $n$ 行只需 $n(2n+1)=O(n^2)$ bit。

定理模拟的是采样任务和指定 Pauli 测量概率，不要求在多项式时间列出全部 $2^n$ 个振幅。经典前馈自身也要高效；若把难问题藏进控制程序，就不能把它的代价忽略。

直觉

一般态向量可能需要指数多个复数；稳定子态却可由“这 $n$ 个问题的答案都为 $+1$ ”紧凑指定。Clifford 门只改写问题，Pauli 测量要么答案已由现有问题确定，要么产生一个新的公平随机答案并替换一个旧约束。

所以模拟器的主要动作是二元表格更新、带相位的行相乘和消元。纠缠并不会破坏这套描述，Bell 态就是最简单的例子。

从00态的ZI与IZ出发，H与CNOT把生成元变成XX与ZZ；测量Z1后随机分成正号和负号两支，第二位Z的结果由同一符号确定。

例子与边界

三种基本门的逐行更新

下表对每一稳定子行执行。所有右侧值都取门更新前的值， $\oplus$ 为模二加法：

门	相位位更新	坐标更新
$H_a$	$r\leftarrow r\oplus x_az_a$	交换 $x_a,z_a$
$S_a$	$r\leftarrow r\oplus x_az_a$	$z_a\leftarrow z_a\oplus x_a$
CNOT $a\to b$	$r\leftarrow r\oplus x_az_b(x_b\oplus z_a\oplus1)$	$x_b\leftarrow x_b\oplus x_a$ ， $z_a\leftarrow z_a\oplus z_b$

这些规则由 Pauli 共轭表推出。尤其不能只更新 $x,z$ 而丢掉 $r$ ；例如 $H$ 把 $+Y$ 变成 $-Y$ ，其二元坐标没变，变化全在相位位。

行相乘时同样要保留 $XY=iZ$ 、 $YX=-iZ$ 等相位。对本来相互对易的 Hermitian 稳定子行，乘积最后仍为 Hermitian Pauli，其总相位为 $\pm1$ ；若只对两组比特做异或，通常无法得到正确符号。

测量有反对易生成元：抛一枚公平硬币

测 Hermitian Pauli $M$ 。若某个生成元 $g_p$ 与 $M$ 反对易，则

\langle M\rangle=\langle g_pMg_p\rangle=-\langle M\rangle=0.

因此 $\pm1$ 两结果各占 $1/2$ 。抽取公平位 $b$ ，结果为 $(-1)^b$ 。对其余所有与 $M$ 反对易的行，先作 $g_i\leftarrow g_ig_p$ ；最后把第 $p$ 行换成 $(-1)^bM$ 。

旧行相乘后与 $M$ 对易，而且仍保留投影后的态；新行则强制本次测量本征值。其余行不变。这样仍得到 $n$ 个独立对易生成元，正是测量后的纯态。

测量与所有生成元对易：答案已经确定

$n$ 个独立生成元指定纯态，构成最大对易 Pauli 子群。因此与它们全部对易的 $M$ 必为该群元素的正号或负号。

对 $(x,z)$ 做二元消元，找到生成元乘积的系数，再实际相乘核对符号。如果乘积为 $M$ ，结果确定为 $+1$ ；若为 $-M$ ，结果为 $-1$ ，状态无需改变。这里也包括 $M=\pm I$ 。

Bell态的完整测量路径

初态 $|00\rangle$ 可用 $ZI,IZ$ 表示。施 $H_1$ 后为 $XI,IZ$ ；再施 CNOT $1\to2$ 后为 $XX,ZZ$ 。

现在测 $Z_1=ZI$ ，它与 $XX$ 反对易，故抽公平位 $b$ 。更新后的生成元可写为

(-1)^bZI,\qquad ZZ.

二者乘积给 $(-1)^bIZ$ ，所以再测 $Z_2$ 必得到同一位 $b$ ：两位结果为00或11，各占一半。重测 $Z_1$ 也确定为 $b$ ，不会再抽一枚独立硬币。

推论与应用

逐个基本 Clifford 门更新 $n$ 行，每门用 $O(n)$ 次 bit 操作；判断一般 Pauli 测量的对易性和随机分支行更新需 $O(n^2)$ 。若确定分支每次从头作朴素二元高斯消元，可保守计为 $O(n^3)$ ，因此 $T$ 步电路可在 $O(Tn^3)$ 时间、 $O(n^2)$ 存储内模拟。

Aaronson–Gottesman 算法额外保存 $n$ 行 destabilizer，把确定测量也降到二次量级，代价是约加倍表格行数。[1] 两种版本都已经证明多项式可模拟性，不能把改进版复杂度无说明地算给只存稳定子行的朴素算法。

非稳定子输入、 $T$ 门或一般非 Pauli 测量，会破坏上述闭包。例如对 $|+\rangle$ 施 $T$ 得到的魔术态没有单个 Pauli 的确定本征值，不能继续用一行纯稳定子表描述。

测量后的自适应 Clifford 操作不构成障碍：模拟器已经生成相同分布的经典结果，可以按同一控制规则选择下一门。另一方面，对极罕见后选择事件的条件分布进行高效采样不是本定理自动附送的保证，重复拒绝采样的成本仍要计入接受概率。

参考资料

[1] Scott Aaronson and Daniel Gottesman, Improved Simulation of Stabilizer Circuits, Physical Review A 70, 052328, 2004，§§II–III：带相位tableau、rowsum与测量分支。
[2] Daniel Gottesman, Surviving as a Quantum Computer in a Classical World, 2024 draft，§6.2：稳定子电路经典模拟。

形式陈述 ​

三种基本门的逐行更新 ​

测量有反对易生成元：抛一枚公平硬币 ​

测量与所有生成元对易：答案已经确定 ​

Bell态的完整测量路径 ​

反向链接

形式陈述

三种基本门的逐行更新

测量有反对易生成元：抛一枚公平硬币

测量与所有生成元对易：答案已经确定

Bell态的完整测量路径