2017/07/17 by Guang Hao Low, Isaac L. Chuang, Low, Guang Hao +1 · 22 citations
Computer Science · Engineering · #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata #Low-power high-performance VLSI design
paper · pdf · doi:10.48550/arxiv.1707.05391
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(d ‖ H‖max‖ H‖1)1/2log(t‖H‖/ε)) queries, where ‖ H‖≤ ‖ H‖1≤ d‖ H‖max. Up to logarithmic factors, this is a polynomial improvement upon prior art using O(td‖ H‖max+\fraclog(1/ε)loglog(1/ε)) or O(t3/2(d ‖ H‖max‖ H‖1‖ H‖/ε)1/2) queries. In the process, we also prove a matching lower bound of Ω(t(d‖ H‖max‖ 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.