量子偏微分方程（PDE）求解是量子计算最具变革性潜力的应用之一。PDE 描述了物理世界的基本规律——流体力学、电磁学、量子场论、金融定价——经典求解的计算代价随维度指数增长。本文系统梳理量子 PDE 求解的复杂度演进史，从 2017 年的初步方案到 2024 年的最优结果。

问题定义

PDE 的一般形式

$$\frac{\partial u}{\partial t} = \mathcal{L}[u] + f(\mathbf{x}, t), \quad u(\mathbf{x}, 0) = u_0(\mathbf{x})$$

其中 $\mathcal{L}$ 是空间微分算符（如 $\Delta$, $\nabla \cdot$, $\nabla \times$），$f$ 为源项。

主要 PDE 类型：

经典复杂度

对 $d$ 维空间，$N$ 个格点/维，精度 $\varepsilon$：

维度灾难：复杂度随 $d$ 指数增长——$d = 3$ 时 $N^3$ 已巨大，$d > 10$ 时经典方法完全不可行。

量子 PDE 求解的复杂度演进

第一代：量子模拟直接方法（2017-2019）

Lloyd et al. (2019) 和 Berry (2017, 2020)：

对线性 PDE，空间离散化后得到线性 ODE $\dot{\mathbf{u}} = A\mathbf{u}$，$A$ 由空间差分矩阵构成。

方法：Trotter 分解 $e^{iA\Delta t}$，逐步推进。

复杂度：

$$O\left(L \cdot n \cdot \frac{T}{\Delta t} \cdot \frac{1}{\varepsilon^{1/(2p)}}\right)$$

$L$ 为 $A$ 的稀疏度，$n = \lceil\log_2 N^d\rceil$ 量子比特。

关键限制：对 $d$ 维空间，$N^d$ 个格点需要 $n = d\log N$ 量子比特，空间复杂度指数改善，但时间复杂度仍为 $O(N^d)$（因 Trotter 步数与格点数有关）。

第二代：高阶方法（2020-2022）

Costa, An, Jordan, Liu (Quantum 2022)：

将高阶 Trotter 与多步法结合，显著降低步数依赖。

改进：从 $O(T/\varepsilon^{1/(2p)})$ 步改进为 $O(T^{1+1/p}/\varepsilon^{1/p})$ 步（$p$ 为积分阶数）。

关键思想：用高阶 Magnus 展开处理时变哈密顿量，用高阶 Suzuki 公式降低 Trotter 误差。

复杂度：

$$O\left(L \cdot n \cdot \left(\frac{T^{1+1/p}}{\varepsilon^{1/p}} + \log(1/\varepsilon)\right)\right)$$

第三代：Schrödingerization（2022-2024）

Jin, Liu, Yu（2022 年底起，多篇论文）：

突破性方法——不需要哈密顿量 Hermitian，不依赖 Trotter 分解。

核心思想：通过 Laplace 变换引入辅助维度，将任意线性 PDE 转化为薛定谔方程（见 Schrödingerization 教程）。

对 PDE 的应用：

对一般线性 PDE $\partial_t u = \mathcal{L}u$（$\mathcal{L}$ 可以是非 Hermitian 的微分算符）：

1. 空间离散化：$\mathcal{L} \to A$（$N^d \times N^d$ 矩阵）
2. Schrödingerization：$\mathcal{H} = (A + A^\dagger)/2 \otimes I + (A - A^\dagger)/(2i) \otimes P$
3. 量子模拟：$e^{-i\mathcal{H}t}$

复杂度：

$$O\left(\text{poly}(n) \cdot (\|A\|t + \log(1/\varepsilon))\right)$$

突破：$\|A\|t$ 可以远小于 $N^d$（对局域算符，$\|A\| = O(1)$），因此总复杂度为 $O(\text{poly}(n) \cdot T)$。

第四代：黑盒 PDE 求解（2023-2024）

An, Liu, Lin (PRL 131, 150601, 2023)：

提出线性组合哈密顿量模拟（LCHS）+ 自适应态制备的框架，对非齐次线性 PDE 和非线性 PDE 实现了更优复杂度。

对非齐次 PDE：$\partial_t u = \mathcal{L}u + f$

Duhamel 公式：$u(T) = e^{\mathcal{L}T}u_0 + \int_0^T e^{\mathcal{L}(T-s)}f(s)ds$

量子实现：

1. 将积分离散化为 $M$ 个时间步
2. 每步用 LCHS 实现 $e^{\mathcal{L}\delta}$（对非 Hermitian $\mathcal{L}$）
3. 用受控操作叠加所有时间步

复杂度改进：从 $O(T^2/\varepsilon)$ 降至 $O(T \cdot \text{poly}\log(T/\varepsilon))$。

主要 PDE 类型的具体处理

热方程（抛物型）

$\partial_t u = \kappa \Delta u$

经典：$A = \kappa \Delta$（负半定 Hermitian），$e^{At}$ 是收缩的。

