Recorded 03 October 2023. Kianna Wan of Stanford University presents "Fast multipole method on a quantum computer" at IPAM's Quantum Algorithms for Scientific Computation Workshop. Abstract: 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. Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-i-quantum-algorithms-for-scientific-computation/?tab=schedule