💻 computer science

Ramanujan quantum expanders from the Weil representation

本文通过利用 Weil 表示将 Morgenstern 的 Ramanujan Cayley 图进行转移，为任何奇素幂 $q$ 构造了 Ramanujan 量子扩展图的无限族精确构造，在实现对数门复杂度的情况下，达到了无加性误差的最优奇异值界限。

原作者： Siddhartha Jain

发布于 2026-09-30

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Siddhartha Jain

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在现代物理学的广阔版图中，存在着一种持续的张力：即随机性的混沌本质与可靠技术所需的严密结构之间的张力。科学家经常依赖随机过程来解决那些过于复杂、无法通过逐步逻辑解决的问题，就像徒步旅行者在茂密的森林中徘徊以寻找一片空地，而不是试图预先绘制出每一棵树的地图。在量子计算领域，这一理念转化为“量子扩展器”（quantum expanders），这是一种能够高效混合信息的特殊数学工具。想象一个挤满了人的房间，每个人都向邻居低声诉说一个秘密；如果这些连接是随机且分布均匀的，秘密就会在人群中迅速且均匀地传播。量子扩展器对量子粒子的微妙状态也进行同样的操作，确保信息能够快速且均匀地扩散。这种速度对于构建强大的量子计算机至关重要，但制造这些工具却极其困难，因为它们必须以极高的精度构建，以避免可能摧毁脆弱量子信息的误差。

多年来，研究人员一直致力于构建具有完美效率——即“拉曼努金”（Ramanujan）界限——的量子混合器。这是一个理论极限，代表了在物理定律允许范围内所能达到的绝对最佳性能。此前的尝试虽然可以非常接近这个理想值，但总是会留下微小的误差余量，或者需要极其复杂的机械装置，从而导致其不切实际。德克萨斯大学奥斯汀分校的一位研究人员现在破解了这个谜题，构建了一个全新的、无限的完美量子扩展器家族。他们的工作证明，为各种规模构建这些高效混合器是可能的，而且至关重要的是，它们可以使用一组特定的、易于处理的量子操作来构建，且不会引入任何额外的误差。

通往这一解决方案的路径涉及桥接两个截然不同的数学领域：对称形状的研究与量子波的行为。研究人员从一个已知的经典数学结构开始，这是一种被称为凯莱图（Cayley graph）的网络类型，它已被证明是经典信息的完美混合器。挑战在于如何将这种经典网络转化为量子世界，同时又不丢失其完美的特性。为此，他们使用了被称为韦伊表示（Weil representation）的数学工具，该工具充当了“翻译官”的角色，将经典网络的运动转化为量子态的操作。他们专注于这种翻译过程中一个特定的、隐藏的部分，即一个量子态表现出特定行为的“子空间”。通过隔离这一特定部分，他们发现复杂的量子操作简化为了三种基本动作：改变波的相位、缩放波的大小，以及执行傅里叶变换（一种基于模式重新排列信息的方法）。

这项发现的意义不仅在于他们找到了混合信息的方法，还在于他们实现这一目标的方式极其高效。研究人员展示了，对于给定规模的量子系统，他们可以仅使用随着系统规模增大而增长极其缓慢的基本步骤，来构建整个混合机器。具体而言，所需的步骤数量与系统规模对数的平方成正比。这意味着即使量子计算机规模扩大以处理海量数据，构建混合器所需的代价依然保持在惊人的低水平。此外，该构造使用了一套固定的工具，这意味着无论系统变得多么庞大，同样的基本指令都适用。这比以往的方法有了重大改进，因为以往的方法往往需要随着规模扩大而变得越来越复杂且易出错的指令。

研究人员还解决了关于精度的关键问题。在现实世界中，量子计算机是带有噪声的，微小的错误可能会不断累积。然而，团队证明，如果量子电路完全按照设计构建，并使用他们特定的工具集，其混合性能将完美达到理论极限。不存在任何会导致性能略低于理想值的残留误差或“加性噪声”。虽然由于量子态的脆弱性，在物理实验室中构建这样一个完美的电路是一项艰巨的挑战，但数学证明表明，这在原理上是可行的。这项工作依赖于一个确定性过程，这意味着对于任何给定的规模，研究人员都可以计算出构建混合器所需的精确指令，而无需任何猜测或随机搜索。

