Elliot Eklund

Here we describe an approach for simulating quantum chemistry on quantum computers with significantly lower asymptotic complexity than prior work. The approach uses a real-space first-quantised representation of the molecular Hamiltonian which we propagate using high-order product formulae. Essential for this low complexity is the use of a technique similar to the fast multipole method for computing the Coulomb operator with O(eta) complexity for a simulation with eta particles. We show how to modify this algorithm so that it can be implemented on a quantum computer. We ultimately demonstrate an approach with t(eta^{4/3} N^{1/3} + eta^{1/3} N^{2/3})(eta Nt/epsilon)^o(1) gate complexity, where N is the number of grid points, epsilon is target precision, and t is the duration of time evolution. This is roughly a speedup by O(eta) over most prior algorithms. We provide lower complexity than all prior work for N<eta^7 (the regime of practical interest), with only first-quantised interaction-picture simulations providing better performance for N>eta^7. As with the classical fast multipole method, large numbers eta>10^3 would be needed to realise this advantage.