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:1703.05015 · Lecture notes in computer science

Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test

Farid Mansurovich Ablayev, Andris Ambainis, Kamil Ravilevich Khadiev, Aliya Khadieva

Published Dec 21, 2017• 22 citations
arXivHTMLPDF
DOI
10.1007/978-3-319-73117-9_14

Related papers

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams

Kamil Ravilevich Khadiev, Aliya Khadieva

arXiv:1703.00242•Lecture notes in computer science•Jan 1, 2017•30 citations

Exponential separation between quantum and classical ordered binary decision diagrams, reordering method and hierarchies

Kamil Ravilevich Khadiev, Aliya Khadieva, Alexander Knop

arXiv:2204.10671•Natural Computing•Jul 26, 2022•10 citations

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

Quantum Ordered Binary Decision Diagrams with Repeated Tests

Matthias Homeister, Stephan Waack

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.

arXiv:quant-ph/0507258•Jul 27, 2005•3 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

Quantum weakly nondeterministic communication complexity

François Le Gall

arXiv:quant-ph/0511025•Theoretical Computer Science•Dec 22, 2012•0 citations
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.
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.
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.