Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2211.06818 · ACM Transactions on Programming Languages and Systems

CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams

Meghana Aparna Sistla, Swarat Chaudhuri, Thomas Reps

Published Mar 4, 2024• 16 citations
arXivHTMLPDF

Abstract

This article 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 are useful for representing certain classes of functions, matrices, graphs, relations, and so forth 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 Greenberger-Horne-Zellinger, 524,288 for Bernstein-Vazirani, 4,194,304 for Deutsch-Jozsa, and 4,096 for Grover’s algorithm, besting BDDs by factors of 128×, 1,024×, 8,192×, and 128×, respectively.

DOI
10.1145/3651157

Related papers

Weighted Context-Free-Language Ordered Binary Decision Diagrams

Meghana Aparna Sistla, Swarat Chaudhuri, Thomas Reps

This paper presents a new data structure, called Weighted Context-Free-Language Ordered BDDs (WCFLOBDDs), which are a hierarchically structured decision diagram, akin to Weighted BDDs (WBDDs) enhanced with a procedure-call mechanism. For some functions, WCFLOBDDs are exponentially more succinct than WBDDs. They are potentially beneficial for representing functions of type B n → D , when a function’s image V ⊆ D has many different values. We apply WCFLOBDDs in quantum-circuit simulation, and find that they perform better than WBDDs on certain benchmarks. With a 15-minute timeout, the number of qubits that can be handled by WCFLOBDDs is 1 − 64 × that of WBDDs (and 1 − 128 × that of CFLOBDDs, which are an unweighted version of WCFLOBDDs). These results support the conclusion that for this application—from the standpoint of problem size, measured as the number of qubits—WCFLOBDDs provide the best of both worlds: performance roughly matches whichever of WBDDs and CFLOBDDs is better. (From the standpoint of running time, the results are more nuanced.)

arXiv:2305.13610•Proceedings of the ACM on Programming Languages•Oct 8, 2024•8 citations

Symbolic Quantum Simulation with Quasimodo

Meghana Aparna Sistla, Swarat Chaudhuri, Thomas Reps

Abstract The simulation of quantum circuits on classical computers is an important problem in quantum computing. Such simulation requires representations of distributions over very large sets of basis vectors, and recent work has used symbolic data-structures such as Binary Decision Diagrams (BDDs) for this purpose. In this tool paper, we present Quasimodo, an extensible, open-source Python library for symbolic simulation of quantum circuits. Quasimodo is specifically designed for easy extensibility to other backends. Quasimodo allows simulations of quantum circuits, checking properties of the outputs of quantum circuits, and debugging quantum circuits. It also allows the user to choose from among several symbolic data-structures—both unweighted and weighted BDDs, and a recent structure called Context-Free-Language Ordered Binary Decision Diagrams (CFLOBDDs)—and can be easily extended to support other symbolic data-structures.

arXiv:2302.04349•Lecture notes in computer science•Jan 1, 2023•21 citations

Quantum algorithm for finding the optimal variable ordering for binary decision diagrams

Seiichiro Tani

An ordered binary decision diagram (OBDD) is a directed acyclic graph that represents a Boolean function.Since OBDDs have many nice properties as data structures,they have been extensively studied for decades in both theoretical and practical fields,such as VLSI (Very Large Scale Integration) design, formal verification, machine learning, and combinatorial problems.Arguably, the most crucial problem in using OBDDs is thatthey may vary exponentially in size depending on their variable ordering (i.e., the order in which the variables are to be read) when they represent the same function.Indeed, it is NP hard to find an optimal variable ordering that minimizes an OBDDfor a given function.Friedman and Supowit provided a clever deterministic algorithm with time/space complexityO*(3n), where $n$ is the number of variables of the function,which is much better than the trivial brute-force bound O*(n!2n)$.This paper shows that a further speedup is possible with quantum computersby presenting a quantum algorithmthat produces a minimum OBDD together with the corresponding variable orderingin O*(2.77286n) time and space with an exponentially small error probability. Moreover, this algorithm can be adapted toconstructing other minimum decision diagrams such as zero-suppressed BDDs (ZBDDs or ZDDs).

arXiv:1909.12658•Theoretical Computer Science•Apr 6, 2025•3 citations

BDD2Seq: Enabling Scalable Reversible-Circuit Synthesis via Graph-to-Sequence Learning

Mingkai Miao, Jianheng Tang, Guangyu Hu +1 more

Binary Decision Diagrams (BDDs) are instrumental in many electronic design automation (EDA) tasks thanks to their compact representation of Boolean functions. In BDD‑based reversible‑circuit synthesis, which is critical for quantum computing, the chosen variable ordering governs the number of BDD nodes and thus the key metrics of resource consumption, such as Quantum Cost. Because finding an optimal variable ordering for BDDs is an NP‑complete problem, existing heuristics often degrade as circuit complexity grows. We introduce BDD2Seq, a graph‑to‑sequence framework that couples a Graph Neural Network encoder with a Pointer‑Network decoder and Diverse Beam Search to predict high‑quality orderings. By treating the circuit netlist as a graph, BDD2Seq learns structural dependencies that conventional heuristics overlooked, yielding smaller BDDs and faster synthesis. Extensive experiments on three public benchmarks show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern heuristic algorithms. To the best of our knowledge, this is the first work to tackle the variable‑ordering problem in BDD‑based reversible‑circuit synthesis with a graph‑based generative model and diversity‑promoting decoding.

