Trie-based ranking of quantum many-body states

Abstract

Ranking bit patterns -- finding the index of a given pattern in an ordered sequence -- is a major bottleneck scaling up numerical quantum many-body calculations, as fermionic and hard-core bosonic states translate naturally to bit patterns. Traditionally, ranking is done by bisectioning search, which has poor cache performance on modern machines. We instead propose to use tries (prefix trees), thereby achieving a two- to ten-fold speed-up in numerical experiments with only moderate memory overhead. For the important problem of ranking permutations, the corresponding tries can be compressed. These compressed "staggered" lookups allow for a considerable speed-up while retaining the memory requirements of prior algorithms based on the combinatorial number system.

References in corpus (20)

• The density-matrix renormalization group
• Continuous-time Monte Carlo methods for quantum impurity models
• The numerical renormalization group method for quantum impurity systems
• Density matrix embedding: A simple alternative to dynamical mean-field theory
• Towards the solution of the many-electron problem in real materials: equation of state of the hydrogen chain with state-of-the-art many-body methods
• Verification of quantum computation: An overview of existing approaches
• w2dynamics: Local one- and two-particle quantities from dynamical mean field theory
• Nevanlinna Analytical Continuation
• High-order commutator-free exponential time-propagation of driven quantum systems
• Sparse modeling approach to analytical continuation of imaginary-time quantum Monte Carlo data
• Quantum Lattice Model Solver $\mathcal{H}\Phi$
• Systematically improvable multi-scale solver for correlated electron systems
• Conserved quantities of SU(2)-invariant interactions for correlated fermions and the advantages for quantum Monte Carlo simulations
• Sublattice Coding Algorithm and Distributed Memory Parallelization for Large-Scale Exact Diagonalizations of Quantum Many-Body Systems
• EDIpack: A parallel exact diagonalization package for quantum impurity problems
• Exact diagonalization solver for the extended dynamical mean-field theory
• Paradeisos: a perfect hashing algorithm for many-body eigenvalue problems
• Electron-light interaction in nonequilibrium -- exact diagonalization for time dependent Hubbard Hamiltonians
• Photoexcitations in the Hubbard model -- generalized Loschmidt amplitude analysis of impact ionization in small clusters
• libcommute/pycommute: A quantum operator algebra domain-specific language and exact diagonalization toolkit

Cited by in corpus (2)

• Update of $\mathcal{H}\Phi$: Newly added functions and methods in versions 2 and 3
• Next-generation EDIpack: A Lanczos-based package for quantum impurity models featuring general broken-symmetry phases, flexible bath topologies and multi-platform interoperability