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 hat{H}, and the quantum circuit hat{U} that encodes its description. In the quest to better approximate time-evolution e^{-ihat{H}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 hat{U} 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 hat{U} 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 mathcal{O}left\(t(d \|hat H\|_max\|hat H\|₁\)^1/2log{\(t\|hat{H}\|/ε\)}right) queries, where \|hat H\|le \|hat H\|_1le d\|hat H\|_max. Up to logarithmic factors, this is a polynomial improvement upon prior art using mathcal{O}left\(td\|hat H\|_max+frac{log{(1/ε\)}}{loglog{(1/ε)}}right) or mathcal{O}\(t^3/2(d \|hat H\|_max\|hat H\|₁\|hat H\|/ε\)^1/2) queries. In the process, we also prove a matching lower bound of Ω\(t(d\|hat H\|_max\|hat 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.