Abstract
We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.
Introduction
Quantum computers are naturally suited for simulating unitary evolution governed by the Schrödinger equation. However, many critical problems in fluid dynamics, chemical kinetics, and finance are described by linear ordinary differential equations (ODEs) that are non-unitary. Solving these general linear ODEs on quantum hardware requires preparing a state $|u(T)\rangle$ proportional to the solution of: $$\frac{du(t)}{dt} = -A(t)u(t) + b(t)$$ where $A(t)$ is a large matrix and $b(t)$ is an inhomogeneous term.
Historically, quantum algorithms for this task have faced a trade-off. Linear system solvers (HHL-style) offer high precision but suffer from high state preparation costs. Conversely, the original Linear Combination of Hamiltonian Simulation (LCHS) method provides optimal state preparation costs but exhibits poor polynomial scaling with respect to precision ($1/\epsilon$). This work bridges that gap, achieving near-optimal complexity across all parameters.
Methodology: Generalized LCHS
The authors propose a generalized mathematical framework that expresses non-unitary evolution as a weighted sum of unitary Hamiltonian simulations. The evolution operator is represented by the integral identity: $$\mathcal{T} e^{-\int_0^t A(s) ds} = \int_{\mathbb{R}} \frac{f(k)}{1-ik} \mathcal{T} e^{-i \int_0^t (kL(s) + H(s)) ds} dk$$ where $A = L + iH$. This formulation allows the non-unitary problem to be decomposed into a Linear Combination of Unitaries (LCU), where each term is a standard Hamiltonian simulation.
The key breakthrough lies in the choice of the "kernel function" $f(z)$. By replacing the slowly decaying Cauchy kernel of the original LCHS with a family of kernels exhibiting near-exponential decay ($e^{-|k|^\beta}$), the authors can truncate the integral at a significantly smaller range. This mathematical refinement transforms the precision scaling from polynomial to poly-logarithmic ($\text{poly}(\log 1/\epsilon)$). The algorithm is implemented using composite Gaussian quadrature for discretization and advanced techniques like the truncated Dyson series or Quantum Signal Processing (QSP) for the unitary simulations.
Results and Complexity Comparison
The improved LCHS method achieves near-optimal scaling in matrix queries and optimal state preparation costs. For time-independent matrices, the complexity scales additively between the matrix norm and precision ($\|A\|T + \log(1/\epsilon)$), which is a hallmark of optimal quantum algorithms.
As illustrated in the table above, the improved LCHS method provides an exponential boost in precision compared to its predecessor. While the original LCHS required $O(1/\epsilon)$ queries to $A(t)$, the new approach requires only $O(\text{poly}(\log 1/\epsilon))$. Furthermore, the cost to prepare the initial state $|u_0\rangle$ is $O(\|u_0\|/\|u(T)\|)$, matching the theoretical lower bound. Numerical simulations on small-scale systems have validated these theoretical improvements, demonstrating the superior truncation error of the new kernel functions.
Discussion and Future Work
The proposed algorithm assumes that the real part of the matrix $A(t)$ is positive semi-definite ($L(t) \succeq 0$), ensuring the stability of the physical system. While this covers many practical applications, extending the method to all stable ODEs remains an area for future research. Additionally, while additive scaling was achieved for time-independent matrices, achieving similar results for time-dependent systems is an ongoing challenge in quantum simulation. The framework also suggests potential for hybrid quantum-classical implementations, which may be particularly relevant for early fault-tolerant quantum devices.
Summary updated