译者按：

稳定子体系由戈特斯曼于1996年提出，并很快在量子纠错和容错计算理论中发挥了巨大作用。

戈特斯曼1998年在第22届“物理学中的群论方法”国际会议上关于此主题做了演讲。本文是演讲内容的修订稿，详细介绍了稳定子体系的理论框架以及在量子信息方面的诸多应用。文中给出了许多妙趣横生的实例，很值得细细玩味。文末甚至预言了稳定子体系在量子计算方面的可能用途。

的确，近年来这一体系在并行测量与变分电路的预处理方面开始展露威力。现将全文翻译如下，供大家参考。

摘要

自从肖尔发现在量子计算机上以多项式时间分解数字的算法以来，量子计算成为了人们热衷的主题。

可惜的是，量子计算机的关键特性之一——难以用经典计算机来描述——也使得精确地刻画和理解它们的能力变得很困难。

比起态的演化，描述算符演化的一种体系事实上在理解一类重要的量子操作时是非常有成效的。

在纠错和某些通信协议中使用的态可以用它们的稳定子，也就是泡利矩阵张量积构成的一个群，来描述。哪怕这么简单的一个群结构已经足以体现众多丰富的量子效应，尽管它还实现不了量子计算的全部威力。

正文

01. 引言

计算机是物理对象。这看上去显而易见，但却有着深刻的影响。

日常所用的台式机和笔记本电脑，以及它们的大兄弟，主机，运行方式本质上都是一样的。它们的元件是所谓比特的单个寄存器，而比特通过各种被称为门的离散操作互动。底层的硬件在不同系统之间会有所变动，但目前来说，所有的比特都是由数目相当庞大的原子组成的。因此，它们表现得像宏观的经典对象。现代计算机是数字的，因而它们的比特取0和1的离散值（所以才叫“比特”）。

可是，假如我们拥有的是这样一种计算机，它的比特是由几个原子构成的，甚至就是一个原子。那么计算机里的比特就会表现得更像量子对象，而不是经典对象。比特不再只取单个的0和1值，或许还会是0和1的某种叠加。

可以处在这样一种叠加中的比特被称作量子比特，或者量子位。如果一台经典计算机有N个比特，总共就会有 2^N 种可能的态。相反，一台具有N个量子比特的量子计算机可以处在这 2^N 个经典基矢态的任意叠加上，给出 2^N -维希尔伯特空间中的一个任意态。在一台经典计算机上哪怕描述这样一个态也需要 2^N-1 个复数。

经典算法经常用多项式的和指数的（实际上只是意味着超出多项式的）来分类。

一个多项式算法解决一个大小为N的问题需要 CN^k 步（加上一些低阶项），其中C和k是常数。这种算法被认为在处理大型问题时是有效的，因为计算代价随着N变大增长得不是太多（尽管如果C和/或k很大的话，算法对于解决实际问题可能没什么用）。与此相反，指数时间算法意味着它很难解决大型问题。

不幸的是，许多重要问题都没有找到多项式算法，从而迫使我们求助于近似，或是将我们限制在小的问题规模上。

只要我们使用的是根本上经典的比特，那么我们采用的算法大致都是等价的。或许一个体系比另一个差了一个N因子的步数，又或者C有些出入，但一台经典计算机上的指数算法放到任何其它的经典计算机上还会是一个指数算法。

不过，如果我们改变底层的物理定律，用量子比特来代替经典比特，那么情况会有所改变。对于求解一个问题哪怕没有多项式的经典算法，依旧可能存在多项式的量子算法。

对此最激动人心的已知实例或许是肖尔的因子化算法。因子化一个n-比特的数字是相当困难的，特别是当这个数字是两个差不多大小的素数的乘积时。尽管人们做了大量研究，还是没能找到一个多项式的经典算法。实际上，许多经典加密协议，例如RSA，是基于因子化难以实现这一事实的。

归根到底，因子化一个数N本质上（在相差一些简单的额外运算意义上）等价于找到一个任意的数x模N的阶r。

