Skip to content

算法Algorithm

容错综合提取

Fault-tolerant syndrome extraction · Shor error correction

用明确的四位cat制备与端点校验阻断危险传播,再以四轮完整综合和一致性规则处理测量故障,分别证明单输入错与单内部故障条件。

形式陈述 ​

距离3的稳定子码能纠正单数据错误,但提取综合的装置也会发生故障。一个合格的一故障纠错模块至少应满足:

  1. 输入至多一处错误、模块无故障时,恢复正确逻辑态
  2. 输入无错误、模块至多一个故障位置时,输出与正确逻辑态至多相差一处可纠正错误

第二条容许留下一个错误,而不能容许制造一个逻辑错误。用于递归阈值证明还需检查更强的“任意输入映到距某个码态至多一错”的恢复性质;下面的完整综合与恢复表会说明相应机制。[1, §§10.2,12.2]

本文采用Pauli位置故障作明确逐项分析,允许一个双qubit位置同时在两端出错;经典综合处理视为可靠,所有量子初始化、耦合、测量与等待均须计为位置。一般局部算子在同一支撑上的线性扩展由纠错条件承接,不把它当作独立Pauli概率。

具体构造使用七qubit CSS码的六条重量4检查。先选全局物理位置 1,3,5,7 上的第一条 Z 检查,把这四个数据位置局部重命名为 d1,d2,d3,d4,所以

P=Zd1Zd2Zd3Zd4=Z1Z3Z5Z7.

下面cat的编号 a1,…,a4 属于四条辅助线,不是七qubit数据的全局编号。测量其他检查时再按其支撑重命名;X 检查可用相应基变换实现。讨论四轮完整六位综合和恢复表时,数据重新使用全局编号 1,…,7。

直觉

单辅助反复接触四个数据位,会把一次辅助错误传播成多处数据错误。cat态把同一个校验的控制量分散到四条辅助线,每条只碰一个数据位置。

但cat态自己的制备也可能产生相关错误,所以必须在接触数据之前验证。验证主要防止危险的比特型传播;相位错仍可能翻转综合读数,因此还要重复整份综合,而不能把“验证cat”和“综合一定正确”混为一件事。

图中验证线只在 a1,a4 上有控制点,中途跨过 a2,a3 的线不表示连接。通过验证以后,才让每条cat线与一个数据位置耦合。

例子与边界

四位cat测量的理想作用 ​

准备

|cat4⟩=(|0000⟩+|1111⟩)/2.

对 j=1,2,3,4 各施一次 controlled-Z,辅助 aj 控制数据 dj。由Clifford门组成的这层耦合把状态变成

|0000⟩|ψ⟩+|1111⟩P|ψ⟩2.

分别测量四个辅助的 X。若四个本征值的乘积为 s=±1,数据条件更新正比于 (I+sP)|ψ⟩。把同一奇偶的八种详细结果合并,就得到 P 的Lüders投影;详细辅助结果不额外揭示逻辑信息。

在这个耦合中,Xaj 可传播出 Zdj,但每条辅助只接触一个数据位置,所以单辅助错不再直接扩散到多位。辅助的 Z 错只会翻转某个 X 读数,须由后面的重复处理。

指定制备电路,才谈得上指定验证 ​

准备四个 |0⟩,依次施

Ha1,CNOTa1→a2,CNOTa2→a3,CNOTa3→a4.

这是链式制备,不是从第一位向其余三位的扇出。随后用验证辅助 v 的 |0⟩,施 CNOT a1→v、a4→v,测 Zv;仅在结果0时接受。它测的是 Za1Za4,不测量cat本身究竟是全0还是全1。

为什么这一条首尾检查够处理链式制备的单故障?把任意Pauli故障的 X 支撑沿剩余CNOT传播。模cat稳定子 X1X2X3X4,链中一个位置能产生的不可忽略多位模式只有

X3X4或其补集 X1X2.

两者都与首尾检查反对易,必被拒绝。其余模式等效为零或单个 X。例如第二个CNOT之后目标上的 X3 会传播成 X3X4,正是需要排除的危险情况。

如果唯一故障发生在验证部分,cat制备本来正确;验证CNOT最多给一个cat控制位添加 X,验证目标上的 Z 虽可能回传多个cat相位错,却不会生成多个cat比特翻转。任意多个 Z 在理想cat上也只按奇偶等效为零或一处相位错。

接受的cat因此至多带一个可向数据传播的位置错误,允许再有综合翻转。与四位 X 相差的cat模式在数据上相差所测稳定子 P,在测量分支中作用相同到相位,所以这里的“至多一处”按正确的稳定子等价类理解。

这份验证只对上述制备顺序及故障模型作了分析。改成别的cat接线后,危险错误对可能变化,不能机械沿用同一首尾检查。

为什么只测一次完整综合仍会失败 ​

一个数据—cat门故障可以同时在数据制造 Yj、在cat制造相位错,于是一边改变实际综合,一边翻转报告位。对假综合立即执行恢复,可能再添加另一个位置错误,最终从一个故障得到两位数据错。

另一种问题不需要错误读数:数据错误若在六项检查中间出现,前几位描述旧状态,后几位描述新状态,拼成一份从未真实存在的混合综合。逐项把每一位多数投票,并不能排除这种时间混合。

推论与应用

一个有固定最坏次数的一故障规则 ​

对七qubit码依次测完六条检查,算一轮;固定执行四轮,记录完整六位综合 s(1),…,s(4),中间不恢复。每条检查使用新验证cat。

cat验证失败时,在接触数据之前丢弃并重新制备;每条检查最多安排两次制备尝试。两次都失败就标记模块失败。在总共至多一个故障的承诺下,第二次尝试必无故障而通过,所以这一限制不会破坏一故障保证。等待和预留时隙仍计入模块位置。

四轮结束后,选最早一对相邻且完全相同的综合,并按它恢复。若没有这样的相邻对,标记模块失败;该分支在一故障承诺下不会出现。因为至多一轮受故障直接扰动,四轮中要么故障前有两轮连续正确综合,要么故障后有两轮连续正确综合。

恢复表必须覆盖全部六位综合,而不仅是21种单Pauli错误。对CSS码可分别依据两半综合选择 Xi 与 Zj,零综合对应不操作;不同半指向不同位置时允许选一个两位置代表。这使任意综合都能被映回码空间,虽然对任意多错输入并不保证原逻辑态。

两项一故障保证怎样成立 ​

若输入至多一错且模块无故障,四轮综合相同并准确,查表恢复除去这个错误。若输入无错而模块有一个故障,一对相同综合中至少一轮无故障,所以所选综合曾经真实出现过。它可能是故障前的零综合,也可能是故障后的真实综合。

选择故障后综合时,查表移除那一个等效数据错误;选择故障前综合时,后来的故障最多留下一个错误。若唯一故障在最后恢复或等待位置,先前过程正确,故输出同样至多一错。因而不会因错误综合再叠加一个不相关恢复错误。

对任意输入,理想稳定子测量可先按综合分支分析。所选真实综合的恢复把该时刻的状态送入码空间;选择时刻之后至多一个等效数据错误,最终就距某个码态至多一错。这是模块恢复性质的机制,不等于声称任意输入都能恢复其最初逻辑信息。

该模块的工作量是固定轮数乘检查数,再乘每条检查的cat制备、验证和耦合成本:重量为 w 的cat方案每次需 O(w) 个基本门和辅助位,此处检查数6、轮数4、w=4。把整个纠错模块嵌入阈值证明时,还要对等待、失败标志和共享纠错区块统一计数,不能只统计与数据接触的四个门。

参考资料
关系图谱15 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系