Hamiltonian Simulation by Uniform Spectral Amplification

The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian Ĥ, and the quantum circuit Û that encodes its description. In the quest to better approximate time-evolution e-iĤt with error $ε$, we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits Û for generalized measurement. This allows us to define a uniform spectral amplification problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring Û into $n=1,2,3$ unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian, specializing these results allow us simulate time-evolution by d-sparse Hamiltonians using O(t(d \| H\|ₘₐₓ\| H\|₁)1/2log(t\|Ĥ\|/ε)) queries, where \| H\|≤ \| H\|₁≤ d\| H\|ₘₐₓ. Up to logarithmic factors, this is a polynomial improvement upon prior art using O(td\| H\|ₘₐₓ+log(1/ε)loglog(1/ε)) or O(t3/2(d \| H\|ₘₐₓ\| H\|₁\| H\|/ε)1/2) queries. In the process, we also prove a matching lower bound of Ω(t(d\| H\|ₘₐₓ\| H\|₁)1/2) queries, present a distortion-free generalization of spectral gap amplification, and an amplitude amplification algorithm that performs multiplication on unknown state amplitudes.