在量子计算机上，我们可以这样来做，先从叠加态 \sum{|a} 开始，然后在第二个寄存器上计算 x^a 模N，得到态 \sum{|a|x^a} 。这个态关于a是周期性的，并且周期为r。因此，通过实施离散傅里叶变换并测量结果，我们可以提取出r并进而因子化N。其结果是一个多项式的量子算法，而所有已知的经典算法都是指数的。

遗憾的是，由于量子计算机处理的是如此庞大的希尔伯特空间中的任意态，构建和分析哪怕相对较小的量子门网络也是非常困难的。

不过，其实有一类受限的网络可以相对容易地刻画，如果我们追踪的不是量子计算机的态的演化，而是可以作用在计算机上的一个算符集的演化。在某种程度上，这跟量子力学的标准海森堡表示类似，其中算符随时间演化，而不像薛定谔表象中态在演化。

类似的但没这么强力的技术已经被NMR（译注：核磁共振）同行们使用了很多年，并被称为“算符乘积体系”。也有人强化算符乘积体系并应用到量子计算中。

02. 海森堡表示基础

假定量子计算机处在态 ∣ψ ，然后我们作用算符U。于是

UN∣ψ=UNU^{\dagger}U∣ψ (1)

所以在操作后，算符 UNU^{\dagger} 以与之前的算符N一样的方式作用在态上。因此，在计算机上作用U会将一个任意操作N变换成

N{\rightarrow}UNU^{\dagger} (2)

通过追踪足够大的N集合的演化，可以完全重构出态矢量的演化。演化（2）是线性的，因此追踪n×n矩阵集合 \mathcal{M}_n 的一个生成集合就足够了。

我们将这一集合选为泡利群 \mathcal{P} ，它包含4×4n元素。泡利群包含单位矩阵I和泡利矩阵 σ_x ， σ_y 和 σ_z ：

σ_x=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, σ_y=\begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, σ_z=\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}

的4n种n-量子比特张量积。注意 σ_x^2=σ_y^2=σ_z^2=I

以及 σ_y=iσ_xσ_z

因此，为了使群完备化，我们必须容许这4n种张量积每个都带有一个全局相位±1或±i。下面，我会把 σ_x ， σ_y 和 σ_z 写成X，Y和Z（原注：在早期文献中，Y反而等于 -iσ_y ）。算符 X_i ， Y_i 和 Z_i 就是作用在计算机第i个比特上的X，Y和Z。

此外，演化（2）是一个相乘性的群同态：

MN→UMNU^\dag=(UMU^\dag)(UNU^\dag)

因此，我们只需要追踪一个生成集的演化就可以推导出任意泡利群元素的行为。一个便利的生成集就是 {\lbrace}X_1,...,X_n,Z_1,...,Z_n{\rbrace} 。为了完全刻画一个一般的算符，只需要描述2n个单比特算符的演化就够了。

03. 克利福德群

现在，一般来说，变换（2）会把一个泡利矩阵N变成相当大一类幺正算符中的任一个。如果考虑任意量子门，对生成集变换的描述很快就会大到难以处理。于是，我们考虑一类受限的门——将泡利群元素变换为其它泡利群元素的门。

让群 \mathcal{P} 在共轭下不变的算符集构成一个群 N(\mathcal{P}) ， \mathcal{P} 在 U(2^n) 中的正规化子。因为与通常的克利福德群和克利福德代数的关联， N(\mathcal{P}) 也被称为克利福德群 \mathcal{C} 。尽管 \mathcal{C} 比整个幺正群 U(2^n) 小了相当多，它依旧包含了不少特别有趣的算符。

例如，克利福德群包含单比特阿达马变换R（译注：现在一般记作H）：

R|j=|0+(-1)^j|1,R=\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}

另一个元素是相位门P（译注：现在一般记作S）：

P|j=i^j|1,P=\begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}

它还包含受控-非（CNOT）门，也被称为异或（XOR）：

CNOT|j|k=|j|j+{k\mod 2}

第一个量子比特被称为控制比特，而第二个被称为目标比特。

