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).
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 previous research, a novel structure was discussed for representing the matrices that can be built from an n-variable r-valued reversible/quantum circuit. This structure, called a QMDD, takes on a form similar to that of a reduced-ordered-binary-decision-diagram (ROBDD). It is known that the order of variables used for developing an ROBDD from a binary logic circuit is relevant to the size and structure of that ROBDD. This paper determines what effect, if any, variable order has on the QMDD structure and proposes a simple heuristic for choosing a 'good' variable order.