Hamiltonian simulation via quantum walks - Dominic Berry

Hamiltonian simulation can be used to simulate physical systems, and is also the basis for many new quantum algorithms. I present methods to simulate black-box Hamiltonians with fixed error using a number of queries that scales as O(||H||tD), where D is the maximum number of nonzero elements in any column, t is the evolution time and ||H|| is the spectral norm of the Hamiltonian. In contrast, previous methods had complexity scaling as D^4, and slightly superlinear scaling in ||H||t. Alternatively, for D>||H||t the scaling can be improved to approximately O([||H||t]^{4/3}D^{2/3}). Numerical testing indicates that in almost all cases the scaling can be further improved to approximately O([||H||t]^{3/2}D^{1/2}). One application of this is to implementation of black-box unitaries with O(N^{1/2}) queries. In contrast, standard methods take at least N^2 elementary gates. This could be used to more efficiently implement unitaries in cases where the matrix elements can be efficiently calculated.