pith. sign in

arxiv: 2510.07380 · v2 · submitted 2025-10-08 · 🪐 quant-ph

Quantum simulation of electronic structure via quantum fast multipole method

Dominic W. Berry , Kianna Wan , Andrew D. Baczewski , Elliot C. Eklund , Arkin Tikku , Ryan Babbush This is my paper

Pith reviewed 2026-05-18 09:18 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum simulationelectronic structurefast multipole methodCoulomb operatorfirst-quantized representationgate complexitymolecular Hamiltonianquantum algorithms
0
0 comments X

The pith

Electronic structure can be simulated on quantum computers with an O(η) reduction in gate complexity using a quantum fast multipole method.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a new approach for quantum simulation of molecular electronic structure by representing electrons in real space on a grid and evolving their wavefunction with product formulas. Central to the efficiency is adapting the classical fast multipole method to quantum computers to compute the long-range Coulomb interactions between η electrons with near-linear cost. This yields an overall gate complexity of roughly t times (η to the four-thirds times N to the one-third plus η to the one-third times N to the two-thirds) with only polylog overheads. A sympathetic reader would care because this improves on most earlier quantum algorithms by a factor proportional to the number of electrons and beats all previous methods in the regime where the grid size N is smaller than η to the seventh, which covers most molecules of practical interest.

Core claim

We describe an approach for simulating electronic structure 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~(η) complexity for a simulation with η 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(η^{4/3}N^{1/3} + η^{1/3} N^{2/3} ) (η Nt/ε)^{o(1)} gate complexity. This is roughly a

What carries the argument

Quantum fast multipole method that approximates the Coulomb operator with near-linear complexity in the number of particles η.

If this is right

  • Provides lower complexity than all previous quantum algorithms for electronic structure when N < η^7.
  • Only first-quantized interaction-picture simulations offer better performance when N > η^7.
  • Requires η around 1000 or larger to realize the advantage over classical methods.
  • Maintains the improvement with only polylogarithmic factors in precision and simulation time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the polylog overheads remain small in practice, this could enable simulation of larger molecules on future quantum hardware than previously thought possible.
  • Analogous techniques might reduce complexity in quantum simulations of other many-body systems with 1/r potentials.
  • Further gains could come from integrating this method with basis set improvements or variational algorithms.
  • Hardware experiments on small systems could test if the theoretical scaling translates to actual runtime reductions.

Load-bearing premise

The quantum implementation of the fast-multipole Coulomb operator can be realized with only the stated polylog overhead and without hidden polynomial factors in η or N that would erase the claimed advantage in the N < η^7 regime.

What would settle it

A concrete gate-count comparison or small-system circuit implementation that measures whether total gates remain below prior methods by the claimed O(η) factor when N is set near η^4.

Figures

Figures reproduced from arXiv: 2510.07380 by Andrew D. Baczewski, Arkin Tikku, Dominic W. Berry, Elliot C. Eklund, Kianna Wan, Ryan Babbush.

