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/0504198

Quantum vs. Classical Read-Once Branching Programs

Martin Sauerhoff

Published Apr 26, 2005• 4 citations
arXivHTMLPDF

Abstract

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)}.
DOI
10.4230/dagsemproc.06111.15

Related papers

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 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

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

Classical Simulation Complexity of Quantum Branching Programs

Farid Mansurovich Ablayev

We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width $w$ that computes a function with error $delta$ we present a classical deterministic branching program of the same length and width at most $(1+2/(1-2delta))^{2w}$ that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and unbounded error quantum branching programs. Our result is that it is possible stochastically-classically simulate quantum branching programs with the same length and almost the same width, but we lost bounded error acceptance property.

Language and Automata Theory and Applications•Jan 1, 2008•0 citations

Very narrow quantum OBDDs and width hierarchies for classical OBDDs

Farid Mansurovich Ablayev, Aida Gainutdinova, Kamil Ravilevich Khadiev +1 more

We present several results on comparative complexity for different variants of OBDD models. - We present some results on comparative complexity of classical and quantum OBDDs. We consider a partial function depending on 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 2k+1. - We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient than classical one. In particular, an explicit function is presented which is computed by a quantum nondeterministic OBDD with constant width but any classical nondeterministic OBDD for this function needs non-constant width. - We also present new hierarchies on widths of deterministic and non-deterministic OBDDs. We focus both on small and large widths.

arXiv:1405.7849•May 30, 2014•0 citations

On relative complexity of quantum and classical branching programs

Aida Gainutdinova

Abstract We give a definition of a quantum branching program. A well-known Boolean function MOD

Discrete Mathematics and Applications•Jan 1, 2002•3 citations
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.
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.
We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width www that computes a function with error deltadeltadelta we present a classical deterministic branching program of the same length and width at most (1+2/(1−2delta))2w(1+2/(1-2delta))^{2w}(1+2/(1−2delta))2w that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and unbounded error quantum branching programs. Our result is that it is possible stochastically-classically simulate quantum branching programs with the same length and almost the same width, but we lost bounded error acceptance property.
We present several results on comparative complexity for different variants of OBDD models. - We present some results on comparative complexity of classical and quantum OBDDs. We consider a partial function depending on 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 2k+1. - We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient than classical one. In particular, an explicit function is presented which is computed by a quantum nondeterministic OBDD with constant width but any classical nondeterministic OBDD for this function needs non-constant width. - We also present new hierarchies on widths of deterministic and non-deterministic OBDDs. We focus both on small and large widths.