Advances in optimal Hamiltonian simulation

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, 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 this encoding into unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian and recent 'quantum signal processing' and 'Qubitization' techniques, specializing these results allow us better simulate time-evolution by sparse Hamiltonian. Up to logarithmic factors, this is a polynomial improvement upon prior art.