We consider Generalized Equality, the Hidden Subgroup, and 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 ... more >>>

We develop quantum fingerprinting technique for constructing quantum branching programs (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 $MOD_m$ and $DMULT_n$ Boolean functions. The construction of our technique also ... more >>>

We prove upper and lower bounds on the power of quantum and stochastic branching programs of bounded width. We show any NC^1 language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless \NC^1=\ACC. This ... more >>>

A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an ordinary branching program with the following restrictions: (i) along every consistent path at most $k$ variables are tested more than once, (ii) for each node $v$ on all paths from the source to $v$ the same set $X(v)\subseteq X$ of variables is tested, ... more >>>

The superposition (or composition) problem is a problem of representation of a function $f$ by a superposition of "simpler" (in a different meanings) set $\Omega$ of functions. In terms of circuits theory this means a possibility of computing $f$ by a finite circuit with 1 fan-out gates $\Omega$ of functions. ... more >>>

We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the size of any randomized ordered read-once branching program computing integer multiplication. Our proof depends on proving a new lower bound on Yao's randomized one-way communication complexity of certain boolean functions. It generalizes to some other common models of randomized branching ... more >>>

We introduce a model of a {\em randomized branching program} in a natural way similar to the definition of a randomized circuit. We exhibit an explicit boolean function $f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that: 1) $f_{n}$ can be computed by a polynomial size randomized ordered read-once branching program with a ... more >>>

In the manuscript F. Ablayev and M. Karpinski, On the power of randomized branching programs (generalization of ICALP'96 paper results for the case of pure boolean function, available at http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions $f_n$ in $n$ variables such that: 1) $f_{n}$ can be computed by polynomial size ... more >>>

We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit function $f_{n}$ for which we prove that: 1) $f_{n}$ can be computed by polynomial size randomized read-once ordered branching program with a small one-sided error; ... more >>>