Arts & crafts: Strong random unitaries and geometric locality

想象你正在尝试烘焙一个完美且完全不可预测的蛋糕。在量子计算机的世界里，这个“完美蛋糕”被称为Haar 随机幺正算符。它是一种数学配方，能保证每一种可能的结果出现的概率都相等，就像洗牌直到顺序真正随机一样。

然而，对于真实的量子计算机来说，烘焙这种完美蛋糕是不可能的。所需的时间和能量会随着蛋糕的大小呈指数级增长——本质上，你甚至需要整个宇宙的能量，才能为仅仅几十种原料制作出一个蛋糕。

因此，科学家们问道：我们能否烘焙一个“足够好”的蛋糕，让任何试图品尝它的人都觉得它完美随机，但实际上制作起来要快得多？

本文给出了肯定的回答，特别是针对基于网格状结构（如许多现实世界量子芯片中使用的二维或三维网格）构建的量子计算机。以下是他们解决方案的分解，使用了简单的类比。

问题：“光锥”约束

想象你的量子计算机是一座城市，其中的居民（量子比特）只能与紧邻的邻居交谈。如果你想混合全城的人口以创造随机洗牌，你不能直接把所有人传送到中心。你必须让消息从邻居传到邻居。

如果城市是一条长线（一维），消息从一端传到另一端需要很长时间。这被称为光锥限制。论文指出，对于大小为 $n$ 的网格，你能混合事物的最快速度与网格的“半径”成正比（大致是 $n$ 的 $D$ 次方根，其中 $D$ 是维度数）。

先前的研究已经解决了“全对全”城市（每个人都能瞬间与任何人交谈）和一维线的问题，但中间地带——多维网格（如超导量子芯片中使用的二维网格）——一直是个谜。

解决方案：混合蛋糕的两种方法

作者提供了两种不同的配方，用于在网格上创建这些“强随机”电路。

配方 1：“拼接”法（大师建筑师）

这就像建造巨大的马赛克。你无法一次性完成整个作品，所以你先制作小块完美的瓷砖，然后将它们拼接在一起。

小瓷砖：首先，他们想出了如何在网格的一小块区域上制作一个小的、完美随机的“瓷砖”（强 2-设计）。
胶水：他们使用一种特殊的数学“胶水”（称为拼接引理），允许将这些小的随机瓷砖组合成一个巨大的随机马赛克。
结果：通过精心排列这些瓷砖，他们证明了可以在 $D$ 维网格上构建一个巨大的强随机电路，其耗时与理论速度极限（光锥）相匹配。

关键特征：此方法是最优的。它不浪费任何时间或额外原料（辅助量子比特）。这是制造这种特定类型随机性最高效的方式。

配方 2：“路由”法（交通指挥官）

想象你有一个食谱，要求混合那些目前位于房子不同房间的原料。在一个只有一条走廊（连接性有限）的房子里，你必须亲自把原料搬到搅拌碗里。

问题：最好的随机食谱是为那种每个房间都与其他所有房间相连（全对全）的房子设计的。
修正：作者使用了一种路由策略。这就像一位交通指挥官，告诉人们如何精确地穿过房子以高效地交换位置。
结果：他们拿来了“全对全”的随机食谱，并添加了一层“行走指令”（置换），将量子比特移动到彼此相邻的位置，以便它们能够相互作用。

关键特征：就量子比特总数而言，这种方法比第一种稍慢，但它非常灵活。它允许更好地控制“随机性”参数（例如检查蛋糕的次数），并且如果需要，可以使用额外的“辅助”量子比特来加速过程。

什么是“强”设计？

论文强调了**“强”**这个词。

弱随机性：想象一位魔术师洗牌。如果你只看顶部的牌，它看起来是随机的。但如果你看顶部的牌，然后翻转整副牌看底部的牌，一个“弱”的洗牌可能会揭示出某种模式。
强随机性：“强”设计就像一位魔术师，他将牌洗得如此完美，以至于即使你看了顶部的牌，翻转牌堆，看了底部的牌，然后试图逆转洗牌过程，它看起来仍然是完全随机的。

作者的构造是“强”的，这意味着即使对手试图逆向使用量子计算机，或从多个角度观察该过程，它们仍然保持随机性。

结论

论文证明，对于以网格形式排列的量子计算机（这是当今大多数真实量子芯片的构建方式），我们可以生成强随机过程，其速度达到物理定律所允许的极限。

他们通过以下方式实现了这一点：

高效地拼接小的随机块。
路由（移动）量子比特穿过网格，以模拟完全连接的系统。

这是一个重大进展，因为它告诉工程师们，在他们特定的硬件上运行这些随机电路的最快速度究竟是多少，从而确保量子计算机能够执行基准测试、密码学和模拟复杂物理等任务，而不会浪费时间和资源。

技术摘要：强随机幺正算子与几何局域性

