Query-Optimal and Gate-Efficient Time-Dependent Hamiltonian Simulation

Xinzhao Wang presents a query-optimal algorithm for simulating a general Lipschitz-continuous time-dependent Hamiltonian. Its query complexity matches the known lower bound for time-independent Hamiltonian simulation, showing that time dependence incurs no asymptotic query overhead. The main ingredient is a one-query transducer that implements the target evolution given a catalyst state. A weighted combination of circuits that reuse the transducer different numbers of times removes the need to prepare the catalyst; the error from omitting the catalyst decays factorially, which yields the optimal dependence on precision. The same algorithm also admits a gate-efficient implementation that retains the optimal query complexity, with gate complexity linear in the query complexity up to logarithmic factors.