事实上，R、P和CNOT，作用在任意量子比特或量子比特对上时，生成了完整的克利福德群 \mathcal{C} 。这三个门在泡利矩阵上诱导的变换在表1中给出。这个表也给出了在门网络中表示克利福德群操作的符号，以及测量的符号。

如果我们对第j号量子比特作用R或P，我会以R(j)或P(j)来表示。如果我们以量子比特j为控制，k为目标作用CNOT，我会写成CNOT(j→k)。

04. 应用海森堡表示

为了看出如何应用海森堡表示，我们考虑以下例子：

例1 爱丽丝的量子计算机运作得过于良好。它不是单个地执行受控-非门，而是一次执行了三个（图1a）。它到底在做什么？

为了弄清这一点，我们来追踪四个算符 {\overline{X}}_1 、 {\overline{X}}_2 、 {\overline{Z}}_1 和 {\overline{Z}}_2 的演化。算符上的横杠暗示这些算符代表着计算开始时的逻辑算符 X_1 、 X_2 、 Z_1 和 Z_2 。这一术语使得在整个电路中追踪它们的演化变得更加容易。

首先考虑 {\overline{X}}_1 。它在计算开始时是 X_1=X{\otimes}I 。在第一个CNOT之后（A），它变成了 X{\otimes}X ，如表1所示。可以将之写成 (X{\otimes}I)(I{\otimes}X) ，因此步骤B（CNOT(2→1)）将 {\overline{X}}_1 变到 (X{\otimes}I)(X{\otimes}X)=I{\otimes}X 。

接着经过步骤C，我们还是得到 I{\otimes}X ，所以整个电路给出映射 {\overline{X}}_1=X{\otimes}I→I{\otimes}X 。

我们可以对 {\overline{X}}_2 、 {\overline{Z}}_1 和 {\overline{Z}}_2 做类似的计算。完整的计算汇总在图1b里。图1a的网络做了交换 X_1X_2 和 Z_1Z_2 。因此，它交换了第一个和第二个量子比特。

例2 鲍勃的量子计算机上的控制杆卡在了“向前”位，所以它只能从量子比特1到2执行受控-非门。他仍可以正常执行单比特门。他如何执行从量子比特2到1的受控非门呢？

要解决这个问题，关键是看出CNOT门的对称行为。如果交换X和Z门，以及量子比特1和2，我们会回到最初的变换。因此，图2a如同CNOT(2→1)一样作用。电路分析在图2b中给出。我们可以看出最终结果跟CNOT(2→1)一样，因此可以得出结论：给定的电路的确生成了所需的门。

例3 鲍勃尝试阅读一篇用古赫梯语写的文章。他唯一能弄清的是一个门网络，见图3a。这个网络做了什么？

分析在图3b中给出。注意其中出现的两个负号。例如，在步骤C中，对于 {\overline{X}}_2 ，我们得对Y作用R。但是

R(Y)=R(iXZ)=iR(X)R(Z)=iZX=-Y 。

总而言之，通过整个网络，我们得到步骤D给出的变换。

为了切换回态矢体系，我们可以追踪基矢态。例如，初始态 |00 作为 Z{\otimes}I 和 I{\otims}Z 的本征态出现，本征值均为+1。因此，在网络之后，它仍会是 {\overline{Z}}_1=-Y{\otimes}Y 和 {\overline{Z}}_2=-Z{\otimes}X 的+1本征矢量。于是，我们推导出这一网络映射

|00\rightarrow\frac{1}{2}(|00+|01-|10+|11) 。

此外， |01=(I{\otimes}X)|00 ，所以 |01 会映射成 {\overline{X}}_2 作用在 |00 的像上。而 {\overline{X}}_2=-I{\otimes}Y ，

|01\rightarrow\frac{i}{2}(-|01+|00+|11+|10) 。

我们可以类似地找出 |10 和 |11 的像。把它们全放在一起给出下面的幺正矩阵

U=\dfrac{1}{2}\begin{pmatrix} 1 & i & 1 & i \\ 1 & -i & 1 & -i \\ -1 & i & 1 & -i \\ 1 & i & -1 & -i \end{pmatrix}