Figure 1
Figure 1. Figure 1: FIG. 1. Illustration of hierarchical division of a simulation cell, as well as the interaction list and neighbours for an exemplary [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. 1D demonstration of Algorithm 2. Here [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. The interaction list and neighbours used for FMM. The green square is the box [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
read the original abstract

Here we describe an approach for simulating electronic structure 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 $\widetilde{\cal 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 ${\cal 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 particle numbers $\eta\gtrsim 10^3$ would be needed to realise this advantage.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript describes a quantum algorithm for electronic structure simulation in a first-quantized real-space grid representation of the molecular Hamiltonian. Time evolution is performed with high-order product formulas, and the Coulomb operator is evaluated via a quantum adaptation of the classical fast multipole method (FMM) that achieves ~O(η) cost per application for η electrons. The resulting gate complexity is stated as t(η^{4/3}N^{1/3} + η^{1/3}N^{2/3})(η Nt/ε)^{o(1)}, claimed to be asymptotically superior to prior algorithms for N < η^7 (the regime of practical interest) while requiring η ≳ 10^3 to realize the advantage.

Significance. If the quantum FMM construction can be realized with only polylog overhead and without hidden polynomial factors in η or N, the result would constitute a meaningful asymptotic improvement over existing first-quantized product-formula approaches for quantum chemistry simulation. The adaptation of hierarchical multipole-to-local translations to coherent quantum oracles is a plausible route to sub-quadratic Coulomb evaluation, and the explicit regime comparison (N < η^7) provides a concrete, falsifiable claim. No machine-checked proofs or reproducible code are mentioned, but the parameter-free scaling derivation (if fully detailed) would be a strength.

major comments (2)
  1. [Abstract / complexity statement] Abstract and complexity claim: the headline bound t(η^{4/3}N^{1/3} + η^{1/3}N^{2/3})(η Nt/ε)^{o(1)} rests on the quantum FMM replacing the η² Coulomb sum with per-particle cost scaling as η^{1/3}N^{2/3} plus polylog factors. No explicit gate decomposition, oracle cost model, or error analysis is supplied for the coherent multipole-to-local translation operators. If these unitaries scale with expansion order p or particles per box rather than remaining polylog(p, η, N), the total complexity acquires extra η^α or N^β factors that erase the claimed O(η) advantage precisely in the N < η^7 window.
  2. [Quantum FMM construction] The manuscript states that the classical FMM is modified for quantum implementation but provides no circuit diagram, query complexity for the translation oracles, or rigorous bound on the number of expansion terms p needed to achieve target precision ε. This analysis is load-bearing for the central claim that the algorithm is cheaper than all prior work for N < η^7.
minor comments (2)
  1. [Abstract] The notation ~O(η) for the Coulomb operator and the precise meaning of the o(1) exponent in the final bound should be defined explicitly in the main text.
  2. [Notation] Clarify whether the grid size N is the total number of points or per dimension, and state the assumed relation between N and the simulation volume.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the need for more explicit details on the quantum fast multipole method construction. We address each major comment below and have incorporated additional analysis and figures into the revised version to strengthen the presentation of the complexity bounds.

read point-by-point responses

  1. Referee: [Abstract / complexity statement] Abstract and complexity claim: the headline bound t(η^{4/3}N^{1/3} + η^{1/3}N^{2/3})(η Nt/ε)^{o(1)} rests on the quantum FMM replacing the η² Coulomb sum with per-particle cost scaling as η^{1/3}N^{2/3} plus polylog factors. No explicit gate decomposition, oracle cost model, or error analysis is supplied for the coherent multipole-to-local translation operators. If these unitaries scale with expansion order p or particles per box rather than remaining polylog(p, η, N), the total complexity acquires extra η^α or N^β factors that erase the claimed O(η) advantage precisely in the N < η^7 window.

    Authors: We agree that the headline complexity relies on the quantum FMM achieving the stated scaling with only polylog overhead. The original manuscript derives the per-particle cost from the classical FMM hierarchy (with O(η^{1/3}N^{2/3}) work per application after hierarchical translations) and assumes standard quantum techniques (e.g., block-encoding of translation operators) keep the overhead polylogarithmic. To address the concern directly, the revised manuscript adds an appendix with the explicit oracle cost model, showing that multipole-to-local translations are implemented via a quantum walk on the hierarchical tree with query complexity polylog(p, η, N) and that p = O(log(1/ε)) suffices for target precision. This analysis confirms no hidden polynomial factors arise in the N < η^7 regime, preserving the claimed O(η) improvement over prior first-quantized product-formula algorithms. revision: yes

  2. Referee: [Quantum FMM construction] The manuscript states that the classical FMM is modified for quantum implementation but provides no circuit diagram, query complexity for the translation oracles, or rigorous bound on the number of expansion terms p needed to achieve target precision ε. This analysis is load-bearing for the central claim that the algorithm is cheaper than all prior work for N < η^7.

    Authors: We acknowledge that the main text presented the quantum FMM at a high level without circuit diagrams or full query-complexity derivations. The revised manuscript now includes a dedicated subsection with a circuit diagram for the coherent multipole-to-local translation operator (implemented via controlled rotations on the expansion coefficients and a quantum Fourier transform over the hierarchical boxes) together with a rigorous bound: the number of expansion terms satisfies p = Θ(log(N/ε)) to keep truncation error below ε, and the total oracle queries per FMM application remain O(η^{1/3}N^{2/3} polylog(η N / ε)). These additions make the load-bearing analysis explicit and support the regime comparison N < η^7. revision: yes

Circularity Check

0 steps flagged

No circularity; complexity bound derived from explicit algorithmic cost analysis

full rationale

The paper constructs a quantum algorithm for first-quantized electronic structure simulation by combining high-order product formulae with a modified quantum fast multipole method for the Coulomb interaction. The stated gate complexity t(η^{4/3}N^{1/3} + η^{1/3}N^{2/3})(η Nt/ε)^{o(1)} is obtained by summing the per-step costs of the product formula (O(η) terms) with the per-particle cost of the quantum FMM (O(η^{1/3}N^{2/3}) plus polylog factors). No equation or claim reduces the final bound to a fitted parameter, a self-referential definition, or a load-bearing self-citation whose validity is assumed rather than independently derived. The derivation remains self-contained against standard quantum simulation primitives and classical FMM analysis; potential hidden polynomial costs in translation oracles are a question of implementation correctness, not a circular reduction of the claimed result to its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard quantum circuit model assumptions, the existence of high-order product formulas for time evolution, and the classical fast multipole method being adaptable to unitary operators on a quantum computer; no new physical entities or fitted constants are introduced.

axioms (2)
  • standard math High-order product formulas can be used to approximate time evolution of the molecular Hamiltonian to precision ε with cost polynomial in 1/ε.
    Invoked to propagate the first-quantized Hamiltonian; standard in quantum simulation literature.
  • domain assumption The Coulomb operator can be approximated via a hierarchical multipole expansion whose quantum implementation incurs only polylog overhead.
    Central to achieving the stated linear-in-η scaling; location is the description of the quantum FMM modification.

pith-pipeline@v0.9.0 · 5793 in / 1527 out tokens · 30721 ms · 2026-05-18T09:18:47.160980+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Fault-tolerant simulation of the electronic structure using Projector Augmented-Waves and Bloch orbitals

    quant-ph 2026-04 unverdicted novelty 6.0

    Bloch-UPAW integrates Bloch orbitals and local UPAW corrections to enable lower-resource fault-tolerant quantum simulations of solids, showing roughly 10x Toffoli reduction for bulk diamond.

Reference graph

Works this paper leans on

66 extracted references · 66 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    We run through the electrons in sequence, and for each we check if the following electron corresponds to a new region; that isf b(j, ℓ)̸=f b(j+ 1, ℓ)

    Accessing interaction list for 1D case For each electron, we have extra registers for one, two, and three positions over; we will call theseQ 1(j, ℓ),Q 2(j, ℓ), andQ 3(j, ℓ). We run through the electrons in sequence, and for each we check if the following electron corresponds to a new region; that isf b(j, ℓ)̸=f b(j+ 1, ℓ). The cases are then as follows

    work page

  2. [2]

    That is,Q k(j+ 1, ℓ) =Q k(j, ℓ) fork∈ {1,2,3}

    Iff b(j, ℓ) =f b(j+ 1, ℓ), then both electrons are in the same region, and we just directly copy over the charge information. That is,Q k(j+ 1, ℓ) =Q k(j, ℓ) fork∈ {1,2,3}

    work page

  3. [3]

    Iff b(j+ 1, ℓ) =f b(j, ℓ) + 1, then the next electron is in the next region, and we copy the charge information to the next electron’s register for the neighbouring region; that is,Q 1(j+ 1, ℓ) =Q(j, ℓ). We also copy the charge information for one location over to that for two locations over, and that for two regions over to that for three regions over, s...

    work page

  4. [4]

    We also copy the information for one region over to that for three regions over, soQ 3(j+ 1, ℓ) =Q 1(j, ℓ)

    Iff b(j+ 1, n) =f b(j, n) + 2, then the next electron is two regions displaced, and we directly copy into the register for two regions over, soQ 2(j+ 1, ℓ) =Q(j, ℓ). We also copy the information for one region over to that for three regions over, soQ 3(j+ 1, ℓ) =Q 1(j, ℓ). We leaveQ 1(j+ 1, ℓ) zeroed, because that region is missing

    work page

  5. [5]

    We leave bothQ 1(j+ 1, ℓ) andQ 2(j+ 1, ℓ) zeroed, because those regions are missing

    Iff b(j+ 1, n) =f b(j, n) + 3, then the next electron is three regions displaced, and we directly copy into the register for three regions over, soQ 3(j+ 1, ℓ) =Q(j, ℓ). We leave bothQ 1(j+ 1, ℓ) andQ 2(j+ 1, ℓ) zeroed, because those regions are missing

    work page

  6. [6]

    After doing this, we have associated with each electron, registers giving the charge information for the boxes to the left of it, which can be used in computing the potential

    Iff b(j+ 1, ℓ)> f b(j, ℓ) + 3, then the next electron is more than three regions displaced, andQ 1(j+ 1, ℓ), Q2(j+ 1, ℓ), andQ 3(j+ 1, ℓ) can be left zeroed. After doing this, we have associated with each electron, registers giving the charge information for the boxes to the left of it, which can be used in computing the potential. We can then invert the ...

    work page

  7. [7]

    To address this issue, we use Morton ordering, as well as bit shifts

    Accessing interaction list for higher dimensions In order to obtain the information from the boxes in the interaction list in two or three dimensions, we can use a similar approach interleaving bits as we use for charge, but it is more challenging because the boxes in the interaction list need to be accessed by taking a 1D path through this higher-dimensi...

    work page

  8. [8]

    The items to be sorted include only the particle positions and the corresponding box charge for levelℓ, and so is of sizeO(logN)

    There areO(logN) sorts to be performed, with each being a sort ofηitems and therefore having complexity O(ηlogη) with optimal sorting networks. The items to be sorted include only the particle positions and the corresponding box charge for levelℓ, and so is of sizeO(logN). Note that we only need the charge information for levelℓ, so do not need to sort th...

    work page

  9. [9]

    This is doneO(logN) times, and each time there areηsteps withO(logη) information to be copied

    We need to use Algorithm 4 to copy the charge information. This is doneO(logN) times, and each time there areηsteps withO(logη) information to be copied. As a result the complexity is the same as in Eq. (24)

    work page

  10. [10]

    There areO(ηlogN) steps where we need to calculate the addition to the potential. There areO(1) boxes in the interaction list, and so Φ(ca,c b) can be determined with a QROM with complexityO(1) Toffolis, orO(log(1/ϵ)) total gates accounting for the precision that the potential is given to. The multiplications byQ k(j, ℓ) andQ(j, ℓ) have complexityO(logηlo...

    work page

  11. [11]

    The number of qubits to store the system state is O(ηlogN).(27) 18

    work page

  12. [12]

    The qubits used for the charge information at all levels is O(ηlogηlogN).(28) This is because there areO(logN) levels, and each usesO(logη) qubits for the charge

    work page

  13. [13]

    Foundations for quantum simulation of warm dense matter

    There are temporary qubits used for the coherent sorts. Because these record the results of inequality tests, and there areO(ηlogη) of these tests, the total number of qubits is O(ηlogη).(29) The leading contribution to the logical qubits used isO(ηlogηlogN). More generally, for the multipole expansion, the order needed for precisionϵisO(log(1/ϵ)). The nu...

    work page

  14. [14]

    Y. Su, D. W. Berry, N. Wiebe, N. Rubin, and R. Babbush, Fault-tolerant quantum simulations of chemistry in first quantization, PRX Quantum2, 040332 (2021)

    work page 2021

  15. [15]

    D. W. Berry, N. C. Rubin, A. O. Elnabawy, G. Ahlers, A. E. DePrince III, J. Lee, C. Gogolin, and R. Babbush, Quantum simulation of realistic materials in first quantization using non-local pseudopotentials, npj Quantum Information10, 130 (2024)

    work page 2024

  16. [16]

    Babbush, W

    R. Babbush, W. J. Huggins, D. W. Berry, S. F. Ung, A. Zhao, D. R. Reichman, H. Neven, A. D. Baczewski, and J. Lee, Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods, Nature Communications14, 4058 (2023)

    work page 2023

  17. [17]

    N. C. Rubin, D. W. Berry, A. Kononov, F. D. Malone, T. Khattar, A. White, J. Lee, H. Neven, R. Babbush, and A. D. Baczewski, Quantum computation of stopping power for inertial fusion target design, Proceedings of the National Academy of Sciences121, e2317772121 (2024)

    work page 2024

  18. [18]

    Lloyd, Universal Quantum Simulators, Science273, 1073 (1996)

    S. Lloyd, Universal Quantum Simulators, Science273, 1073 (1996)

    work page 1996

  19. [19]

    Wiebe and A

    N. Wiebe and A. M. Childs, Hamiltonian simulation using linear combinations of unitary operations, Quantum Information and Computation12, 901 (2012)

    work page 2012

  20. [20]

    D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Exponential improvement in precision for simulating sparse Hamiltonians, inProceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’14 (ACM, New York, NY, USA, 2014) pp. 283–292

    work page 2014

  21. [21]

    D. W. Berry and A. M. Childs, Black-box Hamiltonian simulation and unitary implementation, Quantum Information and Computation12, 0029 (2012)

    work page 2012

  22. [22]

    D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Simulating Hamiltonian dynamics with a truncated Taylor series, Phys. Rev. Lett.114, 090502 (2015)

    work page 2015

  23. [23]

    G. H. Low and I. L. Chuang, Optimal Hamiltonian simulation by quantum signal processing, Phys. Rev. Lett.118, 010501 (2017)

    work page 2017

  24. [24]

    G. H. Low and I. L. Chuang, Hamiltonian Simulation by Qubitization, Quantum3, 163 (2019)

    work page 2019

  25. [25]

    A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, Theory of Trotter error with commutator scaling, Phys. Rev. X 11, 011020 (2021)

    work page 2021

  26. [26]

    M. E. S. Morales, P. C. S. Costa, G. Pantaleoni, D. K. Burgarth, Y. R. Sanders, and D. W. Berry, Selection and improvement of product formulae for best performance of quantum simulation, Quantum Information & Computation25, 1 (2025)

    work page 2025

  27. [28]

    Stetina and N

    T. Stetina and N. Wiebe, First-quantized quantum simulation of non-relativistic QED with emergent topologically pro- tected Coulomb interactions, arXiv:2508.19343 (2025)

    work page arXiv 2025

  28. [29]

    Kassal, S

    I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, and A. Aspuru-Guzik, Polynomial-time quantum algorithm for the simulation of chemical dynamics, Proceedings of the National Academy of Sciences105, 18681 (2008)

    work page 2008

  29. [30]

    G. H. Low, Y. Su, Y. Tong, and M. C. Tran, Complexity of implementing Trotter steps, PRX Quantum4, 020323 (2023)

    work page 2023

  30. [31]

    Rokhlin, Rapid solution of integral equations of classical potential theory, Journal of Computational Physics60, 187 (1985)

    V. Rokhlin, Rapid solution of integral equations of classical potential theory, Journal of Computational Physics60, 187 (1985)

    work page 1985

  31. [32]

    Barnes and P

    J. Barnes and P. Hut, A hierarchical O(N log N) force-calculation algorithm, Nature324, 446–449 (1986)

    work page 1986

  32. [33]

    Carrier, L

    J. Carrier, L. Greengard, and V. Rokhlin, A fast adaptive multipole algorithm for particle simulations, SIAM Journal on Scientific and Statistical Computing9, 669 (1988)

    work page 1988

  33. [34]

    A. M. Childs, J. Leng, T. Li, J.-P. Liu, and C. Zhang, Quantum simulation of real-space dynamics, Quantum6, 860 (2022)

    work page 2022

  34. [35]

    Cheng and C.-Y

    S.-T. Cheng and C.-Y. Wang, Quantum switching and quantum merge sorting, IEEE Transactions on Circuits and Systems I: Regular Papers53, 316 (2006)

    work page 2006

  35. [36]

    Beals, S

    R. Beals, S. Brierley, O. Gray, A. W. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather, Efficient distributed quantum computing, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences469, 20120686 21 (2013)

    work page 2013

  36. [37]

    Yesypenko, C

    A. Yesypenko, C. Chen, and P.-G. Martinsson, A simplified fast multipole method based on strong recursive skeletonization, Journal of Computational Physics524, 113707 (2025)

    work page 2025

  37. [38]

    R. E. Angulo and O. Hahn, Large-scale dark matter simulations, Living Reviews in Computational Astrophysics8, 1 (2022)

    work page 2022

  38. [39]

    Fukuda and H

    I. Fukuda and H. Nakamura, Non-Ewald methods for evaluating the electrostatic interactions of charge systems: similarity and difference, Biophysical Reviews14, 1315–1340 (2022)

    work page 2022

  39. [40]

    Wang, A hybrid Fast Multipole Method for cosmologicaln-body simulations, Research in Astronomy and Astrophysics 21, 003 (2021)

    Q. Wang, A hybrid Fast Multipole Method for cosmologicaln-body simulations, Research in Astronomy and Astrophysics 21, 003 (2021)

    work page 2021

  40. [41]

    N. Y. Gnedin, Hierarchical particle mesh: An FFT-accelerated fast multipole method, The Astrophysical Journal Supple- ment Series243, 19 (2019)

    work page 2019

  41. [42]

    Stenqvist, V

    B. Stenqvist, V. Aspelin, and M. Lund, Generalized moment correction for long-ranged electrostatics, Journal of Chemical Theory and Computation16, 3737 (2020)

    work page 2020

  42. [43]

    Accelerating Molecular Dynamics Simulations using Fast Ewald Summation with Prolates

    J. Liang, L. Lu, A. Barnett, L. Greengard, and S. Jiang, Accelerating fast Ewald summation with prolates for molecular dynamics simulations, arXiv:2505.09727 (2025)

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  43. [44]

    Su, H.-Y

    Y. Su, H.-Y. Huang, and E. T. Campbell, Nearly tight Trotterization of interacting electrons, Quantum5, 495 (2021)

    work page 2021

  44. [45]

    G. H. Low and N. Wiebe, Hamiltonian Simulation in the Interaction Picture, arXiv:1805.00675 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  45. [46]

    Babbush, D

    R. Babbush, D. W. Berry, J. R. McClean, and H. Neven, Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size, npj Quantum Information5, 92 (2019)

    work page 2019

  46. [47]

    Babbush, N

    R. Babbush, N. Wiebe, J. McClean, J. McClain, H. Neven, and G. K.-L. Chan, Low-Depth Quantum Simulation of Materials, Physical Review X8, 011044 (2018)

    work page 2018

  47. [48]

    Babbush, C

    R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Physical Review X8, 041015 (2018)

    work page 2018

  48. [49]

    I. D. Kivlichan, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, W. Sun, Z. Jiang, N. Rubin, A. Fowler, A. Aspuru-Guzik, H. Neven, and R. Babbush, Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization, Quantum4, 296 (2020)

    work page 2020

  49. [50]

    Optimizing Quantum Circuits for Arithmetic

    T. H¨ aner, M. Roetteler, and K. M. Svore, Optimizing Quantum Circuits for Arithmetic, arXiv:1805.12445 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  50. [51]

    S. Liao, M. Lopez, and S. Leutenegger, High dimensional similarity search with space filling curves, inProceedings 17th International Conference on Data Engineering(2001) pp. 615–622

    work page 2001

  51. [52]

    Barkalov, A

    K. Barkalov, A. Shtanyuk, and A. Sysoyev, A fast kNN algorithm using multiple space-filling curves, Entropy24, 767 (2022)

    work page 2022

  52. [53]

    S. Li, L. Simons, J. B. Pakaravoor, F. Abbasinejad, J. D. Owens, and N. Amenta, kANN on the GPU with shifted sorting, inProceedings of the Fourth ACM SIGGRAPH / Eurographics Conference on High-Performance Graphics, EGGH-HPG’12 (Eurographics Association, Goslar, DEU, 2012) p. 39–47

    work page 2012

  53. [54]

    Gr¨ uneis, J

    A. Gr¨ uneis, J. J. Shepherd, A. Alavi, D. P. Tew, and G. H. Booth, Explicitly correlated plane waves: Accelerating convergence in periodic wavefunction expansions, The Journal of Chemical Physics139, 84112 (2013)

    work page 2013

  54. [55]

    H¨ attig, W

    C. H¨ attig, W. Klopper, A. K¨ ohn, and D. P. Tew, Explicitly correlated electrons in molecules, Chemical Reviews112, 4 (2011)

    work page 2011

  55. [56]

    Harl and G

    J. Harl and G. Kresse, Cohesive energy curves for noble gas solids calculated by adiabatic connection fluctuation-dissipation theory, Physical Review B77, 45136 (2008)

    work page 2008

  56. [57]

    J. J. Shepherd, A. Gr¨ uneis, G. H. Booth, G. Kresse, and A. Alavi, Convergence of many-body wave-function expansions using a plane-wave basis: From homogeneous electron gas to solid state systems, Physical Review B86, 35111 (2012)

    work page 2012

  57. [58]

    Helgaker, W

    T. Helgaker, W. Klopper, H. Koch, and J. Noga, Basis-set convergence of correlated calculations on water, Journal of Chemical Physics106, 9639 (1998)

    work page 1998

  58. [59]

    W. Klopper, Limiting values for Møller-Plesset second-order correlation energies of polyatomic systems: A benchmark study on Ne, HF, H 2O, N2, and He...He, The Journal of Chemical Physics102, 6168 (1995)

    work page 1995

  59. [60]

    Halkier, T

    A. Halkier, T. Helgaker, P. Jørgensen, W. Klopper, H. Koch, J. Olsen, and A. K. Wilson, Basis-set convergence in correlated calculations on Ne, N 2, and H 2, Chemical Physics Letters286, 243 (1998)

    work page 1998

  60. [61]

    Fenn and G

    M. Fenn and G. Steidl, FMM and H-matrices: A short introduction to the basic idea (2002)

    work page 2002

  61. [62]

    Greengard and V

    L. Greengard and V. Rokhlin,On the Efficient Implementation of the Fast Multipole Algorithm, Tech. Rep. (Yale University Department of Computer Science, 1988)

    work page 1988

  62. [63]

    Greengard and V

    L. Greengard and V. Rokhlin, A new version of the fast multipole method for the Laplace equation in three dimensions, Acta Numerica6, 229 (1997)

    work page 1997

  63. [64]

    Shanker and H

    B. Shanker and H. Huang, Accelerated Cartesian expansions–A fast method for computing of potentials of the formR −ν for all realν, Journal of Computational Physics226, 732 (2007). Appendix A: Additional FMM implementation details The main text primarily considers a simplified version of FMM that uses zeroth-order expansions (see Algorithm 1). However, hig...

    work page 2007

  64. [65]

    (P+ 1) 2 multipole and local expansion coefficients for each box outside of the leaf level,

    work page

  65. [66]

    operators (T M M andT LL) that translate the origins of the multipole and local expansions (respectively) from the centroid of one box to the centroid of another, and

    work page

  66. [67]

    The precise details of the various translation operators are one of the primary considerations in an FMM implemen- tation, and they determine the cost of tree traversal

    operators (T M L) that translate the multipole expansion coefficients about one box into local expansion coeffi- cients about a box in its interaction list. The precise details of the various translation operators are one of the primary considerations in an FMM implemen- tation, and they determine the cost of tree traversal. Generically, they only depend ...

    work page