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.)