这不对应到任何已知的操作，所以赫梯人用它做什么只能是一个谜了。

05. 稳定子例4

大费周章之后，爱丽丝终于部分地修好了她的量子计算机。现在它一次只做2个CNOT门了。可惜的是，只有在第二个量子比特输入 |0 态时她才能得到这一改善。现在它做了什么？

这一网络的输入态始终是 I{\otimes}Z 的+1本征矢。因此，系统的态会始终是 {\overline{Z}}_2 的+1本征矢。既然 {\overline{Z}}_2 的本征值固定了，也就没必要再追踪 {\overline{X}}_2 的演化了，因为它的作用会把态变到无关的 {\overline{Z}}_2 的-1本征矢上。对这个电路完整的分析在图4b中给出。

这一分析的格式有了些微的变化。计算机的态为+1本征矢的那些算符不再标出——在这个例子中，是 {\overline{Z}}_2 。此外，在标记的算符中我们也只追踪 {\overline{X}}_1 和 {\overline{Z}}_1 ，并把它们简记为 \overline{X} 和 \overline{Y} 。

最终结果可能没法一眼看懂。我们可以看出来这个态是 Z{\otimes}I 的+1本征矢，所以第一个量子比特是 |0 。既然 Z{\otimes}I 作用在计算机所有可能末态上都相当于恒等元，也就意味着 \overline{Z}=Z{\otimes}Z 等价于 (Z{\otimes}I)(Z{\otimes}Z)=I{\otimes}Z。因此，

\overline{X}{\rightarrow}I{\otimes}X ，

\overline{Z}{\rightarrow}I{\otimes}Z 。

换句话说，原来的第一个量子比特已经转移到了第二个上。爱丽丝的计算机依旧执行了第一个和第二个量子比特的交换。

在前一个例子中，只有单个量子比特有固定的输入值，但更一般地，多个量子比特可以固定或加以限制。跟上面一样，考虑 \mathcal{P} 中使得输入态为+1本征矢的算符集是很有帮助的。这类算符的集合在乘积下是封闭的，因而形成一个群，被称为稳定子S。

S={\lbrace} M∈\mathcal{P}{\rbrace} ，使得 M|\psi=|\psi 对所有允许的输入 |\psi 均成立。

在前一个例子中，稳定子只含有两个元素： I{\otimes}Z 和恒等元 I{\otimes}I 。

稳定子一定是一个交换群：如果 M,N∈S ，那么

MN|\psi=|\psi

NM|\psi=|\psi

[M,N]|\psi=0 。

\mathcal{P} 的任意两个元素要么对易，要么反对易，所以这导出M和N对易。此外， \mathcal{P} 的任何元素平方为±1（整体相因子为±1的算符平方后为+1，而整体相因子为±i的算符平方为-1）。平方为-1的算符具有虚本征值，而平方为+1的算符本征值为±1。因此，任何稳定子都是由 \mathcal{P} 中整体相因子为±1，也就是平方后为+1的算符组成的。由此可以得出，对于某个k，S同构于 (\bold{Z}_2)^k 。

事实上，k恰好是被固定的输入量子比特的数目。单个量子比特被固定的要求提供了稳定子中的单个算符。于是k个算符共同生成了S——S的 2^k 个元素就是这些生成元的乘积。

那些还保有神秘的泡利群算符则作用在其它n-k个量子比特上（如果量子比特总数是n）。总共有2(n-k)个独立的这种算符。当稳定子在态上施加更加复杂的限制时，这些 \overline{X} 和 \overline{Z} 算符是与S对易的任意2(n-k)个算符。

例5 爱丽丝的量子计算机终于修好了。她想表明对鲍勃的挚爱，于是寄给他一个贝尔态的一半，并附上一张写有“永远相伴”的卡。她执行了图5a的网络，并将卡片和第二个量子比特寄给了鲍勃。

