Trie-based ranking of quantum many-body states

Ranking bit patterns-finding the index of a given pattern in an ordered sequence-is a major bottleneck in 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 tenfold speedup 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 speedup while retaining the memory requirements of prior algorithms based on the combinatorial number system.

Automated summary

Ranking bit patterns is a significant bottleneck in numerical quantum many-body calculations. Traditional bisectioning search has poor cache performance, but using tries (prefix trees) can achieve a two-to tenfold speedup with moderate memory overhead. For ranking permutations, compressed tries offer considerable speedup while maintaining memory requirements.