酉群上的深度 1 扩展器及其应用

论文信息

标题: Depth-1 expanders on the unitary group and applications

作者: Anurag Anshu, Shankar Balasubramanian, Jonas Haferkamp, et al.

发布日期: 2026-09-01

arXiv ID: 2609.01605v1

PDF 链接: 下载 PDF

3 分钟速览

• 研究问题：这篇论文要解决在 $n$ 量子比特上构造常度数、常谱隙的量子扩展器，并要求生成元可被深度 1 的 1D 量子电路实现；同时把这一构造用于 1D 纠缠-能隙关系和流式量子态测试。
• 核心方法：利用 Kassabov 对 $\mathrm{SL}(3s,\mathbb{F}_2)$ 的 14 个生成元，通过 CNOT 群表示映射为深度 1 电路；再补入 Pauli $X,Z$ 门得到量子扩展器；对酉群扩展器则借助 Clifford 正态形与 $T,T^\dagger$ 门。
• 关键结果：构造了 16 个深度 1 生成元、谱隙至少 $1/(2\times 10^8)$ 的量子扩展器（定理 2.2）；并构造出满足 $S=\Theta(\Delta^{-1/2})$ 的 frustration-free 1D 哈密顿量族（定理 3.1）。
• 主要局限：深度 1 构造对 $n=3s$ 显式给出；哈密顿量能隙为 $\Theta(n^{-2})$，尚未达到猜想中的 $\Theta(n^{-1})$；常数谱隙较小。
• 适合读者：量子计算理论、量子信息、量子多体物理和扩展器理论研究者。

论文背景和研究动机

量子扩展器是一组酉矩阵 $\{U_1,\dots,U_m\}$，满足对任意无迹 $X$，

$$\left\lVert \frac1m\sum_i U_i X U_i^\dagger \right\rVert_2 \le (1-\Delta)\lVert X\rVert_2,$$

其中 $\Delta>0$ 是谱隙。它在量子一次性密码、QSZK 完全性、高纠缠态测试和量子多体物理中有重要应用。此前已知随机酉矩阵可以给出扩展器，但显式电路构造通常需要 $\mathrm{poly}(n)$ 深度。一个开放问题是：能否用深度 1 的局部电路实现常数谱隙扩展器？

本文给出了肯定回答。更深层的动机来自两个方向。第一，1D 有隙哈密顿量基态的纠缠熵上界曾由 AKLV13 改进为 $S\lesssim 1/\Delta$；对于 frustration-free 系统，猜测最优标度为 $S\lesssim 1/\sqrt{\Delta}$，但此前没有达到该下界的显式构造。第二，酉群上的扩展器要求对所有有限维不可约表示都有统一谱隙，此前 Bourgain–Gamburd 的结果不能控制谱隙对维数的依赖，Lubotzky 曾猜测存在一致有隙的生成族。本文同时在这两个问题上取得了进展。

核心方法和技术细节

核心构造从特殊线性群 $\mathrm{SL}(n,\mathbb{F}_2)$ 与 CNOT 群的关系入手。每个 $g\in \mathrm{SL}(n,\mathbb{F}_2)$ 通过对 $\mathbb{F}_2^n$ 的线性作用置换计算基态，由此得到表示

$$\Gamma(g)|x\rangle=|gx\rangle.$$

初等矩阵 $E_{i,j}=I+e_i e_j^T$ 在 $\Gamma$ 下正好是控制比特 $j$、目标比特 $i$ 的 CNOT 门。因此，$\mathrm{SL}(n,\mathbb{F}_2)$ 的生成元对应 CNOT 电路的生成元。

论文使用 Kassabov 给出的 $\mathrm{SL}(3s,\mathbb{F}_2)$ 的 14 个生成元，其 Kazhdan 常数 $>1/400$（论文定理 2.11）。这些生成元在 $\Gamma$ 下变成深度 1 的 CNOT 电路：其中 4 个是单个 CNOT，其余按 3 个连续量子比特平移不变。为了把 CNOT 群上的谱隙推广为量子扩展器，论文计算了 CNOT 群的交换子，证明它由

$$\mathrm{Span}\{I,\ |+^n\rangle\langle +^n|,\ |0^n\rangle\langle 0^n|,\ |0^n\rangle\langle +^n|,\ |+^n\rangle\langle 0^n|\}$$

张成（论文引理 2.15）。然后使用 HH09 的算子范数引理，把 $X\otimes I$ 和 $Z\otimes I$ 加入生成集，得到 16 个深度 1 电路、谱隙至少 $1/(2\times 10^8)$ 的量子扩展器（论文定理 2.2）。

对于酉群上的扩展器，论文先构造 Clifford 群的 23 个深度 1 生成元。利用 Aaronson–Gottesman 的 Clifford 正态形，把任意 Clifford 门分解为有限长度的 CNOT 层、Hadamard 层和 $S$ 层，再结合上述 CNOT 扩展器得到常数 Kazhdan 常数（论文引理 2.19）。随后加入单个 $T$ 门和 $T^\dagger$ 门，并使用近期随机 Pauli 旋转谱隙结果 $g(\nu_{\mathrm{PR}})\le 15/16$（论文引用 BH26），得到 $\mathrm{SU}(2^n)$ 上 25 个生成元的一致有隙扩展器（论文定理 2.17）。进一步通过 KAK 分解和 216 个嵌入，把结果推广到所有 $\mathrm{SU}(d)$，生成元数量不超过 5400（论文推论 2.18）。

