A Quantum Computational Perspective on Spread Complexity

本文通过证明扩散复杂度是涉及时间演化和叠加的合成框架的极限情形，在扩散复杂度与量子线路复杂度之间建立了直接联系，从而为传统方法（如兰佐斯算法）提供了物理诠释并带来了计算优势。

要点

想象你正试图用黏土制作一件特定且复杂的雕塑。在量子物理世界中，这件“雕塑”是系统的特定状态，而“黏土”则是构成该系统的信息。

长期以来，物理学家一直有两种不同的方法来衡量制作这些雕塑的“难度”。

1. “电路”方式：这种方法计算你需要使用多少种特定工具（逻辑门），才能将一块简单的黏土塑造成你的目标雕塑。这就像计算食谱中的步骤数量。
2. “扩散”方式：这种方法测量黏土随时间演化时“扩散”或散开的程度。这就像测量黏土从其原始位置滚动了多远。

问题在于，这两种衡量方法一直生活在彼此隔离的世界中。“扩散”方式非常适合理解混沌系统（如黑洞或湍流流体），但它往往过于抽象且难以计算。如果数学变得过于狂野（发散），标准工具就会失效。

本文的核心思想
本文作者在这两个世界之间架起了一座桥梁。他们提出了一种新的思考“扩散”测量的方法，将其视为一种特定类型的“电路”测量。

以下是他们使用的类比：

量子“分束器”设置

想象你有一束光（你的初始状态）。你想将其转化为复杂的图案（你的目标状态）。为此，你被允许使用以下两种工具：

1. 时间旅行者（幺正门）：这个工具将光向前推进时间。这就像在视频播放器上按“下一帧”。这需要付出代价（计算努力）。
2. 魔法分束器（Beam Splitter）：这个工具将一束光分成两束，或将两束光合并为一束。关键在于，在这个特定模型中，这个工具是免费的。它不需要任何代价。

他们如何建立联系

作者问道：“使用这些工具，以最低成本构建我们的目标雕塑的方法是什么？”

他们发现，如果你利用免费的“魔法分束器”来创建叠加态（混合光束），并利用付费的“时间旅行者”来演化系统，那么构建目标状态的最有效路径自然会生成一组特定的构建模块。

这些构建模块恰好与“扩散”测量中使用的模块（称为 Krylov 基）完全相同。

“无穷小”技巧
奇迹发生在当你让“时间旅行者”以极小、极小的步长（无穷小时间步）移动时。

• 如果你采取大步，你会得到一个复杂的电路。
• 如果你将步长缩小到几乎为零，使用这种新“分束器”方法构建雕塑的成本将完美收敛于旧的“扩散”复杂度数值。

为何这很重要（根据本文）

本文声称，这种新视角提供了两个主要优势：

1. 赋予物理意义：它解释了“扩散”复杂度实际上是什么。它不仅仅是一个抽象的数学公式；它是利用时间演化和免费叠加态构建状态所需的最低成本。
2. 修复失效的数学：传统计算“扩散”复杂度的方法（使用所谓的 Lanczos 算法）通常在系统变得过于混乱或数值过大（发散）时失效。
   • 本文的解决方案：他们的新方法只需要你在特定时间点检查“返回振幅”（一种衡量系统看起来多大程度上像初始状态的简单测量）。它不需要可能导致爆炸的导数或高阶数学。即使在旧方法崩溃的情况下，它依然有效。

一个具体实例

为了证明这行之有效，作者在特定的数学系统 SU(2)（与粒子自旋相关）上测试了该方法。

• 他们使用不同步长的新“电路”方法计算了复杂度。
• 随着他们将时间步长变得越来越小，他们的新计算平滑地转化为已知的“扩散”复杂度结果。
• 他们还表明，对于某些棘手的情况，他们的方法保持稳定，而传统方法则会失效。

总结

简而言之，本文指出：“扩散复杂度”只是伪装成“电路复杂度”。 如果你使用时间演化和免费混合来构建量子态，并且采取微小步长，你所付出的成本正是“扩散”复杂度。这为我们提供了一种新的、更稳健的工具，用于测量那些旧工具失效的系统中的复杂度。

技术摘要

技术摘要：扩展复杂性的量子计算视角

问题陈述
量子复杂性沿着两条大致平行的轨迹发展：物理系统中的动力学复杂性（例如算符增长、黑洞动力学）和量子信息中的操作电路复杂性。虽然“扩展复杂性”已成为诊断量子混沌、可积性破缺和相变的有效工具，但其物理诠释仍然抽象。此外，其标准计算依赖于 Lanczos 算法，该算法需要哈密顿量的高阶矩或返回振幅的导数。这种方法在具有发散矩、非微扰动力学或返回振幅非解析的系统中会失效或变得定义不明确。本文旨在弥合扩展复杂性与电路复杂性之间的差距，为前者提供物理诠释，并提供一种稳健的计算方法，以避免 Lanczos 算法的局限性。

