The fast multipole method on a quantum computer

The fast multipole method (FMM) is a classical algorithm for approximating pairwise interactions between n particles in O(n) time, improving on the O(n^2) complexity required by direct computation. The ability to implement FMM on a quantum computer with O(n) gate complexity would lead to asymptotically faster algorithms for quantum chemistry. However, translating classical algorithms to quantum circuits without incurring polynomial overhead is not in general straightforward. In this talk, I will show how FMM can nevertheless be adapted to a quantum computer using O(n) gates, by exploiting the underlying structure of the algorithm.