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/0302022 · Lecture notes in computer science

On Computational Power of Quantum Branching Programs

Farid Mansurovich Ablayev, Aida Gainutdinova, Marek Karpiński

Published Jan 1, 2001• 41 citations
arXivHTMLPDF
DOI
10.1007/3-540-44669-9_8

Related papers

On the computational power of probabilistic and quantum branching program

Farid Mansurovich Ablayev, Aida Gainutdinova, Marek Karpiński +2 more

Information and Computation•Sep 27, 2005•48 citations

Quantum branching programs and space-bounded nonuniform quantum complexity

Martin Sauerhoff, Detlef Sieling

arXiv:quant-ph/0403164•Theoretical Computer Science•Feb 8, 2005•41 citations

Quantum and Stochastic Branching Programs of Bounded Width

Farid Mansurovich Ablayev, Cristopher Moore, Christopher John Pollett

arXiv:quant-ph/0201139•Lecture notes in computer science•Jan 1, 2002•13 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

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

Comparative power of quantum and classical computation models

Farid Mansurovich Ablayev

In the talk we present results on comparitve power of classical and quantum computational models. We focus on two well known in Computer Science models: finite automata which is known as uniform computational model and branching programs which is known as nonuniform computational model.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jun 1, 2005•0 citations
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.
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.