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:2305.13610 · Proceedings of the ACM on Programming Languages

Weighted Context-Free-Language Ordered Binary Decision Diagrams

Meghana Aparna Sistla, Swarat Chaudhuri, Thomas Reps

Published Oct 8, 2024• 15 citations
arXivHTMLPDF

Abstract

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

DOI
10.1145/3689760

Related papers

CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams

Meghana Aparna Sistla, Swarat Chaudhuri, Thomas Reps

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.

arXiv:2211.06818•ACM Transactions on Programming Languages and Systems•Mar 4, 2024•22 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•25 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 representing a Boolean function . Since OBDDs have many nice properties as data structures, they have been extensively studied for decades in 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 that they 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 OBDD for a given function. Friedman and Supowit provided a clever deterministic algorithm with time/space complexity O ⁎ ( 3 n ) ⁎ , where n is the number of variables of the function, which is much better than the trivial brute-force bound O ⁎ ( n ! 2 n ) . This paper shows that a further speedup is possible with quantum computers by presenting a quantum algorithm that produces a minimum OBDD together with the corresponding variable ordering in O ⁎ ( 2.77286 n ) time and space with an exponentially small error probability. Moreover, this algorithm can be adapted to constructing other minimum decision diagrams, such as zero-suppressed BDDs (ZBDDs or ZDDs).

arXiv:1909.12658•Theoretical Computer Science•Apr 6, 2025•5 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•7 citations

A new design approach for RSFQ logic circuits based on the binary decision diagram

Nobuyuki Yoshikawa, 博史 多胡, K. Yoneyama

We will propose a new design approach for single-flux-quantum (SFQ) logic circuits based on a binary decision diagram (BDD). The BDD is a way to represent a logical function by using a directed graph, which is composed of nodes having one input (root) and two outputs (branches). The node has binary states internally which can be controlled from outside, and it switches a messenger entering from the root into one of two branches depending on the internal state. It has been proven that any combinational logic can be represented by this basic element. We will show that the BDD is effectively implemented by an SFQ circuit, where the node is replaced with an SFQ D/sub 2/ flip-flop. Important features of the BDD SFQ logic circuit are simplicity of circuit structure, self-timed nature and high modularity. We have designed a BDD SFQ adder and showed that the junction count and latency are smaller than that of the conventional RSFQ adder.

IEEE Transactions on Applied Superconductivity•Jun 1, 1999•18 citations

BDD-Based Synthesis of Reversible Logic

Robert Wille, Rolf Drechsler

Reversible logic became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.

International Journal of Applied Metaheuristic Computing•Oct 1, 2010•8 citations
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.)
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.
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 representing a Boolean function . Since OBDDs have many nice properties as data structures, they have been extensively studied for decades in 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 that they 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 OBDD for a given function. Friedman and Supowit provided a clever deterministic algorithm with time/space complexity O ⁎ ( 3 n ) ⁎ , where n is the number of variables of the function, which is much better than the trivial brute-force bound O ⁎ ( n ! 2 n ) . This paper shows that a further speedup is possible with quantum computers by presenting a quantum algorithm that produces a minimum OBDD together with the corresponding variable ordering in O ⁎ ( 2.77286 n ) time and space with an exponentially small error probability. Moreover, this algorithm can be adapted to constructing other minimum decision diagrams, such as zero-suppressed BDDs (ZBDDs or ZDDs).
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
We will propose a new design approach for single-flux-quantum (SFQ) logic circuits based on a binary decision diagram (BDD). The BDD is a way to represent a logical function by using a directed graph, which is composed of nodes having one input (root) and two outputs (branches). The node has binary states internally which can be controlled from outside, and it switches a messenger entering from the root into one of two branches depending on the internal state. It has been proven that any combinational logic can be represented by this basic element. We will show that the BDD is effectively implemented by an SFQ circuit, where the node is replaced with an SFQ D/sub 2/ flip-flop. Important features of the BDD SFQ logic circuit are simplicity of circuit structure, self-timed nature and high modularity. We have designed a BDD SFQ adder and showed that the junction count and latency are smaller than that of the conventional RSFQ adder.
Reversible logic became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.