Speaker
Description
In quantum algorithms for simulation of quantum systems, a leading method is to use a product formula approach. The Hamiltonian is written as $H=T+V$, where the kinetic energy $T$ and potential energy $V$ are each calculated. Whereas $T$ can be calculated with complexity $n$ for a system with $n$ charges, calculating $V$ has complexity $n^2$ and is therefore a bottleneck. This complexity is from summing the pairwise potentials between all charges, but in classical computing the fast multipole method (FMM) enables complexity scaling linearly in $n$.
FMM uses a sequence of boxes at finer and finer grids. Level 1 is the complete volume, level 2 divides that volume into $2\times 2\times 2$ boxes, level 3 further subdivides each of those boxes, and so forth. Each box requires multipole information to be computed from the charges in the box, as well as boxes in its interaction list. In a quantum algorithm, which charges are in each box is governed by values in quantum registers, which would cause an extra factor of n for data access in the complexity for a naïve application of the classical algorithm. That factor would negate the speedup otherwise enabled by FMM.
Here, we solve that problem by using an approach using quantum sorting. Sorting in quantum computers uses sorting networks with memory accesses in a fixed sequence to eliminate the overhead from memory accesses. We perform a recursive procedure using sorts in each of the three directions to move registers for the charges into the appropriate boxes. To enable an adaptive grid, for each charge we add registers for multipole information for its box and neighbouring boxes. In this way we overcome the data access problem and provide an algorithm nearly linear in $n$.
