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 (6)

• Continuous-time Monte Carlo methods for quantum impurity models
• The numerical renormalization group method for quantum impurity systems
• 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
• Exact diagonalization solver for the extended dynamical mean-field theory
• Photoexcitations in the Hubbard model -- generalized Loschmidt amplitude analysis of impact ionization in small clusters

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