CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams
summary
CFLOBDDs present a compressed Boolean-function representation that can be exponentially smaller than BDDs and, versus the decision tree, offer a double-exponential compression in the best case. The data structure adds hierarchical grouping and non‑recursive procedure-style reuse, is made canonical by structural constraints, and supports polynomial-time operations. Implemented for quantum-circuit simulation, it scales to 65,536 qubits for GHZ, 524,288 for Bernstein–Vazirani, 4,194,304 for Deutsch–Jozsa, and 4,096 for Grover, often outperforming BDDs by 128×–8,192×, though it performs poorly on QFT; intended as a plug-compatible replacement for BDDs.
AI-written summary · about
chapters (12)
- 0:00Introduction to CFLOBDDs
- 1:05BDDs and limitations
- 2:51From BDDs to CFLOBDDs
- 4:16Merging vertices in CFLOBDDs
- 8:33Why CFLOBDDs are context-free
- 8:55CFLOBDDs vs BDDs on matrices
- 10:20Compression benefits
- 11:05Canonical representation
- 11:46CFLOBDDs as BDD replacements
- 12:30Quantum simulation performance
- 13:32Conclusion and future
- 14:14Q&A
related talks
49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit
44mEfficient Enumeration Algorithms via Circuits
43mA Dichotomy for Queries with Negation in Probabilistic Databases
32mCircuits for Querying Trees: A Little Survey
53mDirect Access for Conjunctive Queries with Negation
51mFactorized Databases
53mQuadrable
15mThe Choice Construct in the Soufflé Language