论文标题
基于时间构造的量子求解器，用于时间依赖性线性微分方程
Time-marching based quantum solvers for time-dependent linear differential equations
论文作者
论文摘要
时间到底策略从一个时间步骤到下一个时间步骤传播解决方案，是解决经典计算机上时间依赖的微分方程以及解决量子计算机上的Hamiltonian模拟问题的自然策略。对于更通用的线性微分方程，基于时间级的量子求解器可能会遭受成倍消失的时间步骤数量的成功概率，因此被认为是不切实际的。我们通过反复调用一种称为统一奇异值放大的技术来解决这个问题，并且可以通过与时间步长的数量无关的数量来降低整体成功概率。使用压缩小工具引理可以进一步提高成功概率。这提供了设计量子微分方程求解器的途径，该方程式求解器替代基于量子线性系统算法（QLSA）的途径。我们根据截断的戴森系列使用高阶集成器来证明时间级策略的性能。该算法的复杂性在线性上取决于放大比，这量化了与单一动力学的偏差。我们证明，对扩增比的线性依赖性达到了查询复杂性下限，因此在最坏情况下无法改善。该算法在三个方面还超过了现有的基于QLSA的求解器：（1）系数矩阵$ a（t）$不需要对角线。 （2）$ a（t）$可以是不平滑的，并且仅具有有限的变化。 （3）它可以对初始状态使用更少的查询。最后，我们通过一阶截短的马格努斯系列展示了时间制度的策略，同时保留了上述收益。我们的分析还提出了一些有关基于时间衡量和基于QLSA的方法来求解微分方程之间的差异的开放问题。
The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general linear differential equations, a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps and is thus considered impractical. We solve this problem by repeatedly invoking a technique called the uniform singular value amplification, and the overall success probability can be lower bounded by a quantity that is independent of the number of time steps. The success probability can be further improved using a compression gadget lemma. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms (QLSA). We demonstrate the performance of the time-marching strategy with a high-order integrator based on the truncated Dyson series. The complexity of the algorithm depends linearly on the amplification ratio, which quantifies the deviation from a unitary dynamics. We prove that the linear dependence on the amplification ratio attains the query complexity lower bound and thus cannot be improved in the worst case. This algorithm also surpasses existing QLSA based solvers in three aspects: (1) the coefficient matrix $A(t)$ does not need to be diagonalizable. (2) $A(t)$ can be non-smooth, and is only of bounded variation. (3) It can use fewer queries to the initial state. Finally, we demonstrate the time-marching strategy with a first-order truncated Magnus series, while retaining the aforementioned benefits. Our analysis also raises some open questions concerning the differences between time-marching and QLSA based methods for solving differential equations.
