**CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams**

*
Meghana Aparna Sistla, Swarat Chaudhuri, and Thomas Reps
*

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.

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 GHZ, 524,288 for BV; 4,194,304 for DJ; and 4,096 for Grover's Algorithm, besting BDDs by factors of 128×, 1,024×, 8,192×, and 128×, respectively.

(Click here to access the paper: PDF.)