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:1909.12658 · Theoretical Computer Science

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

Seiichiro Tani

Published Apr 6, 2025• 3 citations
arXivHTMLPDF

Abstract

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

DOI
10.1016/j.tcs.2025.115230

Related papers

Large Width Nondeterministic Quantum OBDDs

Aida Gainutdinova

In this paper we investigate ordered binary decision diagrams (OBDD) – a model for computing Boolean functions. The aim of this work is a comparative complexity analysis of quantum and classical nondeterministic OBDDs of large width. We study the complexity of computing the Boolean function "Equality" in nondeterministic quantum OBDDs for different order of reading variables in comparison with the classical complexity. We show that when using the order of reading for which the width of the classical nondeterministic OBDD is constant, the width of the quantum model is linear and the proved lower bound is tight. We define a Boolean function for which the width of nondeterministic quantum OBDD is exponential for any order of reading variables. We construct a quantum algorithm for computing this function with zero error. We present a result on the relationship between complexity classes for quantum and classical nondeterministic OBDDs of large width.

Вестник Пермского университета Математика Механика Информатика•Jan 1, 2024•0 citations

Very narrow quantum OBDDs and width hierarchies for classical OBDDs

Farid Mansurovich Ablayev, Aida Gainutdinova, Kamil Ravilevich Khadiev +1 more

In the paper we investigate Ordered Binary Decision Diagrams (OBDDs)–a model for computing Boolean functions. We present a series of results on the comparative complexity for several variants of OBDDmodels. • We present results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k+1. • We consider quantum and classical nondeterminism. We show that quantum nondeterminismcan bemore efficient than classical nondeterminism. In particular, an explicit function is presented that is computed by a quantum nondeterministic OBDD of constant width but any classical nondeterministic OBDD for this function needs non-constant width. • We also present new hierarchies on widths of deterministic and nondeterministic OBDDs.

Lobachevskii Journal of Mathematics•Nov 1, 2016•37 citations

Comparative complexity of quantum and classical OBDDs for total and partial functions

Aida Gainutdinova

We consider a model of computation for discrete functions—Ordered Binary Decision Diagrams (OBDD).We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of OBDD. It is known that for total functions bounded error quantum OBDDs can be exponentially more effective than deterministic and bounded error probabilistic OBDDs. We show that such quantum OBDDs also can be exponentially more effective than nondeterministic OBDDs (both quantum and classical). For partial functions the gap can be more significant. For partial function depending on a parameter k exact quantum OBDD has the width two. Deterministic and bounded error probabilistic OBDD for this function must have a width exponentially depending on k .

Russian Mathematics•Oct 14, 2015•15 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

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•16 citations

Quantum and classical nondeterministic OBDDs

Aida Gainutdinova

A model of nondeterministic ordered binary decision diagrams (NOBDDs) was analyzed. A method for proving a lower bound on the complexity of quantum NOBDDs was developed. Two functions were introduced: one function has linear complexity in the quantum NOBDD but constant complexity in the classical NOBDD, while the other function demonstrates the same complexity in both quantum and classical NOBDD models. The relationships among the complexity classes specific to the OBDD model were described.

Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki•Dec 22, 2024•1 citation
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).
In this paper we investigate ordered binary decision diagrams (OBDD) – a model for computing Boolean functions. The aim of this work is a comparative complexity analysis of quantum and classical nondeterministic OBDDs of large width. We study the complexity of computing the Boolean function "Equality" in nondeterministic quantum OBDDs for different order of reading variables in comparison with the classical complexity. We show that when using the order of reading for which the width of the classical nondeterministic OBDD is constant, the width of the quantum model is linear and the proved lower bound is tight. We define a Boolean function for which the width of nondeterministic quantum OBDD is exponential for any order of reading variables. We construct a quantum algorithm for computing this function with zero error. We present a result on the relationship between complexity classes for quantum and classical nondeterministic OBDDs of large width.
In the paper we investigate Ordered Binary Decision Diagrams (OBDDs)–a model for computing Boolean functions. We present a series of results on the comparative complexity for several variants of OBDDmodels. • We present results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k+1. • We consider quantum and classical nondeterminism. We show that quantum nondeterminismcan bemore efficient than classical nondeterminism. In particular, an explicit function is presented that is computed by a quantum nondeterministic OBDD of constant width but any classical nondeterministic OBDD for this function needs non-constant width. • We also present new hierarchies on widths of deterministic and nondeterministic OBDDs.
We consider a model of computation for discrete functions—Ordered Binary Decision Diagrams (OBDD).We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of OBDD. It is known that for total functions bounded error quantum OBDDs can be exponentially more effective than deterministic and bounded error probabilistic OBDDs. We show that such quantum OBDDs also can be exponentially more effective than nondeterministic OBDDs (both quantum and classical). For partial functions the gap can be more significant. For partial function depending on a parameter k exact quantum OBDD has the width two. Deterministic and bounded error probabilistic OBDD for this function must have a width exponentially depending on k .
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
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.