网络的分析呈现在图5b中。在此情况下，我们只需考虑稳定子的元素。再一次地，稳定子的生成元没有标记。它们的顺序无关紧要——我们可以交换生成元，它们依旧生成同样的群。事实上，我们可以将一个或多个生成元跟S中的其它元素做交换而不带来任何影响，只要我们依旧有n个独立的算符作为生成元。稳定子中其余元素的变换完全由生成元的变换决定。

这个例子中的末态具有稳定子 {\lbrace}I{\otimes}I, X{\otimes}X, -Y{\otimes}Y,Z{\otimes}Z {\rbrace} 。只有唯一的一个态在这四个算符作用下都具有本征值+1。（相差归一化因子下）它由下式给出

这是正确的态，因为用N∈S作用上去只会交换求和项的顺序，给出同一个态。（原注：如果稳定子中是 -Z{\otimes}Z 而非 Z{\otimes}Z ， |\psi 会是空态。为了产生正确的态，我们需要在右边从不同于 |00 的某个态开始。）此时，这个态是 \dfrac{1}{\sqrt{2}}(|00+|11) ，确实是贝尔态。

通过指定稳定子能够完整刻画的态称为稳定子态。希尔伯特空间中有许多态并非稳定子态（事实上，给定规模下仅有有限个稳定子态），但许多有趣的态都是稳定子态。

例6 爱丽丝想要换成单重态寄出，但又不想再重做一次CNOT操作。她如何将已有的态制成单重态？

单重态是 \dfrac{1}{\sqrt{2}}(|01-|10) 。

它具有稳定子 {\lbrace} I{\otimes}I, -X{\otimes}X,-Y{\otimes}Y,-Z{\otimes}Z{\rbrace} （由 -X{\otimes}X和 -Z{\otimes}Z 生成）。这跟她现在的稳定子很相似（由 X{\otimes}X 和 Z{\otimes}Z 生成）。她所需要做的是作用一个算符来得到映射 X{\otimes}X{\rightarrow}-X{\otimes}X 和 Z{\otimes}Z{\rightarrow}-Z{\otimes}Z 。

一个可能的算符是 Y{\otimes}I ，

Y(X)=YXY^\dagger=-YY^{\dagger}X=-X ，

Y(Z)=YZY^\dagger=-YY^{\dagger}Z=-Z 。

另一种可能是 I{\otimes}Y 。 X{\otimes}Z 也同样有效：

(X{\otimes}Z)(X{\otimes}X)(X{\otimes}Z)=-X{\otimes}X ，

(X{\otimes}Z)(Z{\otimes}Z)(X{\otimes}Z)=-Z{\otimes}Z 。

事实上，跟 X{\otimes}X 和 Z{\otimes}Z 反对易的任何算符 E∈\mathcal{P} 都可行：如果{E,M}=0，那么

E(M)=EME^\dagger=-EE^{\dagger}M=-M 。 (30)

06. 量子纠错码

例7 爱丽丝和鲍勃有时会把量子数据随身带回家。他们两岁的孩子小爱丽丝很好奇。哪怕数据存放在一个很高的架子上，小爱丽丝有时也能够到。当她够到时，会把单个量子比特放进嘴里，随机化它，再放回去。之后，她失去了兴趣，又跑到别的地方捣乱去了。爱丽丝和鲍勃如何判断小爱丽丝是否扰乱了他们的态？如果态是好的他们并不想毁掉它，但如果它已经被改变了，他们愿意将它抛弃。

爱丽丝和鲍勃不能直接测量他们的量子态，因为那会导致它可能处在的任意叠加坍缩掉。与此不同，解决办法是将量子比特分成两个集合。对于每个对，他们增加处于已知态的两个量子比特，并采取一些操作使得稳定子S由下式生成
X{\otimes}X{\otimes}X{\otimes}X

Z{\otimes}Z{\otimes}Z{\otimes}Z 。 (31)

比如，他们可以采用图6中的电路。

稳定子(31)有一个优点，任意单量子比特算符都跟至少一个生成元反对易。因此，如果我们作用由任意单量子比特算符 E∈\mathcal{P} 形成的错误，至少一个生成元会改变符号，就跟(30)式一样。因此我们可以通过测量S的生成元来探测E是否发生了。如果本征值是+1,则没有错误发生（或者两个以上错误发生了）。