方法论
作者提出了一种计算框架，其中目标态是通过作用于分布在 $n$ 个“波束”（beams）上的系统的三种基本操作合成的：

1. 波束分裂（$Q$）： 一种幺正操作，将 $n$ 波束矢量映射为 $(n+1)$ 波束矢量，有效地创建叠加态。
2. 波束重组（$S$）： 一种叠加操作，将 $(n+1)$ 波束矢量映射回 $n$ 波束矢量，保持总概率守恒。
3. 幺正门（$A$）： 作用于单个波束的标准幺正操作。

作者为这些操作分配了具有特定约束的计算成本：

• 波束分裂（$Q$）和重组（$S$）被分配零成本。
• 幺正门（$A$）被分配1的成本。
• 合成一个态的信道成本定义为应用 $A$ 的次数（电路深度）。

目标态 $|\psi\rangle$ 的复杂性定义为合成该态所需的最小成本。作者基于态制备通过深度为 $k$ 的信道的概率构建了一个成本函数，并以 $k$ 为权重。通过在信道设计参数上最小化该成本，他们推导出了一组由幺正算符 $A$ 和零成本叠加态生成的最优相互正交态 $\{|\kappa_n\rangle\}$。

主要贡献与结果

1. 正交基的推导：
   作者证明，最优合成信道产生了一个基 $\{|\kappa_n\rangle\}$，其中每个态 $|\kappa_n\rangle$ 是 $\{A^m|\kappa_0\rangle\}_{m=0}^n$ 的线性组合。态 $|\psi\rangle$ 的复杂性被证明是期望值 $\langle \psi | \hat{K} | \psi \rangle$，其中 $\hat{K} = \sum n |\kappa_n\rangle\langle\kappa_n|$。

2. 与扩展复杂性的联系：
   核心结果表明，扩展复杂性作为该电路复杂性框架的极限情况出现。当幺正门 $A$ 被识别为无穷小时间演化算符 $A = e^{-i\Delta H}$ 并取极限 $\Delta \to 0$ 时：

   • 基 $\{|\kappa_n\rangle\}$ 收敛于由哈密顿量 $H$ 生成的标准 Krylov 基 $\{|K_n\rangle\}$。
   • 成本算符 $\hat{K}$ 收敛于标准的扩展复杂性算符。
   • 电路复杂性收敛于已知的扩展复杂性。

3. 计算优势：
   与需要返回振幅的导数或高阶矩（这些矩可能会发散）的 Lanczos 算法不同，所提出的方法仅依赖于返回振幅 $R(\tau) = \langle \kappa_0 | e^{-i\tau H} | \kappa_0 \rangle$ 的离散评估。

   • 该方法利用由离散时间步长处的 $R(\tau)$ 构建的矩阵 $S$。
   • 正交基系数通过对 $S$ 进行 Cholesky（或 LU）分解导出。
   • 这种方法在返回振幅定义明确但其泰勒级数发散的非微扰区域中仍然稳健。

4. 显式 $SU(2)$ 示例：
   该框架在具有哈密顿量 $H = \alpha(J_+ + J_-)$ 的 $SU(2)$ 系统上进行了测试。

   • 对于有限时间步长 $\Delta$，显式计算了电路复杂性。
   • 当 $\Delta \to 0$ 时，结果收敛于扩展复杂性的已知解析表达式。
   • 作者指出，对于有限的 $\Delta$，复杂性是周期性的但不具有时间反演对称性，这一特征归因于离散时间步长门 $A$ 的单向性质。

5. 与 Nielsen 复杂性的关系：
   本文讨论了该电路复杂性与几何（Nielsen）复杂性之间的联系。对于由李代数支配的系统，Krylov 复杂性（进而推导出的电路复杂性）被证明与使用 $F_1$ 成本函数计算的几何 Nielsen 复杂性成正比，从而将算符增长与幺正空间中的测地线运动联系起来。

意义与主张
作者声称，这项工作为扩展复杂性提供了具体的物理诠释，将其识别为使用时间演化和叠加操作合成态的最小成本。这一视角通过将扩展复杂性锚定在量子电路模型中，使其去神秘化。

此外，本文提供了一种实用的计算工具。通过绕过对导数和高阶矩的需求，该方法允许在传统方法失效的场景（例如发散矩或非微扰动力学）中计算复杂性。作者强调，该框架将扩展复杂性置于量子信息的更广阔图景中，可能促进高能物理与量子计算之间的交叉融合，例如为复杂动力学设计量子算法或利用物理直觉优化电路。

本文明确指出，这种构造并不与关于 Krylov 复杂性作为态空间度量的不可行定理相矛盾，因为他们的电路模型将特定的参考态固定为输入，从而避免了定义任意中间态之间的距离。最后，作者建议，他们的离散门方法不同于并补充了以往针对电路复杂性的连续流形方法，特别是它不需要动力学对称性的存在。