论文标题
cflobdds：无上下文的二进制决策图
CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams
论文作者
论文摘要
本文提出了一个新的布尔函数压缩表示形式，称为cflobdds（用于无上下文有序的二进制决策图）。它们本质上是BDD（二进制决策图）的插头兼容替代方案，因此可用于以高度压缩的方式来表示某些类别的功能，矩阵，图形，关系等。 CFLOBDD具有BDD的许多好属性，但是 - 在最好的情况下 - 布尔函数的CFLOBDD的指数呈指数小于该功能的任何BDD。与函数的决策树的大小相比，在最佳情况下，cflobdd（同时）大小可缩小双指数降低。他们有可能允许申请（i）执行得更快，并且（ii）处理比迄今为止可能更大的问题实例。 CFLOBDDS是一种超越BDD（及其许多亲戚）的新决策图。关键洞察力是重复使用子模式数据的新方法：cflobdds的组件是层次结构化的，因此可以将子模式描述为独立的''过程'并重复使用。 我们将CFLOBDD应用于模拟量子电路的问题，并发现在几种标准问题上，可扩展性的提高（使用BDDS仿真）非常引人注目。特别是，与BDDS相比，使用CFLOBDD可以处理的Qubits数量更大，GHz的量子为128倍。 BV 1,024X； DJ为8,192X;以及Grover算法的128倍。 （有了15分钟的超时，GHz可以处理的量子位数为65,536，DJ的BV为524,288； Grover的算法为4,194,304； 4,096。
This paper 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 useful for representing certain classes of functions, matrices, graphs, relations, etc. 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. CFLOBDDs are a new kind of decision diagram that go beyond BDDs (and their many relatives). The key insight is a new way to reuse sub-decision-diagrams: components of CFLOBDDs are structured hierarchically, so that sub-decision-diagrams can be treated as standalone ''procedures'' and reused. We applied CFLOBDDs to the problem of simulating quantum circuits, and found that for several standard problems the improvement in scalability--compared to simulation using BDDs--is quite dramatic. In particular, the number of qubits that could be handled using CFLOBDDs was larger, compared to BDDs, by a factor of 128x for GHZ; 1,024x for BV; 8,192x for DJ; and 128x for Grover's algorithm. (With a 15-minute timeout, the number of qubits that CFLOBDDs can handle are 65,536 for GHZ, 524,288 for BV; 4,194,304 for DJ; and 4,096 for Grover's Algorithm.)
