Optimal quantum simulation of linear non-unitary dynamics

Abstract

We present a quantum algorithm for simulating the time evolution generated by any bounded, time-dependent operator $-A$ with non-positive logarithmic norm, thereby serving as a natural generalization of the Hamiltonian simulation problem. Our method generalizes the recent Linear-Combination-of-Hamiltonian-Simulation (LCHS) framework. In instances where $A$ is time-independent, we provide a block-encoding of the evolution operator $e^{-At}$ with $\mathcal{O}(t\log \frac{1}{ϵ})$ queries to the block-encoding oracle for $A$. We also show how the normalized evolved state can be prepared with $\mathcal{O}(1/\Vert e^{-At}|{\vec{u}}_0⟩\Vert )$ queries to the oracle that prepares the normalized initial state $|{\vec{u}}_0⟩$. These complexities are optimal in all parameters and improve the error scaling over prior results. Furthermore, we show that any improvement of our approach exceeding a constant factor of approximately 3 is infeasible. For general time-dependent operators $A$, we also prove that a uniform trapezoidal rule on our LCHS construction yields exponential convergence, leading to simplified quantum circuits with improved gate complexity compared to prior nonuniform-quadrature methods.