Quantum algorithms for the exponentiation of Toeplitz matrices and applications in partial differential equations

技术摘要：托普利茨矩阵指数运算的量子算法

问题陈述
偏微分方程（PDEs）是模拟物理现象的基础，这些现象通常通过空间离散化简化为线性系统的时演问题 $\partial_t u = Au$，其解为 $u(t) = e^{At}u(0)$。由此类离散化产生的矩阵 $A$ 通常是带状托普利茨（banded Toeplitz）或拟托普利茨（quasi-Toeplitz）矩阵。虽然量子计算机为解决此类问题提供了潜在的指数级优势，但存在一个显著的瓶颈：标准的量子算法依赖于酉变换，而 PDE 算子中的矩阵指数 $e^{At}$ 通常是非酉的。

现有的方法利用块编码（block-encoding）框架将次归一化矩阵 $A/\alpha$ 嵌入到一个更大的酉矩阵中。然而，对于像拉普拉斯算子这样的微分算子，其范数 $\|A\|$ 会随着网格间距 $\delta_x$ 的减小而发散（例如，$\|\Delta\| \sim 4/\delta_x^2$）。这导致需要一个巨大的次归一化因子 $\alpha$，从而使得基于量子信号处理（QSP）或量子奇异值变换（QSVT）的算法复杂度随之大幅增加。此外，此前尚未有针对直接对指数 $e^{At}$ 进行块编码的研究，因为任意托普利茨矩阵通常不是可对角化的。

方法论
作者提出了一个量子框架，通过直接构建带状托普利茨矩阵指数的块编码来规避归一化瓶颈。该方法依赖于利用这些矩阵的代数结构：

1. 分解为可对角化生成元：
   尽管一般的托普利茨矩阵 $T$ 不一定可对角化，但它可以表示为下移位算子（$L_n$）和上移位算子（$L_n^\top$）的多项式。这些移位算子是幂零且不可对角化的。然而，作者将它们与循环生成元 $C_n$ 和斜循环生成元 $N_n$ 联系起来。$C_n$ 和 $N_n$ 都是酉矩阵，并可通过量子傅里叶变换（QFT）进行对角化。具体而言，移位算子可以写成 $C_n$ 和 $N_n$ 幂次的线性组合。

2. 通过截断泡利串实现的近似块编码：
   循环生成元 $C_n$ 的特征值构成一个对角矩阵 $\Gamma_n$。作者引入了一种高效的近似方法，通过截断 $\Gamma_n$ 中较小的相位分量来构造近似 $\tilde{\Gamma}_{d,n}$。该近似被分解为一组交换的泡利-$Z$ 串之和，并具有闭合形式的 Frobenius 范数误差界。由于生成的泡利串是交换的，它们的指数运算可以简化为单比特旋转的乘积，这可以高效实现。

3. QFT-Trotter 乘积公式：
   为了处理一般的非对角化托普利茨矩阵，作者应用了 Lie-Trotter 乘积公式。通过将托普利茨矩阵分解为循环分量和斜循环分量的和（这两者均可通过 QFT 对角化），指数 $e^{Tt}$ 可以通过对这些可对角化分量的指数进行乘积来近似。这产生了一个专门的 QFT-Trotter 乘积公式。

4. 带有频率截断的热传导方程应用：
   作为一个具体的应用，该框架被用于处理离散热传导方程（$\partial_t u = \Delta u$）。在周期性边界条件下，离散拉普拉斯算子 $\Delta$ 是循环矩阵。作者观察到，传播子 $e^{\Delta t}$ 的特征值在远离低频模式时迅速衰减。通过引入频率截断 $k_c$，他们将算子截断为一个窄带低频区域。这种截断消除了 $\delta_x^{-2}$ 的范数缩放。

   • 对于由此产生的非酉传播子，作者采用哈密顿量模拟的线性组合（LCHS）将演化过程表示为斜埃尔米特（skew-Hermitian）酉矩阵的线性组合。
   • 该组合中的每个酉矩阵都使用前述的截断泡利串分解进行实现。
   • 该方法通过利用离散正弦变换（DST）和离散余弦变换（DCT）扩展到了狄利克雷（Dirichlet）和诺依曼（Neumann）边界条件，并将这些变换嵌入到 $(n+1)$ 个量子比特的块编码中。

主要贡献与结果

• 直接指数运算： 本文提出了首个直接构建带状托普利茨矩阵指数块编码的方法，避免了先对矩阵 $A$ 进行编码再应用 QSP/QSVT 的中间步骤。
• 高效分解： 提出了一种新型的可控循环特征相位向泡利串的截断方法，其提供的闭合形式误差界取决于截断深度 $\delta = n-d$，而非系统规模 $n$。
• QFT-Trotter 公式： 通过利用托普利茨矩阵分解为 QFT 可对角化酉矩阵的特性，建立了一个专门的乘积公式。
• 消除归一化瓶颈： 在热传导方程的应用中，频率截断策略使得构造出的传播子具有 $O(1)$ 的次归一化因子。这与直接对拉普拉斯算子进行块编码形成鲜明对比，后者的次归一化因子随 $O(1/\delta_x^2)$ 缩放，使得 QSP/QSVT 在细网格下难以实现。
• 误差界： 总误差由与 Trotter 步数和截断误差相关的项组成，具体为 $O(t^2/c \|\alpha\|_1^2) + O(\pi t m / (2\delta) \|\alpha\|_1)$，其中 $c$ 是 Trotter 步数，$m$ 是带宽。

意义
作者指出，这项工作提供了一种通用的方法论，通过利用带状托普近期算子的代数结构来克服与 PDE 求解器相关的、高昂的次归一化因子成本。通过直接处理这些矩阵的指数，该方法实现了 $O(1)$ 的次归一化，使其适用于算子范数很大（在微分算子离散化中很常见）但带宽相对于系统规模较小（$m \ll 2^n$）的情景。

作者提到，虽然之前的研究已经讨论了托普利茨算子或拉普拉斯算子的块编码，但并未在不产生高次归一化成本的情况下，直接构建时间演化问题所需的指数形式 $e^{Tt}$。这项工作填补了这一空白，为结构化矩阵提供了一种专门且高效的替代方案。

局限性
作者明确指出了两个局限性：

1. 定理 V.1 中的 Trotter 误差界包含了一些常数，对于非收缩系数集，这些常数可能会随 $t\|\alpha\|_1$ 指数级增长；对于一般带状托普利茨算子，寻找更紧致的界限仍是一个开放性问题。
2. 用于近似的占主导地位的泡利串子集（$\Omega$）的选择目前是基于观察到的模式进行的启发式选择。若要完全强化结果，需要建立关于 $\Omega$ 大小相对于目标误差的严格先验界限。