问题陈述
本文探讨了在具有几何局域连接性的量子系统（特别是 $D$ 维网格）上构建强近似幺正 $k$ -设计和**强伪随机幺正算子（PRU）**的方法。虽然 Haar 随机幺正算子是随机性的理想模型，但它们在计算上是不可处理的。高效的近似方案（即设计）对于量子机器学习、多体物理和密码学中的应用至关重要。

文中明确区分了弱设计（仅对查询幺正算子 $U$ 的敌手安全）与强设计（对查询 $U$ 、其逆 $U^\dagger$ 、转置 $U^T$ 及共轭 $\bar{U}$ 的敌手均安全）。强设计是必要的，因为许多量子算法和物理过程涉及前向和逆向演化。

先前的工作已确立，对于全连接（all-to-all）拓扑，强设计可在 $O(\log n)$ 深度内构建，而对于一维（1D）链则需 $\Omega(n)$ 深度。然而，对于中间连接性（如 $D$ 维网格， $D > 1$ ）的最优深度仍是一个未解之谜。本文旨在确定在这些通用连接性下构建强设计和 PRU 所需的电路深度，特别关注量子比特数为 $n$ 的 $D$ 维网格。

方法论
作者在 $D$ 维网格上构建这些设计时采用了两种不同的方法：

通过拼接与笛卡尔积的直接构建：
- 强拼接引理： 作者基于 Schuster 等人 [SML+25] 提出的强拼接引理，该引理允许将较小的强幺正设计组合成更大的设计，前提是它们被夹在强 2-设计之间。
- 笛卡尔积结构： 认识到 $D$ 维网格是 1D 线图（line graphs）的笛卡尔积，作者通过迭代应用“泡利混合”（Pauli mixing）协议来构建强 2-设计。这涉及在网格的行和列上交替施加幺正算子层。
- 弱设计集成： 为确保生成的系综是强设计，将构建的 2-设计（针对特定查询组合安全）与 [SHH25] 中已知的弱相对误差 2-设计相结合。
- 递归组合： 利用强 2-设计作为构建模块，作者递归地应用拼接引理来构建强 $k$ -设计，且无需辅助量子比特。
基于路由的构建：
- 路由理论： 第二种方法利用了图路由理论的结果。在局域网格上实现非局域相互作用的任务被映射为一个路由问题，其中“石子”（量子比特）必须被置换到特定的目的地。
- SWAP 网络： 作者利用笛卡尔积图路由数的界限（特别是 [BA91] 中的定理 23），确定了将量子比特置换到可进行局域相互作用位置所需的深度。
- 编译： 现有的全连接强设计构建方案（来自 [SML+25]）通过交错随机门层与路由层（SWAP 网络）被编译到网格上。这种方法允许使用辅助量子比特以改善 $k$ 和 $\epsilon$ 的扩展性。

主要贡献与结果

最优深度强 $k$ -设计（定理 1/22）：
作者证明，对于任意常数维度 $D$ ，强 $\epsilon$ -近似幺正 $k$ -设计可在 $D$ 维网格上以如下深度构建：
$d = O\left(n^{1/D} + k \log^7(k) \log(nk/\epsilon)\right)$
该构建无需辅助量子比特。 $n^{1/D}$ 项与 $D$ 维中信息传播的自然光锥下界相匹配，确立了关于 $n$ 的最优性。
最优深度强 PRU（定理 2/27）：
假设学习带误差（LWE）问题的次指数级困难性，作者在 $D$ 维网格上构建了深度为以下的强 PRU：
$d = \Theta(n^{1/D})$
这也无需辅助量子比特，并匹配了由光锥论证提供的下界。
基于路由的近最优设计（定理 4/推论 26）：
通过将路由协议应用于全连接设计，作者提供了替代构建方案，改善了 $k$ 和 $\epsilon$ 的扩展性，但代价是使用了辅助量子比特：
1. 深度为 $O((nk)^{1/D} \text{polylog}(n,k) \log \log(1/\epsilon))$ ，使用 $\tilde{O}(nk)$ 个辅助量子比特。
2. 深度为 $O(n^{1/D} k \text{polylog}(n) \log \log(k/\epsilon))$ ，使用 $\tilde{O}(n)$ 个辅助量子比特。
向笛卡尔积的推广：
这些技术被证明不仅适用于简单网格，还适用于任何作为较小图之笛卡尔积的连接图。

意义与主张
本文声称解决了关于中间连接性下强设计深度扩展性的未解之谜。其主要意义在于证明强设计和 PRU 可以在 $D$ 维网格上以最优深度扩展（ $\Theta(n^{1/D})$ ）构建，这匹配了由光锥施加的基本物理极限。

作者指出，虽然基于路由的方法在 $k$ 和 $\epsilon$ 方面提供了更好的扩展性，但直接构建具有重要意义，因为它在不使用辅助量子比特的情况下实现了关于 $n$ 的最优性，而这是近期量子硬件的关键约束。这项工作弥合了理论上的全连接模型与实际量子设备（如超导量子比特、硅量子点）中发现的几何局域架构之间的差距。论文明确指出，将这些技术扩展到非笛卡尔连接性（如六边形晶格）仍然是一个未解问题。