On the Complexity of Quantum States and Circuits from the Orthogonal and Symplectic Groups

本文证明，由辛群和特殊正交群生成的随机量子态和电路展现出与由完整幺正群生成的态和电路相当的指数级大复杂度和近正交性，同时确立了学习此类结构化电路的平均情况困难性。

要点

想象一下，你正试图烘焙一款尽可能复杂且不可预测的蛋糕。在量子物理的世界里，这款“蛋糕”就是一个量子态，而“食谱”则是一个量子电路（一系列操作）。

通常，科学家认为制作一款真正随机且复杂的蛋糕的最佳方式，是使用一个能够完成任何任务的“通用搅拌机”。这被称为Haar 测度（或完整酉群）。这就像拥有一个配备了所有可能工具、食材和技术的厨房。

核心问题：
本文问道：我们真的需要整个厨房吗？ 如果我们将自己限制在一个更小、更有组织的工具集中——具体来说，那些只能制作实数蛋糕的工具（正交群），或具有特定对称性的蛋糕工具（辛群）——这些受限的厨房是否仍然能够制作出与通用厨房中制作出的蛋糕一样复杂且难以预测的蛋糕？

简短回答：
是的。 作者证明，即使使用这些受限的、具有“结构”的工具包，生成的量子态与使用完整工具包生成的量子态一样，具有令人难以置信的复杂性且难以理解。

以下是他们发现的分解，使用了日常类比：

1. 蛋糕的“复杂性”

在量子术语中，“复杂性”意味着将一个特定的量子态与一个完全无聊、混合的状态（如一盆普通面粉）区分开来的难度。

• 发现： 如果你使用这些受限的工具包（正交群或辛群）来烘焙蛋糕，结果几乎总是指数级复杂的。
• 类比： 想象你有一本简单的食谱书。如果你试图仅用几个简单的步骤（门）来重现由这些受限群制作的蛋糕，你将失败。蛋糕如此错综复杂，以至于所需的步骤数量巨大到 practically 无法写下来。本文表明，尽管这些群比完整的可能性宇宙“小”，但它们仍然产生了难以逆向工程的、不可能复杂的蛋糕。

2. 状态的“拥挤房间”

作者还研究了这些蛋糕彼此之间的差异程度。

• 发现： 你可以将大量这些复杂的状态塞进一个“房间”里，而它们彼此之间几乎都呈正交（意味着它们彼此之间的差异达到了两个状态所能达到的最大差异）。
• 类比： 想象一个挤满了人的房间。如果每个人都戴着一顶略有不同的帽子，他们就是独特的。但在这里，作者表明，你可以在房间里塞进“双重指数级”数量的人，而每个人戴的帽子都完全独特，且与他人的帽子截然不同。尽管“制帽机器”（群）是受限的，但它仍然产生了令人眩晕的多样化独特结果。

3. “猜谜游戏”（学习食谱）

本文的第二大部分是关于学习。想象你是一名侦探，试图仅通过品尝几块碎屑（测量数据）来找出蛋糕的食谱。

• 发现： 如果你只能品尝几块碎屑，要学习这些蛋糕的食谱是极其困难的。
• 类比： 假设你试图猜测一个秘密代码。如果该代码是由这些受限群生成的，它看起来如此随机和均匀，以至于猜测它简直是一场噩梦。
  • 本文证明，即使你拥有一台非常强大的计算机，你也需要品尝数量大得不可思议的碎屑（查询）才能找出规律。
  • 这就像试图通过一次捡起一粒沙子来在沙滩上找到特定的一粒沙子。沙滩如此之大（复杂性如此之高），以至于你需要捡起的沙粒数量超过宇宙中的原子总数，才能确信你找到了正确的那一粒。

4. 为什么这很重要（在本文的语境中）

作者基于仅他们写到的内容，提到了几个具体原因，说明这为何重要：

• 硬件现实： 真实的量子计算机往往存在物理限制。由于硬件的构建方式，它们可能自然地产生“实数”状态（正交）或具有特定的对称性（辛群）。本文让我们放心，即使存在这些物理限制，计算机仍在执行极其复杂且“混乱”的操作。
• 安全与验证： 由于这些状态如此难以预测和学习，它们是证明量子计算机实际上正在执行普通计算机无法完成的任务（量子优势）的绝佳候选者。这就像一把极其复杂的锁，即使是一位大师级的小偷（经典计算机）也无法在不耗费永恒时间的情况下将其撬开。
• 机器学习： 如果你尝试使用这些群来训练量子机器学习模型，你可能会陷入“ barren plateau”（ barren 高原）。这就像试图攀登一座顶部完全平坦的山；无论你向哪个方向迈步，你都无法爬得更高（你学不到任何东西）。本文表明，仅仅在你的模型中添加对称性并不会自动使其更容易训练；它可能仍然过于复杂。

总结

本文是一个数学证明，表明约束并不一定会降低复杂性。即使你将量子工具限制在特定的、结构化的群中（如真实硬件中使用的群），生成的量子态仍然：

1. 极其复杂（难以创建或描述）。
2. 极度独特（难以相互混淆）。
3. 无法从有限数据中学习。

这有点像发现，即使是一个小型的、专业的工具箱，也能建造出一座如此复杂的房屋，以至于没有人能仅通过观察砖块就弄清楚它是如何建造的。

技术摘要

技术摘要：关于正交群与辛群量子态及电路的复杂性

1. 问题陈述

