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• 3 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 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

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

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

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