2026/07/22 by Alexander Zlokapa, Richard R. Allen, Aram W. Harrow
#quant-ph
For Hamiltonian H = ∑j hj, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms ‖hj‖, time t, and trace-distance error ε. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case ‖hj‖ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in 1/ε, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.