应用方面，哈密顿量构造采用左、右两条 1D 链，每条链分为数据链和时钟链。$H_{\mathrm{check}}$ 约束时钟配置为合法字；$H_{\mathrm{prop}}$ 用修改的 Feynman-Kitaev 域墙时钟在数据链上依次施加 $U_i$ 或 $\overline{U_i}$；$H_M$ 耦合左右链，迫使数据部分处于最大纠缠态 $|\Gamma_n\rangle$。由于 $U_i$ 是深度 1 电路，可以顺序化并保持 1D 局域性。流式测试则利用扩展器的几乎平移不变结构，通过滑动窗口实现常数内存的受控酉操作。

创新点和贡献

本文的主要贡献包括：

• 深度 1 量子扩展器：首次构造常度数、常谱隙且每个生成元为深度 1 电路的量子扩展器（论文定理 2.2）。这回答了低深度扩展器存在性问题，并使电路可以在 1D 几何上实现。
• 酉群上的一致有隙扩展器：在 $\mathrm{SU}(2^n)$ 上给出 25 个生成元的扩展器，谱隙对所有有限维表示和维度 $n$ 一致有界；对一般 $d$ 给出生成元数量不超过 5400 的版本（论文定理 2.17、推论 2.18）。这解决了 Lubotzky 猜想，并改善了 Bourgain–Gamburd 未控制维度依赖的问题。
• 1D 纠缠-能隙关系的紧性：构造 frustration-free 1D 哈密顿量族，其基态纠缠熵为 $\Theta(n)$、能隙为 $\Theta(n^{-2})$，因此 $S=\Theta(\Delta^{-1/2})$（论文定理 3.1）。这是此前被认为的最优标度，但此前没有构造达到。
• 流式状态测试协议：给出测试 $n$ 对 EPR 态 $|\Gamma_n\rangle$ 的单遍流式协议，内存为 $O(\Delta^{-1}\log(1/\varepsilon))$，且假阴性概率为 0（论文定理 4.3）。
• 改进的局部能隙界：证明 frustration-free 1D 系统基态纠缠熵满足 $S\le \tilde{O}(\Delta_{\mathrm{loc}}^{-3/4})$，优于先前的 $\tilde{O}(1/\Delta)$ 上界（论文第 5 节）。

结果分析与意义

本文是理论工作，没有数值实验。从定理给出的定量结果看，深度 1 量子扩展器的谱隙为至少 $1/(2\times 10^8)$，虽然非零但常数很小。论文也提到这不是优化值，构造更看重的是常数谱隙和深度 1 的存在性，而非常数的实际大小。

哈密顿量族中，$H-H_M$ 的有效单粒子时钟哈密顿量是三角对角矩阵，其能隙约为 $\pi^2/(4\alpha^2n^2)$；取 $\alpha=2$ 时给出下界 $4/(25n^2)$（论文引理 3.3）。加入 $H_M$ 后，利用扩展器谱隙得到常数级有效摄动，仍保持 $\Theta(n^{-2})$ 能隙，同时基态唯一且左右数据链形成 $n$ 个 EPR 对，纠缠熵为 $n$（论文引理 3.2）。

在流式测试中，重复扩展器 $r$ 次可将误差缩小为 $(1-\Delta)^r$，而内存只线性增长为 $O(r\ell+r\log m)$，因此得到 $O(\Delta^{-1}\log(1/\varepsilon))$ 的标度（论文定理 4.3）。这一协议的关键是深度 1 扩展器的几乎平移不变性；对于一般的深度 1 电路，滑动窗口大小仍为常数。

局限与待解决问题

论文也留下若干未决问题。首先，猜想 1.5 仍未解决：是否存在基态纠缠熵为 $\Theta(n)$、能隙为 $\Theta(1/n)$ 的一般 1D 哈密顿量族？本文构造的 frustration-free 哈密顿量只能达到 $\Theta(1/n^2)$。作者指出，时钟哈密顿量本质上像一个单粒子行走，如果能替换为自由费米子等多粒子哈密顿量，可能把能隙放大到 $1/n$，但他们尝试把该构造从酉推广到哈密顿量均未成功。

其次，深度 1 量子扩展器的显式构造针对 $n=3s$；论文提到并发的 LH26 工作可处理所有 $n$，但需要常数深度和更多生成元，并非深度 1。这说明深度 1 与对所有 $n$ 的统一处理之间仍有张力。

第三，流式测试协议目前主要针对 $|\Gamma_n\rangle$，以及可由常数键维 MPO 作用的 $U|\Gamma_n\rangle$ 类。能否测试更自然的平移不变哈密顿量基态，仍然是开放问题。论文作者推测，如果能够构造形式为 $H=\sum_j U_j$ 的几乎平移不变阶梯电路算子，则可能给出 $O(\log m)$ 内存的更多流式算法，但这尚未实现。

最后，改进后的 $S\le \tilde{O}(\Delta_{\mathrm{loc}}^{-3/4})$ 上界与本文给出的 $S=\Theta(\Delta^{-1/2})$ 下界之间仍有差距。能否进一步压缩到猜测的 $O(1/\sqrt{\Delta})$，或构造出更紧的反例，仍待研究。