Quantum differential equation solvers: limitations and fast-forwarding

D. An, J.-P. Liu, D. Wang, Q. Zhao · 2025 · Commun. Math. Phys.（DOI 10.1007/s00220-025-05358-7；arXiv 2022）

| 编号 QC031 | 主题 量子 PDE 求解 | 链接 arXiv:2211.05246 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

We study the limitations and fast-forwarding of quantum algorithms for linear ordinary differential equation (ODE) systems with a particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational overheads due to two types of “non-quantumness”: real part gap and non-normality of the coefficient matrix. We then show that homogeneous ODEs in the absence of both types of “non-quantumness” are equivalent to quantum dynamics, and reach the conclusion that quantum algorithms for quantum dynamics work best. To obtain these lower bounds, we propose a general framework for proving lower bounds on quantum algorithms that are amplifiers, meaning that they amplify the difference between a pair of input quantum states. On the other hand, we show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency. More specifically, we obtain exponential improvements in both T and the spectral norm of the coefficient matrix for inhomogeneous ODEs with efficiently implementable eigensystems, including various spatially discretized linear evolutionary partial differential equations. We give fast-forwarding algorithms that are conceptually different from existing ones in the sense that they neither require time discretization nor solving high-dimensional linear systems.

本站词条在引用该文献时，会以 wikilink（sources/QC031）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。