Time-Dependent Hamiltonian Simulation with Optimal Query Complexity

Abstract

We give a query-optimal algorithm for simulating a general $n$-qubit time-dependent Hamiltonian $H(t)$ on $[0,T]$, assuming that $H$ is Lipschitz continuous and $\Vert H(t)\Vert \le \alpha$. In the standard $\mathrm{HAM\mbox{-}T}$ access model, the algorithm approximates the time-ordered propagator $U_H(T)$ to error $\epsilon$ using $$O\left(\alpha T+\frac{\log (1/\epsilon )}{\log (e+\log (1/\epsilon )/(\alpha T))}\right)$$ $\mathrm{HAM\mbox{-}T}$ queries. This matches the known query lower bound for time-independent Hamiltonians, showing that time dependence incurs no asymptotic query overhead. Our method first constructs a one-query transducer that, given an auxiliary state, implements an approximation to $U_H(T)$ and returns the state unchanged. A weighted combination of circuits that apply the transducer different numbers of times makes the error caused by omitting this state decay factorially, yielding the stated optimal precision dependence. For time-independent Hamiltonians, the same method also gives a query-optimal alternative to qubitization.

35 pages, 1 figure, 1 table