Qubit-Efficient Quantum Algorithm for Linear Differential Equations
Di Fang and David Lloyd George and Yu Tong
随着量子硬件迅速迈向早期容错时代,一个关键的挑战是开发量子算法,这些算法不仅在理论上是健全的,而且在近期设备上对硬件友好。 在这项工作中,我们提出了一个量子算法,用于求解线性普通微分方程(ODEs),具有可证明的运行时保证。 我们的算法只使用单个 ancilla qubit,并且是局部性保存,即当 ODE 的系数矩阵为 k-local 时,该算法只需要实现 (k+1)-local Hamiltonians 的时间演进。 我们还讨论了我们提议的算法和Lindbladian模拟之间的联系,以及它与相互作用的Hatano-Nelson模型的应用,这是一个被广泛研究的非Hermitian模型,具有丰富的现象学。
As quantum hardware rapidly advances toward the early fault-tolerant era, a key challenge is to develop quantum algorithms that are not only theoretically sound but also hardware-friendly on near-term devices. In this work, we propose a quantum algorithm for solving linear ordinary differential equations (ODEs) with a provable runtime guarantee. Our algorithm uses only a single ancilla qubit, and is locality preserving, i.e., when the coefficient matrix of the ODE is k-local, the algorithm only ...