这一成就为量子算法的设计开启了一扇新的大门。通过提供一个清晰、精确的蓝图来创建这些完美的混合器，研究人员消除了一个长期阻碍进展的主要理论障碍。该构造适用于由素数决定的特定规模家族，但它涵盖了无限的可能范围，这表明该方法具有鲁棒性和可扩展性。论文并未声称构建了一个物理设备，而是解决了如何构建此类设备的数学和算法问题。它确立了完美的量子混合器不仅仅是一个理论上的梦想，而是一个可以用简单、高效的规则来描述的具体的现实。这种清晰度使其他科学家能够专注于构建硬件的工程挑战，因为他们知道底层的逻辑是稳健且最优的。

这项工作还阐明了实现这一目标并不需要哪些东西。长期以来，人们一直认为构建这些混合器需要一个完整的、基于复杂群的“量子傅里叶变换”，那是一个极其庞大且困难的操作，会将系统分解为所有可能的组成部分。研究人员表明，这种沉重的机械装置是不必要的。相反，他们只需要实现一个单一的、不可约的表示，这是一种更简单、更直接的方法。这一洞察简化了整个领域，表明实现完美量子混合的路径并不需要解决量子数学中最难的问题，而是需要找到看待问题的正确且更简单的视角。

最后，论文呈现了一个完整且自洽的解决方案。它从一个经典网络开始，使用特定的表示将其转化为量子语言，隔离了该语言中最高效的部分，并证明了由此产生的机器是完美的。其结果是一个量子扩展器家族，它们达到了理论上的极致，其构建步骤随规模增长的效率极高，并且由精确且无误差的规则定义。这为量子计算的未来发展奠定了坚实的基础，为工程师提供了一个明确的目标，同时也为理论家探索信息处理的极限提供了新的工具。

技术摘要：基于 Weil 表示的 Ramanujan 量子扩展图

问题陈述

量子扩展图是经典随机游走在扩展图上的量子类比。它们被定义为幺正通道（unital quantum channels），其第二奇异值（在无迹算符上的收缩因子）较小。具体而言，一个度数为 $D$ 的混合幺正通道 $\Phi$ 若满足界限 $\lambda_D = \frac{2\sqrt{D-1}}{D}$ ，则被称为 Ramanujan 量子扩展图。

虽然 Hastings (2007) 表明随机幺正算符渐近地达到该界限，但挑战在于如何显式构造此类通道并使用高效的量子电路。Harrow (2008) 提出了一个转移原理：如果群 $G$ 上的经典 Cayley 图是 Ramanujan 扩展图，且 $\mu$ 是 $G$ 的一个不可约表示，那么通道 $\Phi_\mu(X) = \frac{1}{|S|} \sum_{s \in S} \mu(s) X \mu(s)^*$ 将继承该谱界限。然而，高效实现 $\mu(s)$ 一直是一个瓶颈。对于 $PSL_2(\mathbb{F}_p)$ 群，由于目前尚无已知的、能够分解正则表示的高效非阿贝尔量子傅里叶变换（QFT），现有的方法要么无法达到最优的固定度数界限，要么引入了带有加性误差的近似。

方法论

本文通过结合三个组件来构造一个无限的 Ramanujan 量子扩展图族：

经典 Ramanujan 图： 利用 Morgenstern 对 $PSL_2(\mathbb{F}_p)$ 上 Ramanujan Cayley 图的构造，其中 $p = q^n$ （ $q$ 为奇素数幂， $n$ 为偶数）。
奇 Weil 表示（Odd Weil Representation）： 作者没有尝试进行完整的群 QFT，而是利用了 $SL_2(\mathbb{F}_p)$ $S L_{2} (F_{p})$ 的 奇不可约子表示。
- Weil 表示作用在由基态 $|x\rangle$ （对于 $x \in \mathbb{F}_p$ ）张成的希尔伯特空间 $\mathbb{C}^{\mathbb{F}_p}$ 上。
- 该表示由三种基本操作生成：二次相位（chirp）、域缩放以及 $\mathbb{F}_p$ 上的加法傅里叶变换。
- 作者将该表示限制在 奇宇称子空间 $H^-_p = \text{ker}(R+1)$ 中，其中 $R|x\rangle = |-x\rangle$ 。该子空间的维度为 $N = (p-1)/2$ ，并被证明在 $PSL_2(\mathbb{F}_p)$ 的射影作用下是不可约的。
高效电路实现：
- 任何元素 $g \in SL_2(\mathbb{F}_p)$ 最多可以分解为四个基本矩阵（Bruhat 分解）。
- 在 Weil 表示下，这些矩阵对应于上述三种基本量子操作。
- 作者证明了这些操作可以使用 $O(\log^2 N)$ 个基本门和 $O(\log N)$ 个辅助量子比特（ancilla qudits）来实现，且其使用的固定有限门集仅依赖于 $q$ 。