Proceedings of the AAAI Conference on Artificial Intelligence•Mar 14, 2026•0 citations

BDD2Seq: Enabling Scalable Reversible-Circuit Synthesis via Graph-to-Sequence Learning

Mingkai Miao, Jianheng Tang, Guangyu Hu +1 more

Binary Decision Diagrams (BDDs) are instrumental in many electronic design automation (EDA) tasks thanks to their compact representation of Boolean functions. In BDD-based reversible-circuit synthesis, which is critical for quantum computing, the chosen variable ordering governs the number of BDD nodes and thus the key metrics of resource consumption, such as Quantum Cost. Because finding an optimal variable ordering for BDDs is an NP-complete problem, existing heuristics often degrade as circuit complexity grows. We introduce BDD2Seq, a graph-to-sequence framework that couples a Graph Neural Network encoder with a Pointer-Network decoder and Diverse Beam Search to predict high-quality orderings. By treating the circuit netlist as a graph, BDD2Seq learns structural dependencies that conventional heuristics overlooked, yielding smaller BDDs and faster synthesis. Extensive experiments on three public benchmarks show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern heuristic algorithms. To the best of our knowledge, this is the first work to tackle the variable-ordering problem in BDD-based reversible-circuit synthesis with a graph-based generative model and diversity-promoting decoding.

arXiv:2511.08315•Nov 11, 2025•0 citations

Quantum state preparation via free binary decision diagram

Yu Tanaka, Hayata Yamasaki, Mio Murao

Abstract Quantum state preparation (QSP) is the task of preparing a quantum state from a given classical description. The classical description of an n -qubit quantum state may have exp ⁡ ( O ( n ) ) parameters in general, which makes preparing the corresponding state inherently inefficient in the worst case. However, in many practical cases, we may be able to employ suitable data structures for QSP. Ordered binary decision diagrams (OBDDs) and free BDDs (FBDDs) are data structures that can represent large-scale data in a compressed way. An efficient QSP method for a subclass of OBDDs is known, but requires an O ( 2 n ) -sized quantum circuit in general, while QSP based on FBDDs, which includes OBDDs as a special case, remains unexplored. Here, we construct a state-preparation procedure for QSP when the classical description of a quantum state is given by an FBDD with weighted edges and analyze the space and time complexity of QSP in this setting. We provide a nontrivial example of an n -qubit state that can be represented by a weighted FBDD (WFBDD) with N = O ( poly ( n ) ) nodes rather than exp ( O ( n ) ) . We show that any quantum state represented by a QSP-admissible WFBDD with N nodes can be prepared by an O ( N ) -sized quantum circuit using at most N ancillary qubits, exponentially improving the required circuit size for QSP compared to other BDD-based QSPs. We also provide another example of an n -qubit state that can be represented by a WFBDD with N = O ( n 2 ) nodes and O ( n 2 ) ancillary qubits, for which the known amplitude-amplification-based QSP cost expression is exponential in n . These results provide techniques to employ FBDDs

