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:quant-ph/0507258

Quantum Ordered Binary Decision Diagrams with Repeated Tests

Matthias Homeister, Stephan Waack

Published Jul 27, 2005• 4 citations
arXivHTMLPDF

Abstract

Quantum branching programs (quantum binary decision diagrams, respectively) are a convenient tool for examining quantum computations using only a logarithmic amount of space. Recently several types of restricted quantum branching programs have been considered, e. g. read--once quantum branching programs. This paper considers quantum ordered binary decision diagrams (QOBDDs) and answers the question: How does the computational power of QOBDDs increase, if we allow repeated tests. Additionally it is described how to synthesize QOBDDs according to Boolean operations.

DOI
10.48550/arxiv.quant-ph/0507258

Related papers

Width Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams with Repeated Test

Kamil Ravilevich Khadiev, Rishat Ibrahimov

We consider quantum, nondterministic and probabilistic versions of known computational model Ordered Read-$k$-times Branching Programs or Ordered Binary Decision Diagrams with repeated test ($k$-QOBDD, $k$-NOBDD and $k$-POBDD). We show width hierarchy for complexity classes of Boolean function computed by these models and discuss relation between different variants of $k$-OBDD.

arXiv:1703.07891•Mar 23, 2017•2 citations

On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting

Farid Mansurovich Ablayev, Alexander Vasiliev

We develop quantum fingerprinting technique for constructing quantum branching pro-grams (QBPs), which are considered as circuits with an ability to use classical bits as control variables. We demonstrate our approach constructing optimal quantum ordered binary decision diagram (QOBDD) for MODm Boolean function. The construction of our technique also allows to extend the recent result of Ambainis and Nahimovs it is based on. In addition we show how our technique works for encoding quantum information for the equality problem in the simultaneous message passing model. 1

Electronic colloquium on computational complexity•Jan 1, 2008•10 citations

On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

Farid Mansurovich Ablayev, Airat Khasianov, Alexander Vasiliev

We consider the Hidden Subgroup, and Equality-related problems in the context of quantum Ordered Binary Decision Diagrams. For the decision versions of considered problems we show polynomial upper bounds in terms of quantum OBDD width. We apply a new modification of the fingerprinting technique and present the algorithms in circuit notation. Our algorithms require at most logarithmic number of qubits. 1

Electronic colloquium on computational complexity•Jan 1, 2008•11 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

On Computational Power of Quantum Read-Once Branching Programs

Farid Mansurovich Ablayev, Alexander Vasiliev

In this paper we review our current results concerning the computational power of quantum read-once branching programs. First of all, based on the circuit presentation of quantum branching programs and our variant of quantum fingerprinting technique, we show that any Boolean function with linear polynomial presentation can be computed by a quantum read-once branching program using a relatively small (usually logarithmic in the size of input) number of qubits. Then we show that the described class of Boolean functions is closed under the polynomial projections.

arXiv:1103.2809•Electronic Proceedings in Theoretical Computer Science•Mar 8, 2011•5 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.

arXiv:1405.7849•Lobachevskii Journal of Mathematics•Nov 1, 2016•40 citations
Quantum branching programs (quantum binary decision diagrams, respectively) are a convenient tool for examining quantum computations using only a logarithmic amount of space. Recently several types of restricted quantum branching programs have been considered, e. g. read--once quantum branching programs. This paper considers quantum ordered binary decision diagrams (QOBDDs) and answers the question: How does the computational power of QOBDDs increase, if we allow repeated tests. Additionally it is described how to synthesize QOBDDs according to Boolean operations.
We consider quantum, nondterministic and probabilistic versions of known computational model Ordered Read-kkk-times Branching Programs or Ordered Binary Decision Diagrams with repeated test (kkk-QOBDD, kkk-NOBDD and kkk-POBDD). We show width hierarchy for complexity classes of Boolean function computed by these models and discuss relation between different variants of kkk-OBDD.
We develop quantum fingerprinting technique for constructing quantum branching pro-grams (QBPs), which are considered as circuits with an ability to use classical bits as control variables. We demonstrate our approach constructing optimal quantum ordered binary decision diagram (QOBDD) for MODm Boolean function. The construction of our technique also allows to extend the recent result of Ambainis and Nahimovs it is based on. In addition we show how our technique works for encoding quantum information for the equality problem in the simultaneous message passing model. 1
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).
In this paper we review our current results concerning the computational power of quantum read-once branching programs. First of all, based on the circuit presentation of quantum branching programs and our variant of quantum fingerprinting technique, we show that any Boolean function with linear polynomial presentation can be computed by a quantum read-once branching program using a relatively small (usually logarithmic in the size of input) number of qubits. Then we show that the described class of Boolean functions is closed under the polynomial projections.
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.