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:1103.2809 · Electronic Proceedings in Theoretical Computer Science

On Computational Power of Quantum Read-Once Branching Programs

Farid Mansurovich Ablayev, Alexander Vasiliev

Published Mar 8, 2011• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4204/eptcs.52.1

Related papers

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

Algorithms for Quantum Branching Programs Based on Fingerprinting

Farid Mansurovich Ablayev, Alexander Vasiliev

In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as Equality, Palindrome, and Permutation Matrix Test. We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.

arXiv:0911.2317•Electronic Proceedings in Theoretical Computer Science•Nov 15, 2009•29 citations

On computational power of classical and quantum branching programs

Farid Mansurovich Ablayev

We present a classical stochastic simulation technique of quantum Branching programs. This technique allows to prove the following relations among complexity classes: PrQP-BP &subuline; PP-BP and BQP-BP &subuline; PP-BP. Here BPP-BP and PP-BP stands for the classes of functions computable with bounded error and unbounded error respectively by stochastic branching program of polynomial size. BQP-BP and PrQP-BP stands the classes of functions computable with bounded error and unbounded error respectively by quantum branching program of polynomial size. Second. We present two different types, of complexity lower bounds for quantum nonuniform automata (OBDDs). We call them "metric" and "entropic" lower bounds in according to proof technique used. We present explicit Boolean functions that show that these lower bounds are tight enough. We show that when considering "almost all Boolean functions" on n variables our entropic lower bounds gives exponential (2c(δ)(n-log n)) lower bound for the width of quantum OBDDs depending on the error δ allowed.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 24, 2006•1 citation

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

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)

Daniel Grier, Jackson Morris, Kewen Wu

$\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.

cs.CCCross-listedarXiv:2601.03243•Jan 7, 2026•0 citations

Quantum vs. Classical Read-Once Branching Programs

Martin Sauerhoff

A simple, explicit boolean function on 2n input bits is presented that is computable by errorfree quantum read-once branching programs of size O(n^3), while each classical randomized read-once branching program and each quantum OBDD for this function with bounded two-sided error requires size 2^{omega(n)}.

arXiv:quant-ph/0504198•Apr 26, 2005•4 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.
In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as Equality, Palindrome, and Permutation Matrix Test. We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.
We present a classical stochastic simulation technique of quantum Branching programs. This technique allows to prove the following relations among complexity classes: PrQP-BP &subuline; PP-BP and BQP-BP &subuline; PP-BP. Here BPP-BP and PP-BP stands for the classes of functions computable with bounded error and unbounded error respectively by stochastic branching program of polynomial size. BQP-BP and PrQP-BP stands the classes of functions computable with bounded error and unbounded error respectively by quantum branching program of polynomial size. Second. We present two different types, of complexity lower bounds for quantum nonuniform automata (OBDDs). We call them "metric" and "entropic" lower bounds in according to proof technique used. We present explicit Boolean functions that show that these lower bounds are tight enough. We show that when considering "almost all Boolean functions" on n variables our entropic lower bounds gives exponential (2c(δ)(n-log n)) lower bound for the width of quantum OBDDs depending on the error δ allowed.
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
QAC0\mathsf{QAC}^0QAC0 Contains TC0\mathsf{TC}^0TC0 (with Many Copies of the Input)
QAC0\mathsf{QAC}^0QAC0 is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical AC0\mathsf{AC}^0AC0 lower bounds to QAC0\mathsf{QAC}^0QAC0 have failed. We give one possible explanation of this: QAC0\mathsf{QAC}^0QAC0 circuits are significantly more powerful than their classical counterparts. We show the unconditional separation QAC0⊄AC0[p]\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]QAC0⊂AC0[p] for decision problems, which also resolves for the first time whether AC0\mathsf{AC}^0AC0 could be more powerful than QAC0\mathsf{QAC}^0QAC0. Moreover, we prove that QAC0\mathsf{QAC}^0QAC0 circuits can compute a wide range of Boolean functions if given multiple copies of the input: TC0⊆QAC0∘NC0\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0TC0⊆QAC0∘NC0. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.