理解量子态与量子电路的复杂性是量子信息科学中的核心挑战，其影响波及多体物理、高能物理及量子学习理论。传统上，典型态与电路的行为是通过从全酉群 $U(D)$ 上的 Haar 测度采样酉变换来建模的。然而，许多物理和算法背景涉及从特定子群抽取的具有结构的酉变换，例如特殊正交群 $SO(D)$、酉辛群$Sp(D/2)$以及特殊酉群$SU(D)$。

本工作解决的核心问题是：这些结构化子群能否复现通常归因于 Haar 随机酉变换的平均情况属性？具体而言，作者研究了：

1. 态复杂性：由这些经典紧致群中的酉变换生成的随机态是否表现出高“强态复杂性”（即，是否难以使用有界大小的电路将其与最大混合态区分开）？
2. 学习难度：从这些子群抽取的电路的输出分布（Born 分布）在统计查询（SQ）模型中是否难以学习？

2. 方法论

作者结合测度集中现象与高斯积分技术，分析了由经典紧致群 $G \in \{SU(D), SO(D), Sp(D/2)\}$ 诱导的系综，其中 $D=2^n$。

• 测度集中：分析主要依赖 Lévy 引理，该引理指出紧致群上的 Lipschitz 函数集中在其均值附近。作者利用针对每个群的具体集中常数（$C_{SO}, C_{Sp}, C_{SU}$）来界定态可区分性及输出分布属性的波动。
• 高斯积分重构：为了在不依赖 Weingarten 演算的情况下评估这些群上的平均值，作者将 Haar 平均值重构为对标准独立高斯随机变量的期望。该技术统一了偶次齐次函数在正交、辛和酉情形下的处理。
• 统计查询（SQ）框架：学习问题在 SQ 模型中形式化，其中算法仅通过有界测试函数期望的 $\tau$ 精度估计值来访问目标分布。这模拟了近中期量子设备（有限采样统计）和噪声测量的局限性。
• 设计理论：结果被推广到这些群上的 $\varepsilon$-近似 $k$-设计，利用了设计矩与 Haar 矩接近度的界限。

3. 主要贡献与结果

A. 高强态复杂性与几何分离

作者确立，使用辛或正交酉变换生成的随机量子态通常表现出指数级大的强态复杂性。

• 定理 3：对于从 $SO(D)$、$Sp(D/2)$或$SU(D)$ 的 Haar 诱导系综中抽取的随机态 $|\psi\rangle$，若电路大小 $r$（由基本门组成）满足 $r \lesssim D/\log n$，则利用该电路将其与最大混合态区分开的概率在系统维度 $D$ 上是指数级小的。该结果对精确 Haar 系综和近似 $k$-设计（$k>3$）均成立。
• 定理 4：高复杂性与强几何分离是相容的。作者证明，可以在这些系综中打包双指数级数量的态，使得每个态都具有高复杂性，且任意一对态在迹距离上几乎达到最大分离。这证实了这些结构化系综并未聚集在低复杂性区域。

B. 学习 Born 分布的平均情况难度

本文证明了从这些经典群抽取的电路的输出分布的学习在 SQ 模型中是平均情况困难的。

• 定理 5 与 6：作者计算了控制 Born 分布 $P_U$ 与均匀分布之间平均总变差距离的显式常数（$M_G$）。他们表明，对于 $SO(D)$和$Sp(D/2)$，这些分布平均而言远离均匀分布。
• 查询复杂度：通过结合测度集中（表明大多数电路远离均匀分布）与 SQ 下界框架（引理 2），作者证明，即使以非平凡精度学习这些 Born 分布的极小部分，也需要双指数级数量的查询（$q = 2^{2^{\Omega(n)}}$）。这种难度适用于正交群和辛群，正如它适用于全酉群一样。

C. 技术统一

一个重要的方法论贡献是利用高斯积分定理推导这些界限。这种方法避免了 Weingarten 演算的复杂性，并为正交、辛和酉情形提供了统一的证明技术，从而得出了显式的平均情况界限。

4. 意义与影响

本文声称，酉群的结构化子群可以表现出与全酉群相当的复杂性。这些发现的意义在以下几个语境中被阐述：

• 伪随机性与混沌：结果支持了这样的观点，即“类 Haar"输出统计和高复杂性可以在结构化设置（如实值编码或辛电路）中以浅层深度出现，这对于模拟量子混沌和量子引力至关重要。
• 量子学习理论（QML）：这些发现挑战了通过向量子电路 Born 机器（QCBMs）注入对称性以逃避训练障碍（如 barren plateaus）的策略。作者表明，仅将 ansatz 限制在 $SO(D)$或$Sp(D/2)$ 并不能恢复输出分布的可学习性。这表明过度表达性的对称 ansatz 仍可能遭受平均情况难度的困扰，从而促使采用热启动或更受约束的模型。
• 量子优势与验证：这些群产生的输出分布远离均匀分布这一事实，使其成为“重输出生成”任务的合适候选者，这是一种被提议用于验证量子优势的方法。
• 密码学与黑洞：学习这些分布的平均情况难度与基础领域相关联，如量子密码学（伪随机态生成）和黑洞动力学研究，其中类似的复杂性理论障碍是相关的。

总之，这项工作表明，学习和计算的难度以及典型态的高复杂性是稳健的特征，即使随机性被限制在经典紧致子群中，只要系综足够丰富（例如 $k>3$ 的 $k$-设计），这些特征就会持续存在。