动机
一般的多量子比特态,需要指数多个概率幅才能写下来。但某些态有较短的描述:指定一组可交换且数值已知的可观测量,让这些方程决定状态。例如 Bell 态是同时对 和 具有特征值一的唯一态。此描述保留关联,却不用列出四个概率幅,而且能推广至很多量子比特。
要把短描述用于模拟,还必须能有效更新它。我们需要说明,门如何改变方程,测量如何改变方程,以及如何取得测量概率。符号一直重要: 和 具有相同的非恒等张量因子模式,测量意义却相反。
本篇建立只存储生成元、并明确保留四值相位的 tableau 表。它与常见的单一符号比特惯例略有不同,所以每条更新都从指定的算子次序推导。所得算法对计算基输入、指定 Clifford 门及 Pauli 测量,证明精确模拟结论;它不模拟任意量子电路,也不列出指数长的概率表。
定义
令
定义 4.1.1
(Pauli 行编码)
对二元向量 和 ,把 Pauli 编码为
次序是全部 因子先于全部 因子。特别地,单量子比特行 表示 ,而 表示 。二元坐标按模二相加,记为 ;相位指数则按模四相加。相位公式中的内积,先作整数加总,再按所示模数化简。
定义 4.1.2
(稳定子态)
纯稳定子态由 个彼此交换、独立的厄米(Hermitian) Pauli 生成元 指定,其生成群不含 。独立表示二元行向量 的秩为 ;上标标记生成元,下标则标记量子比特坐标。状态是共同 特征向量,归一化后只差整体相位。可展开投影 检查唯一性:独立性使每个非空乘积都是非恒等 Pauli,故迹为零。投影的迹为一,因此秩为一。
定义 4.1.3
(Tableau 与 Clifford 共轭)
本篇的 tableau 就是这 行,每行有 个二元坐标及两个相位比特。Clifford 酉算子把 Pauli 群共轭映至自身。我们使用
以及按 定义的受控非门。若状态经 演变,稳定子就按 演变。测量厄米 Pauli ,是使用两个投影 ,结果标记为 。
定理/命题
定理 4.1.4
(保留相位的 Pauli 算术)
乘法规则为
两行可交换,当且仅当 模二成立。一行为厄米,当且仅当 模二成立。
定理 4.1.5
(本篇惯例下的共轭更新)
对每个生成元行使用下列规则。右边全部是旧值,未指定的项保持不变:
这些门是 Clifford 门,共轭后的行指定演变后的态。CNOT 不更新相位,是本篇先 后 的次序惯例之结果,并不是每一种 tableau 惯例的规则。
定理 4.1.6
(纯稳定子态的 Pauli 测量)
若有生成元与 反交换,两个结果的概率均为 。选一个这样的主元 。对其余每个与 反交换的生成元,使用原来主元及保留相位的乘法,把它改为 。其他行不变,最后按采样结果 ,把主元改成 。新行描述归一化的测量后状态。
若全部生成元都与 交换,就在 上解出与 有相同二元坐标的生成元乘积。其真正带符号乘积不是 就是 ,相应结果确定为 或 ,状态不变。
定理 4.1.7
(本篇实际证明的模拟结论)
从计算基乘积态出发,由 、受控非门和已编码厄米 Pauli 测量组成的电路,可使用 比特存储量及多项式经典时间作精确采样。只存储生成元的做法,每个所列门需 ,用二元高斯(Gauss)消元处理每次测量至多需 。若门的选择依赖过去测量结果,而其经典控制能在多项式时间内计算,仍在结论范围内。
这是对指定理想电路模型的构造性 Gottesman–Knill 结论。下面证明更新不变量及采样概率;但不证明任意抽象 Clifford 酉算子都能由此门集合成,不证明较快的 destabilizer 表算法,也不处理任意混合或含噪声输入,以及不受限制的非 Clifford 门。有效采样一条记录,也不同于输出全部可能记录。
证明思路
证明
(重排 Pauli 因子所产生的符号)
乘法的唯一额外符号,来自把 移过 。每个重叠对贡献一个负号,得到 。把乘法次序反过来就得到交换测试。取伴随时, 次序反转,相位也共轭,所以厄米性要求 ,恰是所述奇偶条件。两个可交换稳定子行的乘积仍为厄米;任意两个反交换行的乘积则未必如此。
证明
(验证单量子比特与 CNOT 的更新)
对门,直接矩阵乘法给出 、、 和 。Hadamard 因而把局部 和 的次序反转,向相位加入 。相位门贡献 ,并把旧的 比特加到 比特。这同时证明两条单量子比特规则,包括局部因子为 时的符号。
在基态上检查受控非门可得
全部变换后的 因子仍可置于全部 因子之前,不需要把某个 移过某个 ,因为它们本来就以该次序到来。因此二元更新不用改变 。酉共轭保留乘法、交换关系及共同特征空间,所以保留 tableau 的状态意义。
证明
(随机测量结果与新生成元)
对随机测量,反交换主元给出
所以两个投影概率相同。归一化分支为 。每个未改变的交换生成元都稳定此分支;两个反交换生成元之积也与 交换并稳定它;最后, 在所选分支上特征值为一。改变后的非主元行仍独立,张成旧二元行空间的一个 维子空间。测量向量不在该空间,因为它与旧主元反交换,旧行空间中的每个向量却都与旧主元交换。加入测量行后,秩回到 。分支非零,所以新群不能含 。因此这些行精确指定归一化分支,而不只是列出它满足的一些限制。
证明透视
先用旧主元消去,才替换它
两个都与测量反交换的旧行,其乘积会与测量交换,这正是更新所需的抵消。先替换主元会破坏此论证:把反交换行乘上新的测量行,可能得到反厄米算子。应保存原来主元,以精确 Pauli 乘法完成全部消去,最后才放入带有所测符号的可观测量。
证明
(由极大性得到确定测量)
确定结果的情况用到极大性,而不只是交换的口号。令 是旧二元行空间,配上双线性形式
此形式非退化,因为与坐标 、 向量配对,能检测每个坐标。因此正交补的维数是 。交换性给出 ,维数相等便有两者相等。所以与每行交换的测量必在 内。二元消去找出系数,再乘上带符号的行,决定结果是 还是 ;厄米性排除 的相位差。这证明确定概率,也解释为何消去后不能把相位丢掉。
概念视角结构
稳定子态是极大迷向子空间
先暂时不管符号。二元行 位于 ,配上上文的双线性型 ; 个独立且互相对易的生成元张成满足 的子空间,即极大迷向子空间。稳定子态就是这样的子空间再加上一组符号选择。 时有三个子空间(、、),各有两种符号,共六个态; 时有十五个子空间、六十个态。
证明
(存储量、运行时间与精确采样)
对基输入 ,以 初始化各行。表示式使用 比特。每个所列门只触及每行固定数目的项;测量与全部行的交换测试,以及随机情况的消去,需 比特操作。确定情况的成员判定,可用普通二元消去在 操作完成,再作保留相位的乘法。每个随机分支用一枚公平硬币。由于条件概率和新状态都与量子测量相同,归纳法加概率链式法则便证明整条记录的精确采样,不必列举分支。
Aaronson 与 Gottesman 的较快算法保留额外行,避免此消去步骤。本篇不证明该改良及较强的性能界;明确的生成元算法已足以对指定模型建立多项式模拟。
例题详解
例题 4.1.8
(三个门之后仍要保留单量子比特的符号)
从由 稳定的 出发,其行为 。依次作用 、、,各行变成
它们表示 ,故最后测量 必得 。若只保留最后的二元对,就会遗失符号。稳定子方程的符号指定特征值,不是态向量无关紧要的整体相位。
例题 4.1.9
(典范相位不变,为何仍可表示负 YY)
以量子比特一控制量子比特二的受控非门,共轭 。原行有 、、;更新后两个二元向量都为 ,相位仍为零。所得算子是
这不与相位规则矛盾。把典范有序乘积转成局部 因子时,会出现两个 。若另一惯例是在局部 标记前存储正负号,就要在另一位置处理这个转换。
例题 4.1.10
(Bell 关联与真正随机的第一次测量)
从 出发,作用 和受控非门,初始生成元 变成 。其乘积是 ,所以测量 必得 。
若改为测量 ,它与第一生成元反交换,每个结果 的概率为 ,新生成元是 。其乘积为 ,故随后的 测量必有相同结果。两分支是 和 。经典采样可以精确保留这个关联;稳定子可有效模拟,不表示没有纠缠。
反例模式
非 Clifford 相位破坏 Pauli 更新
对 ,
它不是 Pauli 算子。态 的 、 期望值为 , 期望值为零,所以没有非恒等的单量子比特 Pauli 以它作特征态。本篇的一行纯态表示对此门不封闭。但表示法失效,不等于证明每个含 的电路都难以经典模拟;例如 。
第二个反例涉及确定情形,而不是门集合。
反例模式
不完整的码空间描述中,交换仍不足够
两量子比特上的单一生成元 指定码空间,而非纯态; 和 Bell 态都在其中。 与此生成元交换,但在第一个态上必得正结果,在第二个态上却均匀随机。确定情况的证明需要 个独立生成元和极大的二元行空间,不能只用较少生成元,忽略尚未决定的逻辑态后仍套用它。
常见错误
常见错误
(共轭方向错误,或使用已被覆写的坐标)
状态按 演变时,要使用 ;反方向共轭回答另一个问题。二元更新右边全部用旧坐标,再存储新行;若混入已覆写坐标,即使公式正确也可能得到错结果。
常见错误
(生成元的符号不是整体相位)
不要把 Pauli 的和当成单一 Pauli,也不要把生成元符号与态的整体相位混淆。二元消去决定乘积的支撑模式,真正的相位则决定特征值。未先翻译所表示算子,就在不同 tableau 约定之间照搬相位公式,尤其容易出错。
常见错误
(模型外的门不能证明困难性)
模拟器假设理想操作和完整指定状态的稳定子输入,没有证明一般容错或噪声阈值,也没有只凭模型外某个门的出现就建立困难性结论。紧凑表示可能不再适用,但不会自动令每个这类电路实例都很难。
总结
Pauli 行结合二元支撑与相位,后者必须在乘法和共轭中保留。所列 Clifford 门保持此表示。Pauli 测量不是均匀随机并替换主元,就是以极大性及带符号成员判定得到确定结果。这些性质对指定理想模型给出精确多项式时间采样,但合成、优化表、较广输入及噪声模型仍不在已证结论内。
练习
快速检查
(以典范乘法规则计算 和 。为何不修正相位,就不宜把这些乘积当作厄米稳定子生成元?)
把 编码成 。
解答 · 答案
反交换乘积带虚相位。对 ,相位为 ,二元对为 ,所以 。反向次序没有交叉贡献,故 。两者都反厄米,与两个反交换厄米算子相乘一致。稳定子行替换使用彼此交换的生成元,其乘积仍为厄米。
快速检查
(从 出发,作用 再 ,然后测量 。求概率及每分支的新生成元;立即重测 又如何?)
测量前的生成元是 。
解答 · 答案
结果随机一次,然后确定。门给出生成元 ,它与 反交换,所以每个结果的概率为 。结果 把唯一生成元替换成 ;新态因此是特征值 的 特征态,立即重测必得相同结果。
快速检查
(对 Bell 生成元 和 ,测量 并以第一生成元作主元。两旧行都与测量反交换,求新生成元及概率。)
先用原主元消去第二行,再替换主元。
解答 · 答案
消去两个反交换行:第二行成为 ,新主元是 ,每个 的概率为 。两个新生成元彼此交换且独立。乘积行的典范相位为零,两个二元向量都是 ;把它读成正的 就是符号错误。
快速检查
(三量子比特态的生成元为 、、。先测 再测 ,以生成元乘积推导其关联,不要列态向量。)
第一结果决定新的带符号 生成元。
解答 · 答案
三个比特共享同一个结果。 与 反交换,故每个结果 的概率为 。两个旧 对生成元与它交换,保持不变。新生成元 乘 得 ,再乘 得 。所以后来测量 必得 。代数用三行而不是八个概率幅追踪此关联。