arXiv:2407.01671•Journal of Physics A Mathematical and Theoretical•Jun 11, 2026•0 citations
This article 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 are useful for representing certain classes of functions, matrices, graphs, relations, and so forth 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 Greenberger-Horne-Zellinger, 524,288 for Bernstein-Vazirani, 4,194,304 for Deutsch-Jozsa, and 4,096 for Grover’s algorithm, besting BDDs by factors of 128×, 1,024×, 8,192×, and 128×, respectively.
This paper presents a new data structure, called Weighted Context-Free-Language Ordered BDDs (WCFLOBDDs), which are a hierarchically structured decision diagram, akin to Weighted BDDs (WBDDs) enhanced with a procedure-call mechanism. For some functions, WCFLOBDDs are exponentially more succinct than WBDDs. They are potentially beneficial for representing functions of type B n → D , when a function’s image V ⊆ D has many different values. We apply WCFLOBDDs in quantum-circuit simulation, and find that they perform better than WBDDs on certain benchmarks. With a 15-minute timeout, the number of qubits that can be handled by WCFLOBDDs is 1 − 64 × that of WBDDs (and 1 − 128 × that of CFLOBDDs, which are an unweighted version of WCFLOBDDs). These results support the conclusion that for this application—from the standpoint of problem size, measured as the number of qubits—WCFLOBDDs provide the best of both worlds: performance roughly matches whichever of WBDDs and CFLOBDDs is better. (From the standpoint of running time, the results are more nuanced.)
Abstract The simulation of quantum circuits on classical computers is an important problem in quantum computing. Such simulation requires representations of distributions over very large sets of basis vectors, and recent work has used symbolic data-structures such as Binary Decision Diagrams (BDDs) for this purpose. In this tool paper, we present Quasimodo, an extensible, open-source Python library for symbolic simulation of quantum circuits. Quasimodo is specifically designed for easy extensibility to other backends. Quasimodo allows simulations of quantum circuits, checking properties of the outputs of quantum circuits, and debugging quantum circuits. It also allows the user to choose from among several symbolic data-structures—both unweighted and weighted BDDs, and a recent structure called Context-Free-Language Ordered Binary Decision Diagrams (CFLOBDDs)—and can be easily extended to support other symbolic data-structures.
An ordered binary decision diagram (OBDD) is a directed acyclic graph that represents a Boolean function.Since OBDDs have many nice properties as data structures,they have been extensively studied for decades in both theoretical and practical fields,such as VLSI (Very Large Scale Integration) design, formal verification, machine learning, and combinatorial problems.Arguably, the most crucial problem in using OBDDs is thatthey may vary exponentially in size depending on their variable ordering (i.e., the order in which the variables are to be read) when they represent the same function.Indeed, it is NP hard to find an optimal variable ordering that minimizes an OBDDfor a given function.Friedman and Supowit provided a clever deterministic algorithm with time/space complexityO*(3n), where nnn is the number of variables of the function,which is much better than the trivial brute-force bound O*(n!2n)$.This paper shows that a further speedup is possible with quantum computersby presenting a quantum algorithmthat produces a minimum OBDD together with the corresponding variable orderingin O*(2.77286n) time and space with an exponentially small error probability. Moreover, this algorithm can be adapted toconstructing other minimum decision diagrams such as zero-suppressed BDDs (ZBDDs or ZDDs).
Binary Decision Diagrams (BDDs) are instrumental in many electronic design automation (EDA) tasks thanks to their compact representation of Boolean functions. In BDD‑based reversible‑circuit synthesis, which is critical for quantum computing, the chosen variable ordering governs the number of BDD nodes and thus the key metrics of resource consumption, such as Quantum Cost. Because finding an optimal variable ordering for BDDs is an NP‑complete problem, existing heuristics often degrade as circuit complexity grows. We introduce BDD2Seq, a graph‑to‑sequence framework that couples a Graph Neural Network encoder with a Pointer‑Network decoder and Diverse Beam Search to predict high‑quality orderings. By treating the circuit netlist as a graph, BDD2Seq learns structural dependencies that conventional heuristics overlooked, yielding smaller BDDs and faster synthesis. Extensive experiments on three public benchmarks show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern heuristic algorithms. To the best of our knowledge, this is the first work to tackle the variable‑ordering problem in BDD‑based reversible‑circuit synthesis with a graph‑based generative model and diversity‑promoting decoding.
Binary Decision Diagrams (BDDs) are instrumental in many electronic design automation (EDA) tasks thanks to their compact representation of Boolean functions. In BDD-based reversible-circuit synthesis, which is critical for quantum computing, the chosen variable ordering governs the number of BDD nodes and thus the key metrics of resource consumption, such as Quantum Cost. Because finding an optimal variable ordering for BDDs is an NP-complete problem, existing heuristics often degrade as circuit complexity grows. We introduce BDD2Seq, a graph-to-sequence framework that couples a Graph Neural Network encoder with a Pointer-Network decoder and Diverse Beam Search to predict high-quality orderings. By treating the circuit netlist as a graph, BDD2Seq learns structural dependencies that conventional heuristics overlooked, yielding smaller BDDs and faster synthesis. Extensive experiments on three public benchmarks show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern heuristic algorithms. To the best of our knowledge, this is the first work to tackle the variable-ordering problem in BDD-based reversible-circuit synthesis with a graph-based generative model and diversity-promoting decoding.
Abstract Quantum state preparation (QSP) is the task of preparing a quantum state from a given classical description. The classical description of an n -qubit quantum state may have exp ⁡ ( O ( n ) ) parameters in general, which makes preparing the corresponding state inherently inefficient in the worst case. However, in many practical cases, we may be able to employ suitable data structures for QSP. Ordered binary decision diagrams (OBDDs) and free BDDs (FBDDs) are data structures that can represent large-scale data in a compressed way. An efficient QSP method for a subclass of OBDDs is known, but requires an O ( 2 n ) -sized quantum circuit in general, while QSP based on FBDDs, which includes OBDDs as a special case, remains unexplored. Here, we construct a state-preparation procedure for QSP when the classical description of a quantum state is given by an FBDD with weighted edges and analyze the space and time complexity of QSP in this setting. We provide a nontrivial example of an n -qubit state that can be represented by a weighted FBDD (WFBDD) with N = O ( poly ( n ) ) nodes rather than exp ( O ( n ) ) . We show that any quantum state represented by a QSP-admissible WFBDD with N nodes can be prepared by an O ( N ) -sized quantum circuit using at most N ancillary qubits, exponentially improving the required circuit size for QSP compared to other BDD-based QSPs. We also provide another example of an n -qubit state that can be represented by a WFBDD with N = O ( n 2 ) nodes and O ( n 2 ) ancillary qubits, for which the known amplitude-amplification-based QSP cost expression is exponential in n . These results provide techniques to employ FBDDs