  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^{-i\hat{H}t}$ with error $\epsilon$, 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
\emph{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\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/\epsilon)}\right)$
queries, where $\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}$. Up to
logarithmic factors, this is a polynomial improvement upon prior art using
$\mathcal{O}\left(td\|\hat
H\|_{\text{max}}+\frac{\log{(1/\epsilon)}}{\log\log{(1/\epsilon)}}\right)$ or
$\mathcal{O}(t^{3/2}(d \|\hat H\|_{\text{max}}\|\hat H\|_{1}\|\hat
H\|/\epsilon)^{1/2})$ queries. In the process, we also prove a matching lower
bound of $\Omega(t(d\|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2})$ queries,
present a distortion-free generalization of spectral gap amplification, and an
amplitude amplification algorithm that performs multiplication on unknown state
amplitudes.
