Sparse Carleman Embeddings for Nonlinear Discrete Dynamical Systems

技术摘要：用于非线性离散动力系统的稀疏 Carleman 嵌入

问题陈述
本文解决了模拟离散非线性动力系统（形式为 $x_{n+1} = F(x_n)$，特别关注强迫二次迭代 $x_{n+1} = f + Ax_n + Bx_n \otimes x_n$）的计算挑战。这些系统出现在人口建模、流体力学和机器学习（例如梯度下降优化和循环神经网络）中。虽然量子线性系统算法（QLSA）为线性系统提供了指数级的加速，但将问题应用到非线性动力学需要将其提升到更高维度的线性空间。识别出的主要障碍包括：

1. 截断误差： Carleman 嵌入将非线性更新转换为无限的线性递推。截断这一层级会引入误差，这些误差必须在长迭代周期内保持受控。
2. 稀疏性丢失： 在离散设置中，一个关键问题是，即使原始系数映射（$f, A, B$）是稀疏的，提升后的 Car मामला 矩阵往往会变得稠密。例如，如果 $A$ 的行稀疏度为 $s_A$，则度数为 $N$ 的块 $A^{\otimes N}$ 的稀疏度可能为 $s_A^N$，这使得标准的稀疏访问量子算法效率低下。
3. 条件数： 用于求解状态历史的线性系统必须具有可控的条件数，以确保高效的量子求解。

方法论
作者提出了一个结合了 Carleman 嵌入与一种新型稀疏辅助表示以及历史状态线性系统表述的框架。

1. Carleman 嵌入与截断：
   状态被提升为一个包含张量幂 $(1, x_n, x_n^{\otimes 2}, \dots)$ 的向量 $X_n$。非线性更新变为线性递推 $X_{n+1} = L X_n$。作者分析了保留最高度数为 $N$ 的截断系统 $y^{(N)}_{n+1} = L_N y^{(N)}_n$。

2. 稀疏辅助实现：
   为了克服 $L_N$ 的稠密性，作者构建了一个精确的辅助线性系统表示。他们没有显式地构造稠密的张量积，而是引入了一个辅助算子 $C$ 和嵌入 $E_{in}, E_{out}$，使得：
   $$L_N = E_{in}^\dagger (I - C^\dagger)^{-1} E_{out}$$
   算子 $C$ 被构造为逐个张量因子地应用原始系数映射（$f, A, B$）。至关重要的是，由此产生的矩阵 $D = I - C^\dagger$ 的行和列稀疏度被限制在 $1 + s_f + s_A + s_B$ 以内，该界限与截断度 $N$ 无关。这使得可以使用稀疏访问 QLSA，而无需展开稠密的张量结构。

3. 重缩放与历史系统：
   为了控制 $n$ 次迭代过程中线性系统的条件数，作者使用稳定性区域内的半径 $r$ 对系数进行重缩放。随后，他们构建了一个“历史系统”，将前 $n$ 个时间步耦合进单个稀疏线性系统 $\tilde{A}_n \mathbf{w} = \mathbf{b}$ 中。

   • 条件数： 他们证明了条件数 $\kappa(\tilde{A}_n)$ 随 $n$ 线性增长（$\Theta(n)$），且常数与截断度 $N$ 无关。
   • 状态提取： 为了减轻从历史状态中提取最终状态时固有的 $1/n$ 概率损失，他们采用了“终端填充（terminal padding）”技术，即重复最后一次辅助向量 $n$ 次。这使得提取物理状态的成功概率独立于 $n$（仅取决于状态的范数）。

核心贡献与结果

1. 一致几何收敛性：
   在明确的稳定性假设（假设 1）下，作者证明了度数为 1 的块（物理状态近似）的截断误差随嵌入度 $N$ 呈几何级数下降。具体而言，$\sup_{n \ge 0} \|x_n - y^{(N)}_{n,1}\| \le \rho R^N$，其中 $R < 1$。这意味着对于固定的误差容限 $\epsilon$，只需 $N = O(\log(1/\epsilon))$ 的截断度即可，且与迭代次数 $n$ 无关。

2. 提升更新的稀疏表示：
   本文构造了一个使用辅助算子的精确表示，该算子的稀疏度由与 $N$ 无关的界限限制。这解决了离散 Carleman 提升中典型的“稀疏性爆炸”问题，从而实现了高效的量子访问。

3. 量子算法复杂度：
   作者推导出了一个用于准备近似归一化第 $n$ 次迭代 $x_n / \|x_n\|$ 状态的量子算法。

   • 查询复杂度： 该算法以常数成功概率实现迹距离误差 $\epsilon$。其查询复杂度为 $O(s n K_r \Gamma \log(\Gamma/\epsilon))$，其中 $s$ 是稀疏度界限，$n$ 是迭代计数，$\Gamma$ 取决于稳定性参数和 $\|x_n\|$ 的下界 $\xi$。
   • 缩放： 对于固定的稳定性参数和 $\xi$，复杂度对于 $n$ 是线性的，并且对于 $1/\epsilon$ 是多项式对数级的。
   • 假设： 该结果依赖于对系数的相干输入访问以及已知最终状态范数的正下界。

4. 数值验证：
   在一维和三维中的数值实验证实了理论收敛率。结果表明，截断误差随 $N$ 呈几何级数下降，且轨迹收敛至预测的稳定不动点。

意义与主张
本文声称，提供了第一个针对离散二次系统进行 Carleman 嵌入的严谨分析，该分析同时解决了量子实现中的截断误差、稀疏性和条件数问题。

• 关注点分离： 这项工作成功地将 Carleman 近似（由 $N$ 控制）的精度要求与量子求解器（由辅助构造控制）的稀疏性要求分离开来。
• 高效性： 通过证明历史系统的条件数与 $N$ 无关且保持了稀疏性，作者证明了可以将收敛的 Carleman 近似与量子实现相结合，而不会导致总成本随着截断度的增加而爆炸。
• 范围： 研究结果特定于一类稳定的二次离散动力系统。作者指出，虽然该方法可扩展到更高阶的多项式，但目前的分析侧重于二次情形。他们承认，将这些保证扩展到更广泛的非多项式类或分析观测值估计的完整成本仍是开放的研究方向。

文章得出结论，在所述假设下，可以利用一种量子算法准备非线性映射的第 $n$ 次迭代近似，其成本随迭代次数呈线性缩放，这为在量子硬件上模拟复杂的离散动力学提供了一条潜在路径。