Guang Hao Low , Isaac L. Chuang
DOI:arXiv:1707.05391v1
Abstract:
The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian Hˆ , and the quantum circuit Uˆ that encodes its description. In the quest to better approximate time-evolution e −iHt ˆ 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 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 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 O t(dkHˆ kmaxkHˆ k1) 1/2 log (tkHˆ k/) queries, where kHˆ k ≤ kHˆ k1 ≤ dkHˆ kmax. Up to logarithmic factors, this is a polynomial improvement upon prior art using O tdkHˆ kmax + log (1/) log log (1/) or O(t 3/2 (dkHˆ kmaxkHˆ k1kHˆ k/) 1/2 ) queries. In the process, we also prove a matching lower bound of Ω(t(dkHˆ kmaxkHˆ k1) 1/2 ) queries, present a distortion-free generalization of spectral gap amplification, and an amplitude amplification algorithm that performs multiplication on unknown state amplitudes.