当然，随机化一个量子比特一般来说并不对应于作用 \mathcal{P} 中的一个算符。不过， \mathcal{P} 确实生成了矩阵集，因此最一般的错误会是 \mathcal{P} 中算符的求和。这样一个错误会使得态处在S本征态的叠加上，而测量S的生成元将态坍缩到一个本征态上。其效果是，将错误坍缩为 \mathcal{P} 中的某个算符。

由（31）描述的态构成一种可以探测单比特错误的量子探错码。一种码如果可以探测影响比特数小于d的任意错误，则称它的距离为d。因此这个四量子比特码的距离为2。由于这种码完全由其稳定子决定，所以被称为稳定子码。

例8 爱丽丝和鲍勃想把一些特别重要的量子数据带回家。他们制备它的时候非常不容易，所以哪怕小爱丽丝毁坏了单个量子比特也不愿丢弃它。他们应该怎么做？

现在，爱丽丝和鲍勃得把探错码提升为一种量子纠错码。不过，原理依旧是一样的。为了纠正单个错误，爱丽丝和鲍勃只要能准确地找出错误是什么就足够了。由于它在 \mathcal{P} 里（或是已被坍缩到 \mathcal{P} 里的错误），他们可以接着执行逆操作来恢复原始态。

区分 E|\psi 与 F|\psi 跟区分 EF|\psi （原注：或者更准确地说， E^{\dagger}F|\psi ，当E厄米时这是一样的）与 |\psi 是同一个问题。因此，探测错误EF的码会区分错误E和F。换句话说，要纠正任意单比特错误，码必须探测所有双比特错误。更一般地，要纠正t位任意错误，码必须具有距离2t+1。

修复单比特错误的最小纠错码的稳定子在表2中给出。它将单个量子比特编码在五个量子比特中，并且距离是3。我们说它是一种[5,1,3]量子码（或者[[5,1,3]]码）。

\overline{X} 和 \overline{Z} 算算符跟之前一样，对应着作用在原始数据量子比特上的逻辑算符。通过分析它们的行为，我们可以，比如说，无需先解码出态就能弄清如何在数据上执行操作（容错操作）。

我前面说过，如果对于每一个权重小于d的泡利群算符E,都存在稳定子中的一个元素M与E反对易，则称该稳定子码具有距离d。事实上，这一条件稍微弱了点。也有可能对于所有码字 |\psi ，存在某个特别的E，使得 E|\psi=|\psi 。在此情形下，该码没法探测出E是否发生了——但也没必要这么去做，因为产生的态就是正确态。如果 E|\psi=|\psi,\forall|\psi ，那么 E∈S 。因此，稳定子码具有距离d的完整条件是，要么 {\exists}M∈S 使得{M,E}=0，要么 E∈S 。如果第二个条件用上了，就说该码是简并的。如果第二个条件没有用到，如同上面的四量子比特码和五量子比特码，就说该码是非简并的。

量子纠错码解决了量子计算机设计中的一个重大难题。只有展现大致量子行为的对象不足以生成一台量子计算机。如果量子比特跟环境相互作用，它会趋向于处在某个基矢态上（对于某组特别的基，而这依赖于相互作用），就如同它被测量了一样。因此一台跟环境强烈相互作用的量子计算机会趋向于处在 2^N 个基矢态之一上——换句话说，它会表现得就像一台经典计算机。利用量子纠错和容错操作，我们可以大幅度简化我们的任务：我们无需构建一台跟环境几乎没有不可控相互作用的的量子计算机，而仅仅需要让它的相互作用足够小，使得我们有时间执行纠错。（原注：仅仅。你能说我是个理论家吗？）

07. 测量

例9 鲍勃撞到了头，想不起来怎么执行P门。幸运的是，他还记得怎么操作CNOT，泡利群，以及测量泡利群中的算符。他如何制备一个P门？

解决办法在图7a中给出。完整的分析呈现在图7b中。如果初始态是

