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

Information and Computation

On the computational power of probabilistic and quantum branching program

Farid Mansurovich Ablayev, Aida Gainutdinova, Marek Karpiński, Cristopher Moore, Christopher John Pollett

Published Sep 27, 2005• 48 citations
Publisher
DOI
10.1016/j.ic.2005.04.003

Related papers

On Computational Power of Quantum Branching Programs

Farid Mansurovich Ablayev, Aida Gainutdinova, Marek Karpiński

arXiv:quant-ph/0302022•Lecture notes in computer science•Jan 1, 2001•41 citations

Ordered Quantum Branching Programs Are More Powerful than Ordered Probabilistic Branching Programs under a Bounded-Width Restriction

Masaki Nakanishi, Kiyoharu Hamaguchi, Toshinobu Kashiwabara

Lecture notes in computer science•Jan 1, 2000•35 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 simulating the quantum and classical branching programs

Aida Gainutdinova

The complexity classes defined on the basis of branching programs are considered. Some basic relations are established between the complexity classes defined by the probabilistic and quantum branching programs (measure-once, as well as measure-many), computing with bounded or unbounded error. To prove these relations, we developed a method of “linear simulation” of a quantum branching program and a method of “quantum simulation” of a probabilistic branching program.

Journal of Applied and Industrial Mathematics•Mar 1, 2007•1 citation

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 and stochastic branching programs of bounded width: (Track A)

Farid Mansurovich Ablayev, Cristopher Moore, Christopher John Pollett

•Jan 1, 2002•1 citation
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.