Optimal Linear Combination of Hamiltonian Simulation for Dissipative Dynamics

Abstract

Linear combination of Hamiltonian simulation (LCHS) is an efficient method for simulating dissipative dynamics on quantum computers. The choice of the LCHS kernel controls the cost of the algorithm. We prove that the kernel family proposed by Ni and Ying~\cite{NY26} minimizes the LCHS query cost in the minimax sense. For target accuracy $ε$, the minimum cost is asymptotically $\frac{2\mathrm{e}}π(\ln\frac1ε-\ln\ln\frac1ε+o(1))$, with optimal leading constant $\frac{2\mathrm{e}}π$. Our lower-bound proof combines weak duality with a realization lemma that approximates extremal dual functions by matrix elements of dissipative evolutions.

Linear combination of Hamiltonian simulation (LCHS) approximates dissipative evolution $e^{-(X+iY)}$, with $X\succeq0$ and $Y=Y^*$, by integrating unitaries $e^{-i(kX+Y)}$ against a complex measure. This paper determines the optimal trade-off between the support window $[-R,R]$, total-variation budget $\lambda$, and worst-case operator-norm error, establishing minimax optimality of the previously proposed Ni–Ying kernels. Writing $p=(2/\pi)\arctan R$ and $q=1-p$, the minimum error is exactly $1-\lambda$ for $0\le\lambda\le p$, and $q(p/\lambda)^{p/q}$ for $\lambda\ge p$. Optimizing the cost proxy $\lambda R$ at target error $\epsilon$ gives $J(\epsilon)=(2e/\pi)[\ln(1/\epsilon)-\ln\ln(1/\epsilon)]+o(1)$. These results allow arbitrary finite complex measures and hold for both time-independent and time-dependent generators; for the latter, dimension two already suffices for the lower bound. The lower bound uses weak duality and harmonic measure to construct extremal bounded analytic functions. A realization lemma approximates these functions by matrix elements of dissipative evolutions, using bounded polynomial approximation, generalized quantum signal processing, and an autonomous clock followed by discretization. Matching upper bounds follow from existing kernel and local Wiener-norm estimates. The minimax model imposes no bounds on matrix dimension or generator norms, and the realization construction may require both to grow as its approximation error decreases. The result bounds this LCHS cost model, not arbitrary simulation algorithms. Improvements remain possible for restricted matrix classes, including small dimensions or controlled commutators $[X,Y]$.