Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation

Abstract

The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$q=O\left(\alpha T+\frac{\log (1/\epsilon )}{\log \left(e+\log (1/\epsilon )/(\alpha T)\right)}\right)$$ queries to $\mathrm{HAM\mbox{-}T}$ within $\epsilon$ error for a Lipschitz-continuous time-dependent Hamiltonian $H(t)$ on $[0,T]$ satisfying $\Vert H(t)\Vert \le \alpha$. However, its direct circuit implementation incurs a substantially larger gate overhead. In this note, we give an implementation of the same algorithm that retains its optimal query complexity and uses $$O\left[q\left(a+\log \left(1+\frac{T(\alpha +\beta T)}{\epsilon }\right)\right)\right]$$ one- and two-qubit gates, where $a$ is the number of block-encoding ancilla qubits and $\beta$ is the Lipschitz constant of $H$. The main ingredient is an exact dyadic factorization of the ordered update product in the underlying one-query transducer.

23 pages, 1 figure