核心贡献

1. 精确满足 Ramanujan 界限

主要的理论贡献是构造了一个能够精确满足 Ramanujan 界限 $\lambda_D = \frac{2\sqrt{D-1}}{D}$ 的量子通道，只要电路实现是精确的，则不存在加性误差。

以往的工作（例如 Iyer 等人，2026）实现了接近 Ramanujan 界限的近似，其误差为 $\epsilon$ ，时间复杂度为 $\text{polylog}(1/\epsilon)$ 。
此构造依赖于这样一个事实：从 $PSL_2(\mathbb{F}_p)$ 提升到 $SL_2(\mathbb{F}_p$ 的两个元素，其差异仅在于奇子空间上的标量相位。由于量子通道涉及共轭运算（ $U X U^\dagger$ ），这些标量相位会相互抵消，从而使通道是良定义的，且与提升的选择无关。

2. 高效的电路复杂度

本文为维度为 $N$ 的度数为 $D$ 的量子扩展图提供了一个显式的电路构造：

门计数： $O(\log^2 N)$ 个基本门。
辅助量子比特： $O(\log N)$ 个辅助量子比特。
门集： 一个取决于 $q$ 的固定有限门集（包括域算术、受控置换以及基于基域 $\mathbb{F}_\ell$ 的傅里叶变换）。
预处理： 用于确定域模型、生成矩阵和电路系数的经典预处理需要 $\tilde{O}(\log^5 N)$ 次位运算。

3. 规避全群 QFT

该构造绕过了对 $PSL_2(\mathbb{F}_p)$ 进行完整非阿贝尔 QFT 的需求。通过识别出单个大型不可约表示（奇 Weil 表示）足以满足 Harrow 的转移引理，作者避免了分解整个正则表示的障碍。

结果

本文建立了以下定理：
对于每个奇素数幂 $q$ 和度数 $D = q+1$ ，存在一个作用在希尔伯特空间维度 $N_k = (q^{2k}-1)/2$ 上的无限 Ramanujan 量子扩展图族 $\{\Phi_{p_k}\}$ 。

该通道是一个度数为 $D$ 的混合幺正通道。
其第二奇异值满足 $\sigma_2(\Phi_{p_k}) \le \frac{2\sqrt{D-1}}{D}$ 。
其实现使用 $O(\log^2 N)$ 个门和 $O(\log N)$ 个辅助量子比特。

本文还讨论了近似问题：如果将精确门集替换为具有 Solovay-Kitaev 合成的通用门集，则奇异值界限会产生一个与近似误差成正比的加性误差，这与标准的量子电路合成极限一致。

意义与主张

本文的主张主要在于谱界限的精确性和构造的高效性。

精确性： 不同于以往渐近接近或带有误差的构造，此方法对于理想化的电路能精确满足 Ramanujan 界限。这直接归功于奇 Weil 表示的表示论特性以及对 Morgenstern 图的特定选择。
高效性： 该构造实现了相对于维度 $N$ 的对数级电路深度和规模的最优缩放，在保持量子谱性质的同时，达到了与经典扩展图构造相当的效率。
理论桥梁： 它通过利用一个此前未被充分利用的、可高效实现的特定表示（Weil 表示），成功架起了经典 Ramanujan 图（Morgenstern）与量子扩展图（Harrow）之间的桥梁。

作者指出，虽然精确实现从理论上是成立的，但实际实现将依赖于 Solovay-Kitaev 定理，从而引入近似幺正算符的标准开销，但该理论框架提供了一个清晰、无误差的基准。该工作对于构造所有度数以及对于所有足够大的希尔伯特空间维度（而非仅仅是特定的序列 $N_k = (q^{2k}-1)/2$ ）的扩展图问题仍留有开放性。