快速上手 Tarski 不动点问题

Posted on 2026-03-19 Edited on 2026-03-24

Abstract. 这篇综述详细调查了目前 Tarski 不动点问题的研究进展。

问题
应用
目前的结果
总结

【失败作】人工智能用张量分析

Posted on 2026-03-15 Edited on 2026-03-16

Abstract. 本文是将凸优化课上讲的矩阵求导形式变简明的尝试，然而这个尝试是失败的。我们尝试将矩阵导数推广到了张量到张量的函数的协变导数，然后使用了一些张量分析的记号。但是很遗憾最后的效果是除了省掉了求和符号之外没有任何简化的迹象，主要是因为即便是在恒等函数的协变导数的记法上，普通的符号也很难展示两个二阶张量直积起来的时候新的指标是从哪来的，然而引入彭罗斯的图形化表示又过于繁杂，只能放弃。

张量函数的微分运算
张量函数的微分法则
使用例

QEC Workshop 4 | FTQC 基础，横向门

Posted on 2026-03-06 Edited on 2026-03-13

容错量子计算

至此我们已经配备了一些能够纠正 Pauli 错误的工具。然而实际上的错误不可能在 Encode 和 Decode 阶段缺席，因此我们需要考虑更广泛的景观。

错误发生的位置

定义 1.1.1（Locations）. 一个量子线路，无论容错与否，基本上是由各种位置（locations）构成的，分为：

态制备位（Preparation Location）；
门位（Gate Location）；
存储位（Wait / Storage Location）；
测量位（Measurement Location）；
经典计算位（Classic Computation Location）。

在这个模型下，错误可能发生在每个 Location 上，具体地我们采用这样的错误模型：

定义 1.1.2（Base Model for Fault Tolerance）. 本条定义罗列一些关于错误模型的关键术语。

独立随机错误模型. 线路 $C$ 上的一个独立随机错误模型 $\widetilde{C}$ 系指将 $C$ 中每个 Location $L$ 替换做一个相应、独立的 $\widetilde{L}$，其中 $\widetilde{L}$ 以 $1 - p_L$ 的概率执行 $L$ 的操作；以 $p_L$ 的概率输出同样 Hilbert Space 里面的别的酉变换。这个 $\widetilde{C}$ 也称为 $C$ 的含噪实现，$p_L$ 称为错误率，同种 Location 具有相同的错误率。
独立 Pauli 模型. $\widetilde{L}$ 总是 $L$ 复合上一个 Pauli 信道。
错误路径. 一个 $C$ 中 Location 的子集。

注意发生的错误实际上会随着线路传播。比如考虑 $\mathcal{E} = \mathcal{X}\otimes \mathcal{I}$ 作用在一个 $\mathcal{CNOT}$ Gate Location 上，有

$$
\mathcal{CNOT}(\mathcal{E}|\psi\rangle) = (\mathcal{CNOT}\cdot \mathcal{E}\cdot \mathcal{CNOT}^\dagger)\mathcal{CNOT}|\psi\rangle
$$

本质上发生的错误是 $\mathcal{CNOT}\cdot \mathcal{E}\cdot \mathcal{CNOT}^\dagger = \mathcal{X}\otimes \mathcal{X}$。而单量子门不会传播错误，只会改变错误类型。比如考虑 $[[7, 1, 3]]$ 码，你可以验证 $\mathcal{H}$ 门作用于逻辑比特就等价于给每个物理比特作用 $\mathcal{H}$（这种性质记作“$\mathcal{H}$ 是 $[[ 7, 1, 3]]$ 码上的横向门”，我们稍后展开讲）

$$
\mathcal{H}^{\otimes 7}|0\rangle_L = \frac 1{\sqrt 2}(|0\rangle_L + |1\rangle_L), \qquad \mathcal{H}^{\otimes 7} |1\rangle_L = \frac{1}{\sqrt{2}}(|0\rangle_L - |1\rangle_L)
$$

现在假设此时发生了一个 $3$ 位置上的比特翻转 $\mathcal{X}_3$，可以算出 $\mathcal{H}^{\otimes 7}\mathcal{X}_3 \mathcal{H}^{\otimes 7\dagger} = \mathcal{Z}_3$，并没有造成错误传播。

为了进行容错量子计算，一个自然的思路是将制备的初态 $|\psi\rangle$ 变成 $|\psi\rangle_L$，所有的门换成逻辑门。此处纠错的基本单元便是 Gadget。

定义 1.1.3（Gadgets）. 对于一个 Location $L$，其 Gadget 系指二元组 $(Q, \mathcal{G}_L)$，其中 $Q = (\mathcal{D}, \mathcal{E})$ 是一个 QECC，$\mathcal{G}_L$ 是相应的逻辑操作，即

$$
L = \mathcal{D}\circ \mathcal{G}_L \circ \mathcal{E}
$$

采用统一的 QECC，将所有种类的 Location 集合起来便得到一个容错计算协议（Fault Tolerant Protocol）。

定义 1.1.4（容错模拟）. 设 $C$ 是一个线路。根据一个容错计算协议，将 $C$ 中所有 Location 替换为相应的 Gadget 得到 $FT(C)$。这个线路称为 $C$ 的理想容错模拟。而对应的含噪版本 $\widetilde{FT(C)}$ 便称为其容错模拟。

这个容错模拟的线路大小开销（circuit size overhead）为 $FT(C)$ 的 Location 数目除以 $C$ 的 Location 数目。类似地可以定义空间开销（qubit 数目相除）、深度开销或时间开销等。

阈值定理的陈述与直觉

在接下来的两三讲中，我们的核心目标是证明以下的阈值定理：

Theorem. 假设一个系统服从独立随机错误模型，其中每种 Location 出错的概率都是 $p$。则存在一族纠错协议 $\mathcal{F}_l$，阈值 $p_T$ 使得：一旦 $p < p_T$，则对于一切始于态制备、终于测量的理想量子线路 $C$ 和任意正数 $\varepsilon > 0$，都存在一个 $l$ 使得 $C$ 在容错计算协议 $\mathcal{F}_l$ 下的容错模拟 $\widetilde{FT_l(C)}$ 中测量结果的分布和 $C$ 的测量结果的分布的统计距离至多相差 $\varepsilon$，且 $FT(C)$ 的 size overhead 为 $O(\mathrm{polylog}(T / \varepsilon))$。

以下是关于这个定理的一些评论：

定理的直觉. 假如你的线路有 $T$ 个 Location，要实现总误差不超过 $\varepsilon$，只需让每个 Locatoin 的误差不超过 $\varepsilon / T$（Union Bound）。而一个错误不会传播太远（一个错误仅会扩散到 $O(1)$ 个位置）的情况下，那么现在拿着一个能纠正 $t$ 位错误的 QECC 去纠错一次，每个 Gadget 的错误率就会变成 $p^{O(t)}$ 状物。此时你只需要反复用这个 QECC 去纠错即可（换言之 $\mathcal{F}_l$ 是那个 QECC 的拼接码）。
所谓“条件”. 上一条所谓的条件我们将在下一节（“1.3 容错计算的条件”）形式化。
常数的问题. 这个 overhead 的常数其实非常大，而且显然取决于 $p / p_T$。
阈值的测算. 一般我们会想要知道一个码的阈值。当然有一些严格证明的办法，实际上很多文献中常用数值模拟的办法来测量阈值（调节 $p$，算一个线路纠错前后的误差，两条线的交点就是阈值）。数值模拟测出的阈值通常比严格证明放出来的要高一些。