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.00242 · Lecture notes in computer science

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

Kamil Ravilevich Khadiev, Aliya Khadieva

Published Jan 1, 2017• 30 citations
arXivHTMLPDF
DOI
10.1007/978-3-319-58747-9_16

Related papers

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

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 +1 more

arXiv:1703.05015•Lecture notes in computer science•Dec 21, 2017•22 citations

Quantum Differential Evolution Algorithm for Variable Ordering Problem of Binary Decision Diagram

Abdesslem Layeb, Djamel Eddine Saïdouni

Communications in computer and information science•Jan 1, 2008•2 citations

Reordering Decision Diagrams for Quantum Computing Is Harder Than You Might Think

Stefan Hillmich, Lukas Burgholzer, Florian Stögmüller +1 more

Lecture notes in computer science•Jan 1, 2022•4 citations

Binary-decision-diagram-based decomposition of Boolean functions into reversible logic elements

Jia Lee, Ya-Hui Ye, Xin Huang +1 more

Theoretical Computer Science•Jan 20, 2020•8 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
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.