  Over the years, many variants of Binary Decision Diagrams (BDDs) have been
developed to address the deficiencies of vanilla BDDs. A recent innovation is
the Context-Free-Language Ordered BDD (CFLOBDD), a hierarchically structured
decision diagram, akin to BDDs enhanced with a procedure-call mechanism, which
allows substructures to be shared in ways not possible with BDDs. For some
functions, CFLOBDDs are exponentially more succinct than BDDs. Unfortunately,
the multi-terminal extension of CFLOBDDs, like multi-terminal BDDs, cannot
efficiently represent functions of type B^n -> D, when the function's range has
many different values. This paper addresses this limitation through a new data
structure called Weighted CFLOBDDs (WCFLOBDDs). WCFLOBDDs extend CFLOBDDs using
insights from the design of Weighted BDDs (WBDDs) -- BDD-like structures with
weights on edges. We show that WCFLOBDDs can be exponentially more succinct
than both WBDDs and CFLOBDDs. We also evaluate WCFLOBDDs for quantum-circuit
simulation, and find that they perform better than WBDDs and CFLOBDDs on most
benchmarks. With a 15-minute timeout, the number of qubits that can be handled
by WCFLOBDDs is 1,048,576 for GHZ (1x over CFLOBDDs, 256x over WBDDs); 262,144
for BV and DJ (2x over CFLOBDDs, 64x over WBDDs); and 2,048 for QFT (128x over
CFLOBDDs, 2x over WBDDs).