|\alpha=a|0+b|1 ，那么完成步骤A后的态是

a|00+b|11=\frac{1}{2}(a|0-ib|1)(|0+i|1)+\frac{1}{2}(a|0+ib|1)(|0-i|1) 。

因此，测量 I{\otimes}Y 要么会给出态

(a|0-ib|1)(|0+i|1) ，

要么给出态

(a|0+ib|1)(|0-i|1) 。

前者具有稳定子 I{\otimes}Y ，并且 \overline{X}=-Y{\otimes}I ，而后者具有稳定子 -I{\otimes}Y ，并且 \overline{X}=+Y{\otimes}I 。在两种情况下，都有 \overline{Z}=Z{\otimes}I 。测量后的这两种可能态通过算符 Z{\otimes}Z 的作用关联在一起。注意 Z{\otimes}Z 是步骤A之后的稳定子。

因此，步骤B由测量 I{\otimes}Y 并在结果为-1时执行 Z{\otimes}Z 组成。这得出表中的最终态。既然 I{\otimes}Y 在稳定子中，对于关心的态来说 Y{\otimes}Y 等价于 Y{\otimes}I 。我们可以将最终操作识别为 P^\dagger 门。要得到一个常规的P门，可以重复三次这一操作，或者更简单一点，在输出量子比特上作用一次Z。

我们能够将+1和-1的测量结果转换到同一个态并非侥幸。一般地，假定我们的态部分地（或者完全地）由稳定子S描述。假定我们想测量跟某个元素 M∈S 反对易的一个算符 A∈\mathcal{P} 。依赖于测量结果的±1，这一测量作用下面的两个算符之一

P_\pm=\frac{1}{2}(I{\pm}A) 。

但是

MP_-M^\dagger=\frac{1}{2}M(I-A)M^\dagger=\frac{1}{2}(I+A)MM^\dagger=P_+ 。

因此，一旦测量结果为-1就作用M，我们可以确保总是得到态 {P_+}|\psi 。

我们可以更进一步，用海森堡体系来描述态的演化。态 {P_+}|\psi 始终是A的+1本征态，所以A是新的稳定子S'的成员。相反，M会在S'中了。其它的生成元如果跟A对易会在S'中，因为对易的观测量可以有共同本征矢。反之，如果 N∈S 与A不对易，则 N\notin{S} ；但MN倒是跟A对易，所以 MN∈S' 。

我们还可以追踪算符 \overline{X} 和 \overline{Z} 的演化。如果它们跟A对易，则不会被A的测量所影响。我们最初对 {\overline{X}}_j 或 {\overline{Z}}_j 的表示可能跟A不对易，但注意作用在态上的算符在乘以稳定子元素的情况下是等价的。因此，哪怕 {\overline{X}}_j 跟A不对易， M{\overline{X}}_j 可以，并且作用一样。于是，在测量下， {\overline{X}}_j=M{\overline{X}}_j 。

我们将测量A（并在结果为-1时加以修正）后算符演化的规则总结如下：

1-找出满足{M,A}=0的M∈S；

2-将M从稳定子中移除；

3-将A加入到稳定子中；

4-对于每个N，让N跑遍S的其它生成元以及 \overline{X} 和 \overline{Z} 算符，当[N,A]=0时，保持N不变；当{N,A}=0时，用MN替换掉N。

例10（量子隐形传态） 爱丽丝想要快递一个量子比特给鲍勃，但是量子快递公司（QPS）在罢工。幸运的是，爱丽丝跟鲍勃共享着一个EPR对，并且常规的经典电话线路依旧是通。她怎样才能把量子比特给他？

这一难题的答案是量子隐形传态。在海森堡表示下分析是直截了当的。我假定爱丽丝和鲍勃从贝尔态|00+|11 出发。网络在图8a中给出。爱丽丝和鲍勃开始时有一个EPR对。爱丽丝和鲍勃执行了一些局域操作，并且在过程中爱丽丝传给鲍勃两个经典比特。总的后果是爱丽丝的量子比特传给了鲍勃。海森堡表示下的分析在图8b中给出。爱丽丝传给鲍勃的两个经典比特是两次测量结果，而鲍勃需要它们来执行修正操作，以将态转变成两个测量算符的+1本征矢。

