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 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.
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
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).
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.
The decision diagram (DD) data structure enables fast linear-algebra calculations by bringing vectors into a normal form and subsequently merging equivalent ones, yielding a minimally-sized DD modulo the equivalence relation. A fruitful application area is quantum-circuit simulation, where the vectors represent quantum states. The Local Invertible Map Decision Diagram (LIMDD) type, merges LIM-equivalent (typically Pauli-gate equivalent) vectors, can efficiently simulate Clifford circuits as well as some high-T-count circuits, and has theoretically been proven exponentially faster for simulation than other well-developed data structures, including other common DD variants. However, these exponential advantages have not fully materialized yet in existing implementations, for which the normal-form procedure, which is a highly complex algorithm, is either absent or only partially implemented. We here present a novel normal-form algorithm for Pauli-LIMDDs, achieving a worst-case speedup from O(n3) to O(n2) for an n-qubit DD node with a single child node while keeping the O(n3) run time in case of two distinct children nodes. We implement the algorithm as part of QolDDer, our Pauli-LIMDD simulator for quantum circuits, written from scratch in C/C++. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, is significantly faster than the existing LIMDD simulators on such circuits, and on a public quantum-circuit data set often outperforms them by an order of magnitude. In the future, we envision that our work will enable further application and development of LIMDD variants, not only for quantum design tasks, but also for analysis of linear-algebra-based systems in general.