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