在这个网络中量子比特一旦被测量，就完全确定下来并且不再被使用，所以我们将测量过的量子比特从分析中丢弃了。一个更复杂的网络可能包含部分纠缠的测量，那时测量过的量子比特可能依旧包含一些有趣的剩余自由度，因而必须保留在描述中。注意当我们丢弃量子比特时，稳定子的规模缩减了，但我们仍保留了相同数目的 \overline{X} 和 \overline{Z}算符，因为我们丢弃的是被稳定子完全限制了的量子比特。

例11（远程XOR） 爱丽丝忘记从她的另一个量子比特往她传给鲍勃的量子比特上作用一个CNOT了。不幸的是，他俩只剩一对共享EPR对了（鲍勃一直在纠缠赌场赌博，输得很惨）。她还能执行CNOT吗？

让爱丽丝能对鲍勃的量子比特执行远程XOR的网络在图9a中给出。爱丽丝和鲍勃从一个EPR对出发。他们各自做了一个CNOT和一次测量，接着把他们的测量结果传给对方（往每个方向只传了一个经典比特）。其结果是从爱丽丝的量子比特往鲍勃的量子比特的一个CNOT。这一操作也有他人研究过（原注：Wim van Dam，私下交流）。分析呈现在图9b中。

08. 讨论与总结

描述一个n量子比特的系统的演化，通常的办法是将完整的 2^n×2^n 幺正矩阵乘到一起，或者直接跟随这一系统的态矢量的演化。与这些相比，由量子计算的海森堡表示构成的方法让许多网络的分析可以快上许多。对于大多数网络来说，常规方法需要追踪指数多个矩阵元或者系数。

与此相反，对于仅由克利福德群里的门以及泡利群算符测量构成的网络，海森堡表示提供了描述系统的一种完美方法。在这类网络中，只需要跟随最多2n个 \overline{X} 和 \overline{Z} 算符的演化就够了，而每个算符都是泡利群的元素，可以用2n+1个比特来描述。因此，在经典计算机上分析这样一个网络所需的时间和空间都是n的多项式，而非指数。

事实上，我们可以超出只有克利福德群元素和泡利群测量的限制，还加上以经典比特（当然，这些可能是前期计算的测量结果）为条件的克利福德群操作。这一系列观察结果形成了下述定理的证明（原注：E. Knill，私下交流）（译注：这一定理现在被称为戈特斯曼-尼尔定理）：

定理1（尼尔定理） 任何量子计算机如果只执行：a)克利福德群门，b)泡利群算符测量，以及c)以可能是早期测量结果的经典比特为条件的克利福德群操作，一定可以在一台概率型经典计算机上以多项式时间完美地模拟。

当然，克利福德群操作和泡利群测量不能提供量子门的通用集。必须有一个额外的门，它可以是经典托福利门 (|a|b|c{\rightarrow}|a|b|c+ab 的量子版本，布洛赫球面上的π/8转动，或者受控非门的平方根，诸如此类。克利福德群加上一个适当的额外门生成 U(2^n) 中稠密的一个幺正算符集，因此构成一组通用门集。

尼尔定理意味着，只有使用了超出克利福德群的门时，量子计算才会比经典计算更强大。不过，仅使用克利福德群门的网络在量子通信领域有着大量的重要应用。

量子纠错码是一个重要的例子——稳定子码仅使用克利福德群门来编码和解码，但却在克服错误和退相干效应上极其有用。其它重要的通信问题，比如量子隐形传态，也只使用克利福德群门和测量。

最后，由克利福德群门和测量组成的网络也许可以提供更复杂量子计算中的子程序；分析和搜索这类子程序的高效方法会是大有裨益的。

原文链接：

https://arxiv.org/abs/quant-ph/9807006

作者简介：丹尼尔·戈特斯曼，马里兰大学教授
译者简介：左芬，博士，上海微观纪元数字科技有限公司