一句话：提出 CFLOBDD，一种可替代 BDD 的布尔函数压缩表示，最佳情况下比 BDD 指数级更小、比决策树双指数级更小。
本文提出 CFLOBDDs，一种用于布尔函数的新压缩表示，可作为 BDD 的即插即用替代。它继承 BDD 的许多良好性质，但在最佳情况下，同一函数的 CFLOBDD 可比任何 BDD 指数级更小，比决策树双指数级更小，从而有望加速应用并处理更大规模实例。作者将 CFLOBDD 用于量子线路模拟，在多个标准问题上可扩展性显著优于 BDD：15 分钟超时下，GHZ 可处理 65,536 个量子比特，Bernstein-Vazirani 为 524,288，Deutsch-Jozsa 为 4,194,304，Grover 为 4,096，分别比 BDD 提升 128×、1,024×、8,192× 和 128×。
This article presents a new compressed representation of Boolean functions, called CFLOBDDs (for Context-Free-Language Ordered Binary Decision Diagrams). They are essentially a plug-compatible alternative to BDDs (Binary Decision Diagrams), and hence are useful for representing certain classes of functions, matrices, graphs, relations, and so forth in a highly compressed fashion. CFLOBDDs share many of the good properties of BDDs, but—in the best case—the CFLOBDD for a Boolean function can be exponentially smaller than any BDD for that function . Compared with the size of the decision tree for a function, a CFLOBDD—again, in the best case—can give a double-exponential reduction in size . They have the potential to permit applications to (i) execute much faster and (ii) handle much larger problem instances than has been possible heretofore. We applied CFLOBDDs in quantum-circuit simulation and found that for several standard problems, the improvement in scalability, compared to BDDs, is quite dramatic. With a 15-minute timeout, the number of qubits that CFLOBDDs can handle are 65,536 for Greenberger-Horne-Zellinger, 524,288 for Bernstein-Vazirani, 4,194,304 for Deutsch-Jozsa, and 4,096 for Grover’s algorithm, besting BDDs by factors of 128×, 1,024×, 8,192×, and 128×, respectively.
@article{paperbot2674,
title = {CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams},
author = {Meghana Aparna Sistla and Swarat Chaudhuri and Thomas Reps},
journal = {ACM Transactions on Programming Languages and Systems},
volume = {46},
number = {2},
year = {2024},
doi = {10.1145/3651157}
}