论文标题
量子多体状态的基于TRIE的排名
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 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.
