一句话：提出带过程调用机制的层次化加权决策图 WCFLOBDDs，在量子线路模拟中兼顾 WBDD 与 CFLOBDD 的优势。
本文提出加权上下文无关语言有序二叉决策图（WCFLOBDDs），一种层次化决策图，可视为带过程调用机制的加权 BDD（WBDD）扩展。它针对表示 B^n→D 的函数，尤其是像集 V⊆D 含大量不同值的情形；对某些函数，其表示比 WBDD 指数级更简洁。作者将 WCFLOBDDs 用于量子线路模拟，并在部分基准上优于 WBDD。15 分钟超时下，其可处理量子比特数可达 WBDD 的 1–64 倍、CFLOBDD 的 1–128 倍；总体性能约与 WBDD 和 CFLOBDD 中较优者相当，运行时间结果则更复杂。
This paper presents a new data structure, called Weighted Context-Free-Language Ordered BDDs (WCFLOBDDs), which are a hierarchically structured decision diagram, akin to Weighted BDDs (WBDDs) enhanced with a procedure-call mechanism. For some functions, WCFLOBDDs are exponentially more succinct than WBDDs. They are potentially beneficial for representing functions of type B n → D , when a function’s image V ⊆ D has many different values. We apply WCFLOBDDs in quantum-circuit simulation, and find that they perform better than WBDDs on certain benchmarks. With a 15-minute timeout, the number of qubits that can be handled by WCFLOBDDs is 1 − 64 × that of WBDDs (and 1 − 128 × that of CFLOBDDs, which are an unweighted version of WCFLOBDDs). These results support the conclusion that for this application—from the standpoint of problem size, measured as the number of qubits—WCFLOBDDs provide the best of both worlds: performance roughly matches whichever of WBDDs and CFLOBDDs is better. (From the standpoint of running time, the results are more nuanced.)
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2305-13610,
title = {Weighted Context-Free-Language Ordered Binary Decision Diagrams},
author = {Meghana Sistla and Swarat Chaudhuri and Thomas Reps},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {OOPSLA2},
year = {2024},
doi = {10.1145/3689760}
}