量子挑战：$e^{i(-iA)t} = e^{At}$ 需要”虚时间演化”——不是酉操作。

解决方案：

• Schrödingerization：将 $A$ 的 Hermitian 化，通过后选择实现收缩
• QSVT：实现 $P(A) \approx e^{At}$ 的多项式逼近
• 复杂度：$O(\text{poly}(n) \cdot T)$

波方程（双曲型）

$\partial_{tt} u = c^2 \Delta u$

降阶：令 $v = \partial_t u$，得到一阶系统：

$$\partial_t \begin{pmatrix} u \\ v \end{pmatrix} = \begin{pmatrix} 0 & I \\ c^2 \Delta & 0 \end{pmatrix} \begin{pmatrix} u \\ v \end{pmatrix}$$

哈密顿量为 $H = \begin{pmatrix} 0 & I \\ c^2 \Delta & 0 \end{pmatrix}$，Hermitian。

量子模拟：直接 Trotter 分解，复杂度 $O(\text{poly}(n) \cdot T)$。

Poisson 方程（椭圆型）

$\Delta u = f$

转化为线性方程组：$\mathbf{A}\mathbf{u} = \mathbf{f}$（$\mathbf{A}$ 为离散 Laplacian）。

量子求解：用 QSVT 实现 $\mathbf{A}^{-1}$ 的块编码。

复杂度：$O(\kappa \cdot \text{poly}(n) \cdot \log(1/\varepsilon))$（$\kappa$ 为条件数）。

对流方程（一阶双曲型）

$\partial_t u + c \partial_x u = 0$

离散化：$A = -cD_x$（$D_x$ 为微分矩阵），$A$ 是反 Hermitian（对周期边界）。

量子模拟：$e^{i c D_x t}$ 是酉操作，可直接 Trotter 实现。

复杂度：$O(\text{poly}(n) \cdot T)$。

Navier-Stokes 方程

$\partial_t \mathbf{u} + (\mathbf{u} \cdot \nabla)\mathbf{u} = -\nabla p + \nu \Delta \mathbf{u} + \mathbf{f}$

困难：非线性对流项 $(\mathbf{u} \cdot \nabla)\mathbf{u}$，压力-速度耦合。

量子方法：

1. Carleman 线性化 + Schrödingerization
2. 迭代线性化（每步求解线性 PDE，经典更新非线性项）
3. Lattice Boltzmann 量子化（将流体动力学映射为格点玻尔兹曼方程）

复杂度：对 Carleman 化，$O(\text{poly}(n, K) \cdot T)$（$K$ 为截断阶数）。

复杂度演进总结

与经典方法的对比

指数加速场景（量子优势明确）：

• 高维 PDE（$d \ge 3$）：$n = d\log N$ 量子比特 vs. $N^d$ 经典存储
• 长时间模拟：量子方法复杂度 $O(\text{poly}(n) T)$ vs. 经典 $O(N^d T/\varepsilon)$
• 多查询场景：需要对同一 PDE 的多个初始条件求解

量子优势不明确：

• 低维 PDE（$d = 1, 2$）：经典方法已经高效
• 强非线性 PDE：Carleman 爆炸可能抵消量子加速
• 输出问题：完整读出 $u(\mathbf{x}, T)$ 需要 $O(N^d)$ 次测量

开放问题

1. 非线性 PDE 的最优量子算法：Carleman 方法的截断阶数和条件数控制仍是开放问题

2. 守恒律 PDE：激波和间断解的量子处理方法尚不明确

3. 多尺度 PDE：含快慢尺度的 PDE（如大气模型）需要自适应量子网格

4. 输出效率：如何高效提取 PDE 解的宏观物理量（如平均速度、最大涡量）

5. 实际验证：目前量子 PDE 求解的实验验证仅限于 $O(10)$ 量子比特的小规模问题

总结

量子 PDE 求解的复杂度从 2017 年的 $O(n^4 T^2/\varepsilon)$ 演进到 2024 年的 $O(\text{poly}(n) T)$，Schrödingerization 框架的引入是最重要的突破——它打破了”只能模拟 Hermitian 系统”的限制，为任意线性 PDE 提供了统一的量子求解方案。非线性 PDE 的 Carleman 线性化方法也在 2023 年取得了实质性改进。量子 PDE 求解的最终实用化取决于输出效率的改善和非线性问题复杂度的进一步降低。

参考文献：

1. Berry, D. W. (2017). High-order quantum algorithm for solving linear differential equations. Journal of Physics A, 47, 105301.
2. Jin, S., Liu, N., & Yu, Y. (2022). Quantum simulation of partial differential equations via Schrödingerization. arXiv:2212.13969.
3. An, D., Liu, J., & Lin, L. (2023). Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost. Physical Review Letters, 131, 150601.
4. Costa, P. C. S., Jordan, S. P., & Ostrander, A. (2023). Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7, 913.