Quantum and Stochastic Branching Programs of Bounded Width
Farid Ablayev\thanks{Dept. of Theoretical Cybernetics
Cristopher Moore\thanks{ Computer Science Department
In this paper we show that one qubit polynomial time computations are at least as powerful as $\NC^1$ circuits. More precisely, we define syntactic models for quantum and stochastic branching programs of bounded width and prove upper and lower bounds on their power. 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 separates width-$2$ quantum programs from width-$2$ doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in $\NC^1$.
quant-ph0201139.tex
% Dear Cris and Chris. I am very sorry for so long delay with this
% paper. I've been at the IAS from September 19 till October 19. 
%  Razborov suggested to
% define our version  (we called ``perfect'') of program ---
% ``syntactic'' program. It seems his suggestion is good. I use it
% in the paper. I added the notion of consistent and nonconsitent
% states of program. This notion was suggested by IAS seminar
% members. Wigderson and  Yao was there also. I addeded definition 6
% of syntactic program. But may be it is not perfect.

% I used Cris's presentation of the proof of theorem 4. I did not
% anything in the proof of theorem 3.

%I did not add syntactic complexity classes and did not change the
%corollary 2.    

%Now I am at the MPI, Bonn. I discussed our improvements with
%Marek. Might be the  possible option with proceeding with our paper
%is the following: we first improve our ECCC, and quant-ph version of the
%paper (3 authors) and simultanecoly present the extended (5 authors)
%paper to the 
%journal. What do you think on this? 


\documentclass[11pt,a4paper]{article}

\usepackage{amsfonts,amsmath,latexsym}


\title{Quantum and Stochastic Branching Programs of Bounded Width} 

%\title{On the Computational Power of Classical and Quantum
%  Branching Programs} 

\author{ Farid Ablayev\thanks{Dept. of Theoretical Cybernetics, Kazan
    State University.  {\tt ablayev@ksu.ru }; work done in part while
    visiting Institute of Advanced Study and Max-Plnak Institute for
    Mathematics, supported by RFBR grant 03-01-00769} 
\and 
Cristopher Moore\thanks{ Computer Science Department, University of
  New Mexico, Albuquerque and the Santa Fe Institute {\tt
    moore@cs.unm.edu}; supported by NSF grant EIA-0218563} 
\and
Christopher Pollett\thanks{ Dept. of Computer Science San Jose State
  University.  {\tt pollett@cs.sjsu.edu}} }



\date{}

\usepackage{amssymb}
\usepackage{amsfonts,amsmath,latexsym}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%  theorem declarations
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newcommand{\comment}[1]{}
\newcommand{\Accept}{{\rm Accept}}

%\newenvironment{proof}%
%{\medskip
%\noindent {\it Proof.}
%}{$\Box$}


\newcommand{\EQN}[1]{\begin{eqnarray*}#1\end{eqnarray*}}
\newcommand{\mat}{\left(\! \begin{array}{cc}}
\newcommand{\rix}{\end{array} \!\right)}
\newcommand{\ket}[1]{{|{#1} \rangle}}
\newcommand{\bra}[1]{{\langle {#1}|}}
\newcommand{\braket}[2]{{\langle {#1} \mid {#2} \rangle}}
\newcommand{\ignore}[1]{}


\newcommand{\eps}{\epsilon}
% CM: changed mathbb to Bbb
\newcommand{\Z}{{\Bbb Z}}
\newcommand{\R}{{\Bbb R}}
\newcommand{\N}{{\Bbb N}}

\newcommand{\acc}{{\mathrm{acc}}}
\newcommand{\rej}{{\mathrm{rej}}}

% CM: I changed mathit to mathrm for qbps
\newcommand{\nc}{\mathrm{NC}}
\newcommand{\NC}{\mathrm{NC}}
\newcommand{\ACC}{\mathrm{ACC}}
\newcommand{\qnc}{\mathrm{QNC}}
\newcommand{\QNC}{\mathrm{QNC}}
\newcommand{\bp}{\mathrm{BP}}
\newcommand{\sbp}{\mathrm{SBP}}
\newcommand{\qbp}{\mathrm{QBP}}
\newcommand{\BP}{\mathrm{BP}}
\newcommand{\QBP}{\mathrm{QBP}}
\newcommand{\SBP}{\mathrm{SBP}}
\newcommand{\BQBP}{\mathrm{BQBP}}
\newcommand{\EQBP}{\mathrm{EQBP}}
\newcommand{\BSBP}{\mathrm{BSBP}}
\newcommand{\BWBP}{\mathrm{BWBP}}
\newcommand{\QBWBP}{\mathrm{QBWBP}}
\newcommand{\BMBWBP}{\mathrm{BMBWBP}}
\newcommand{\BQBWBP}{\mathrm{BQBWBP}}
\newcommand{\obdd}{\mathrm{OBDD}}
\newcommand{\OBDD}{\mathrm{OBDD}}

\newcommand{\AND}{\mathit{AND}}
\newcommand{\MULT}{\mathit{MULT}}
\newcommand{\MOD}{\mathit{MOD}}

\newcommand{\nats}{{\bf N}}
\newcommand{\ints}{{\bf Z}}
\newcommand{\rats}{{\bf Q}}
\newcommand{\reals}{{\bf R}}
\newcommand{\complexes}{{\bf C}}
\newcommand{\quaternions}{{\bf H}}
\newcommand{\algebraics}{{\overline{\bf Q}}}




%%%%%%%%%% my declarations



\newtheorem{mydef}{Definition}
\newcommand{\bedef}{\begin{mydef}}
\newcommand{\eedef}{\end{mydef}}

\newtheorem{theorem}{Theorem}
\newcommand{\bethm}{\begin{theorem}}
\newcommand{\eethm}{\end{theorem}}

\newtheorem{conjecture}{Conjecture}

\newtheorem{cors}{Corollary}
\newcommand{\becor}{\begin{cors}}
\newcommand{\eecor}{\end{cors}}

\newtheorem{lemm}{Lemma}
\newcommand{\belem}{\begin{lemm}}
\newcommand{\eelem}{\end{lemm}}

\newtheorem{rft}{Theorem}[section]
\newcommand{\bethmsec}{\begin{rft}}
\newcommand{\eethmsec}{\end{rft}}

\newtheorem{fpr}{Property}
\newcommand{\beprop}{\begin{fpr}}
\newcommand{\eeprop}{\end{fpr}}

%\newcommand{\qbp}{\mathrm{QBP}}
\newcommand{\qbps}{\mathrm{QBPs}}
%\newcommand{\bp}{\mathrm{BP}}
\newcommand{\bps}{\mathrm{BPs}}

\newcommand{\ra}{\rangle}
\newcommand{\qs}[1]{\mbox{${|\!\!~#1~\!\!\rangle}$}}
%\newcommand{\ket}[1]{\mbox{${|\!\!~#1~\!\!\rangle}$}}

\newcommand{\cn}[1]{\mbox{$\mathbb{\!\!~#1~\!\!}$}}
\newcommand{\ceiling}[1]{\mbox{$\lceil\!\!~#1~\!\!\rceil$}}
\newcommand{\floor}[1]{\mbox{$\lfloor\!\!~#1~\!\!\rfloor$}}

\newcommand{\Endproof}{\hfill$\Box$\\}

\newcommand{\SU}{{\mathit SU}}
\newcommand{\SO}{{\mathit SO}}



\begin{document}


\maketitle
\thispagestyle{empty}

\begin{abstract}
  

In this paper we show that one qubit polynomial time computations are
 at least as powerful as $\NC^1$ circuits. More precisely,
we define syntactic models  for quantum and stochastic branching
programs of bounded width and prove upper and lower bounds on their
power.  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 separates width-$2$ quantum programs from
width-$2$ doubly stochastic programs as we show the latter cannot
compute the middle bit of multiplication.  Finally, we show that
bounded-width quantum and stochastic programs can be simulated by
classical programs of larger but bounded width, and thus are in
$\NC^1$.

\end{abstract}


%\newpage


\section{Preliminaries}


Interest in quantum computation has steadily increased since Shor's
discovery of a polynomial time quantum algorithm for
factoring~\cite{shor97}.  A number of models of quantum computation
have been considered, including quantum versions of Turing machines,
simple automata, circuits, and decision trees. The goal of much of
this research has been to understand in what ways quantum algorithms
do and do not offer a speed-up over the classical case, and to
understand what classical techniques for proving upper and lower
complexity bounds transfer to the quantum setting.

Branching programs have proven useful in a variety of domains, such as
hardware verification, model checking, and other CAD applications; see
for example the book by Wegener~\cite{we00}.
%Remind that polynomial size branching
% programs as powerful as $\log$ space Turing machines.
In addition, branching programs are a convenient model for
nonuniform computation with varying restrictions.
% CM: what computational model?
Even oblivious branching programs of constant width --- the 
non-uniform equivalent of finite-state automata --- are surprisingly
powerful.  Indeed, Barrington~\cite{bar85} showed that branching
programs of width 5 are already as powerful as circuits of logarithmic
depth.

Moreover, branching programs are a very natural model for comparing
the power of quantum computation with classical computation, both
deterministic and randomized.  Recently, several models of quantum
branching programs have been proposed
\cite{amp02,agk01,asv00,nahaka00}.

In this paper we define and consider syntactic models of stochastic
and quantum branching programs. For this syntactic model we present
several results for quantum branching programs of bounded width
\cite{amp02}.  We show that width-$2$ quantum programs are more
powerful than width-$2$ doubly stochastic programs, and are as strong
as deterministic branching programs of width $5$.  Specifically, we
show that polynomial-length, width-$2$ quantum branching programs can
recognize any language in $\NC^1$ exactly.  Note that such programs
are equivalent to a nonuniform automaton whose only storage device is
a single qubit!

On the other hand, we show that polynomial-length, width-$2$ doubly
stochastic programs cannot compute the middle bit of the
multiplication function.  In the classical case, Yao~\cite{yao83}
showed that width-$2$ deterministic programs require superpolynomial
length to compute the majority function.

Next, we show that bounded-error (syntactic) quantum and stochastic
programs can be simulated by deterministic programs of the same length
and larger, but still bounded, width. Therefore the class of languages
recognized by these programs coincides with (nonuniform) $\NC^1$.
This also implies that, for bounded-width quantum programs, exact
acceptance is just as strong as acceptance with bounded error.


To give some flavour of what our syntactic model is, consider the usual
computation of a branching program. When we query a variable we do one
of two actions depending on its values. If we query the variable again
we expect to see the same value. An inconsistent state is one that is
reached by querying a variable more than once and using a different
value each time. Our syntactic models allow for the inclusion of
inconsistent final states when the final bounded error acceptance
property is calculated.  This enables us to show that final consistent
states of stochastic and quantum programs recognizing languages with
bounded error recognition have a specific metric property: sets of
accepting and rejecting states are isolated from each other. We define
syntactic programs as programs which satisfy the property that the
set of all (consistent as well as inconsistent) final states form a
partition into two sets isolated from each other.

We call this property a syntactic property in analogy with the
notion of syntactic classical read-$k$-times programs. The definition of
classical syntactic read-$k$-times branching programs \cite{brs93}
includes all their nonconsistent paths in the general read-$k$-times
variables testing property.
  

We use the techniques of our result to show that polynomial-length
width-$2$ stochastic programs that accept with probability $1/2+\eps$
cannot compute the majority function if $\eps > 1/4$. In addition, we
show that polynomial-length stochastic programs with width $2$ and
$\eps > 1/8$, width $3$ and $\eps > 1/3$, or width $4$ and $\eps >
3/8$ can only recognize languages in $\ACC$.




\section{Branching Programs}

We begin by discussing the classical model of branching programs and
then generalize it to the quantum setting. A good source of
information on branching programs is Wegener's book~\cite{we00}, and
for an introduction to quantum computation see Nielsen and
Chuang~\cite{nc00}.

\bedef
A {\em branching program} is a finite directed acyclic graph which
accepts some subset of $\{0,1\}^n$.  Each node (except for the sink
nodes) is labeled with an integer $1 \le i \le n$ and has two outgoing
arrows labeled $0$ and $1$.  This pair of edges corresponds to
querying the $i$'th bit $x_i$ of the input, and making a transition
along one outgoing edge or the other depending on the value of $x_i$.
There is a single source node corresponding to the start state, and a
subset $\Accept$ of the sink nodes corresponding to accepting states.
An input $x$ is {\em accepted} if and only if it induces a chain of
transitions leading to a node in $\Accept$, and the set of such inputs
is the language accepted by the program.  A branching program is {\em
oblivious} if the nodes can be partitioned into levels $V_1, \ldots,
V_\ell$ and a level $V_{\ell+1}$ such that the nodes in $V_{\ell+1}$
are the sink nodes, nodes in each level $V_j$ with $j \le \ell$ have
outgoing edges only to nodes in the next level $V_{j+1}$, and all
nodes in a given level $V_j$ query the same bit $x_{i_j}$ of the
input.  Such a program is said to have {\em length $\ell$}, and {\em
width $k$} if each level has at most $k$ nodes.
\eedef


Oblivious branching programs have an elegant algebraic definition.
Recall that a {\em monoid} is a set with an associative binary
operation $\cdot$ and an identity $1$ such that $1 \cdot a = a \cdot 1
= a$ for all $a$.

\bedef 
Let $M$ be a monoid and $S \subset M$ an accepting set.  Let
$x_i$, $1 \le i \le n$ be a set of Boolean variables.  A {\em
  branching program over $M$ of length $\ell$} is a string of $\ell$
{\em instructions}; the $j$'th instruction is a triple $(i_j,a_j,b_j)
\in \{1,\ldots,n\} \times M \times M$, which we interpret as $a_j$ if
$x_{i_j}=0$ and $b_j$ if $x_{i_j}=1$.  Given an input $x$, the {\em
  yield} $Y(x)$ of the program is the product in $M$ of all its
instructions.  We say that the input $x$ is {\em accepted} if $Y(x)
\in S$, and the set of such inputs is the language recognized by the
program.  
\eedef

Such programs are often called {\em non-uniform deterministic finite
  automata} (NUDFAs).  A computation in a deterministic finite
automaton can be thought of as taking a product in its syntactic
monoid; in a NUDFA we generalize this by allowing the same variable to
be queried many times, and allowing ``true'' and ``false'' to be
mapped into a different pair of monoid elements in each query.

A common monoid is $T_k$, the set of functions from a set of $k$
objects into itself.  Then the program makes transitions among $k$
states, and we can equivalently define oblivious, width-$k$ branching
programs by choosing an initial state and a set of accepting final
states, where the $k$ states correspond to the $k$ vertices (according
to an arbitrary ordering) in each level $V_j$.

\bedef\label{oblivious}
An {\em oblivious width-$k$ branching program} is a branching program
over $T_k$, where the accepting set $S \subset T_k$ consists of those
elements of $T_k$ that map an initial state $s \in \{1,\ldots,k\}$ to
a final state $t \in A$ for some subset $A \subset \{1,\ldots,k\}$.
\eedef




\section{Bounded Width Branching Programs}

We define language classes recognized by (non-uniform) families of
bounded-width branching programs whose length increases polynomially
with $n$:

% CM: here and elsewhere I changed "functions" to "languages";
% one recognizes a language, and calculates a function.

\bedef
$k$-$\BWBP$ is the class of languages recognized by polynomial-length
branching programs of width $k$, and $\BWBP = \cup_k \,k$-$\BWBP$.
\eedef

Recall that a {\em group} is a monoid where every element has an
inverse, and a group is {\em Abelian} if $ab = ba$ for all $a,b$.  A
subgroup $H \subseteq G$ is {\em normal} if the left and right cosets
coincide, $aH = Ha$ for all $a \in G$.  A group is {\em simple} if it
has no normal subgroups other than itself and $\{1\}$.

Barrington~\cite{bar85} studied branching programs over the
permutation group on $k$ objects $S_k \subset T_k$; such programs are
called {\em permutation programs}.  He showed that polynomial-length
programs over $S_5$, and therefore width-$5$ branching programs, can
recognize any language in $\NC^1$, the class of languages recognizable
by Boolean circuits of polynomial width and logarithmic depth~\cite{papa}.  
The version of Barrington's result that we will use is:
\begin{theorem}[\cite{bar85,mtlbd00}]
\label{thm:barrington}
Let $G$ be a non-Abelian simple group, and let $a \ne 1$ be any
non-identity element.  Then any language $L$ in $\NC^1$ can be
recognized by a family of polynomial-length branching programs over
$G$ such that their yield is $Y(x) = a$ if $x \in L$ and $1$
otherwise.
\end{theorem}
Since the smallest non-Abelian simple group is $A_5 \subset S_5$, the
group of even permutations of $5$ objects, and since we can choose 
a permutation $a$
that maps some initial state $s$ to some other final state $t$, width $5$
suffices.  Conversely, note that we can model a width-$k$ branching
program as a Boolean product of $\ell$ transition matrices of dimension
$k$, and a simple divide-and-conquer algorithm allows us to calculate
this product in $O(\log l)$ depth.  Thus $\BWBP \subset \NC^1$, so we
have
\[ \mbox{5-$\BWBP$} = \BWBP = \NC^1 \enspace . \]

In the stochastic and quantum cases, the state  of the
program will be described by a $k$-dimensional vector $\mu$.  The
$j$'th step of the program will query a variable $x_{i_j}$, and apply
a transition matrix $M_j(x_{i_j})$.
%
%AF:  added the notion of consitent state:
%
\bedef 
We call state (state vector) $\mu$ of branching program a
consistent state if there exists an input $x$ that induces a chain of
transitions leading to the state $\mu$ from the initial state  $\mu_0$.
Otherwise, we call the $\mu$ an inconsistent state.  
\eedef
 %
If $x=x_1,\dots,x_n$ is the input of a program of length $\ell$, then
the final consistent state of the program will be

\[ \ket{\mu(x)}  =  \prod_{j=\ell}^1 M_j(x_{i_j}) \ket{\mu_0} \enspace . \]
 %
(This product is in reverse order since we think of each step of the
program as a left multiplication of the state by $M_j$.)  In the
deterministic case, state $\mu$ is a Boolean vector with exactly one 1
and the $M_j$ correspond to elements of $T_k$ and so have exactly one
$1$ in each column.  For branching programs over groups this is true
of the rows as well, in which case the $M_j$ are permutation matrices.
We can generalize this by letting $\mu$ be a probability distribution,
and letting the $M_j$ be {\em stochastic} matrices, i.e.,\ matrices
with non-negative entries where each column sums to $1$, or {\em
  doubly stochastic} where both the rows and columns sum to 1.  Recall
that, by Birkhoff's Theorem~\cite{lw01}, doubly stochastic matrices
are convex combinations of permutation matrices~\cite{???}.

In the deterministic and stochastic cases for sink state vector $\mu\in
V_{\ell+1}$, we define 
\begin{equation}
\label{eq:pstoch} 
 \Pr(\mu) = \sum_{i\in \Accept} \braket{i}{\mu} 
 = \left\| \Pi_\Accept \mu \right\|_1 \enspace 
\end{equation}
and we define the probability of acceptance as $Pr(x) = Pr(\mu(x))$.
Here $\ket{i}$ is the basis vector with support on the state $i$, 
and $\Pi_\Accept$ is a projection operator on the 
{\em accepting subspace} ${\rm span}\{\ket{i}: i\in \Accept\}$.

For {\em quantum} branching programs, $\mu$ is a complex state vector
with $\| \mu \|_2 = 1$, and the $M_j$ are complex-valued unitary matrices.
 %
%unitary}, i.e., $M_j^{-1} = M_j^\dagger$ where $\dagger$ denotes the
%Hermitian conjugate.
%CM: I don't think we need to define unitarity for QIC readers...
 %
Then we define $Pr(\mu)$ for sink state  vector $\mu\in V_{\ell+1}$ as 
\begin{equation}
\label{eq:pquant}
 \Pr(\mu)= \sum_{i\in \Accept} |\braket{i}{\mu}|^2 
 = \left\| \Pi_\Accept \mu \right\|_2^2 
\end{equation}
and the probability of acceptance as $Pr(x)=Pr(\mu(x))$
% CM: Again, I changed the following to assume somewhat more knowledge of QM
which is the probability that, that if we measure $\mu(x)$, we will
observe it in the accepting subspace.  Note that this is a
``measure-once'' model analogous to the model of quantum finite
automata in~\cite{mc97}, in which the system evolves unitarily except
for a single measurement at the end.  We could also allow multiple
measurements during the computation, by representing ${\cal A}=\{\mu :
Pr(\mu) >1/2 \}$ the state as a density matrix and making the $M_j$
superoperators; we do not consider this here.

%AF: I aded the definition of unbounded error bp to outline that
%syntactic model  can be differ from general model  only for
%bounded error case. 

We can define recognition in several ways for the quantum case.  We
say that a language $L$ is accepted {\em with unbounded error} if
$\Pr(x) > 1/2$ if $x \in L$ and $\Pr(x) \le 1/2$ if $x \notin L$.  We
say that a language $L$ is accepted {\em with bounded error} if there
is some $\eps > 0$ such that $\Pr(x) \ge 1/2+\eps$ if $x \in L$ and
$\Pr(x) \le 1/2-\eps$ if $x \notin L$. 
% AF: may be it is sence to otline that exact acceptance is a
% particular case of bounded error acceptance (this is essesntial for
% syntactic branching programs): 
For the case $\eps=1/2$ we say $L$ is accepted {\em exactly}. That is,
$\Pr(x) = 1$ if $x \in L$ and $\Pr(x) = 0$ if $x \notin L$ as in the
deterministic case.



\section{Syntactic Variants of Stochastic and Quantum Programs}

For unbounded and bounded error stochastic and quantum branching
programs we define two subsets $\cal A$ and ${\cal R}$ of the set of
sink state vectors as follows:
 %
For an unbounded error programs, we define

\[ {\cal A}=\{\mu\in V_{\ell+1} : Pr(\mu) >1/2 \} \qquad \mbox{and}
\qquad  {\cal
  R}=\{\mu\in V_{\ell+1} : Pr(\mu)
\le 1/2 \}; \]
  %
for bounded error programs,we define 

\[ {\cal A}=\{\mu\in V_{\ell+1} : Pr(\mu) \ge 1/2+\eps \} \quad  \mbox{and}
\quad  {\cal
  R}=\{\mu\in V_{\ell+1} : Pr(\mu)
\le 1/2-\eps \} \]
  %
We call $\cal A$ the accepting set of
state vectors and call $\cal R$ the rejecting set of
state vectors. 

 

\bedef 
We call a stochastic or a quantum branching program a syntactic 
program if its accepting and rejecting set of state vectors
form a partition of the set of sink state vectors for the program. That is
$V_{\ell+1}= {\cal A}\cup {\cal R}$.  
\eedef


Observe that deterministic, unbounded error stochastic
and quantum branching programs are syntactic programs. But in the
case of bounded error branching programs it might happen that
$V_{\ell+1}\not= {\cal A}\cup {\cal R}$.  That is, it might happen
that a inconsistent final state vector $\mu\in V_{\ell+1}$ has the
property that $1/2-\eps < Pr(\mu)< 1/2+\eps$.

We denote by $B\cdot$   
%(where we will drop the $\cdot$' when clear) 
the language classes recognized by standard (nonsyntactic) programs with
 bounded error  and denote by $E\cdot$  those
recognized exactly.  The notations $\SBP$ and $\QBP$ stand for
stochastic and quantum branching programs, respectively. We denote the
classes of languages recognized by width-$k$ stochastic and quantum
programs of polynomial length as $k$-$\BSBP$, $k$-$\BQBP$, and
$k$-$\EQBP$.  Note that we remove ``BW'' to avoid acronym overload. We
write $\BSBP$ for $\cup_k k$-$\BSBP$ and define $\BQBP$ and $\EQBP$
similarly.  Clearly we have
\[ \mbox{$\BWBP$} \subseteq \mbox{$\EQBP$} 
   \subseteq \mbox{$\BQBP$} 
\]
and
\[ \mbox{$\BWBP$} \subseteq \mbox{$\BSBP$} \]
but in principle $k$-$\BSBP$ could be incomparable with $k$-$\EQBP$ or
$k$-$\BQBP$.




\section{Width-$2$ Doubly Stochastic and Quantum Programs}

In this section we show that width-$2$ syntactic quantum programs
with exact acceptance contain $\nc^1$, and also that this class of
programs is stronger than width-$2$ syntactic doubly stochastic
programs.

\belem
\label{ordering}
Any width-$2$ doubly stochastic program on $n$ variables is equivalent
to one which queries each variable once and in the order
$x_1, x_2, \ldots, x_n$.
\eelem
{\em Proof.}
Any $2 \times 2$ stochastic matrix can be written as $\mat p & 1-p \\
1-p & p \rix$ for some $p \in [0,1]$. It is easy to verify that
matrices of this form commute. Hence, if we have a product of such
matrices $\prod^1_{j=n} M_j(x_{i_j})$ we can rewrite it so that we first
take the product of all the matrices that depend on $x_1$, then those
that depend on $x_2$, and so on. To finish the proof we note that
products of doubly stochastic matrices are again doubly stochastic, so
we can use a single doubly stochastic matrix for the product of all
the matrices that depend on a given $x_i$.
\Endproof

The above lemma shows we can convert any width-$2$ doubly stochastic
program into one which is read-once and with a fixed variable
ordering. i.e., a randomized ordered binary decision diagram (OBDD).
Hence in the case of width-$2$ syntactic and nonsyntactic models
of programs are equivalent. 

First we note that stochastic programs are stronger than
permutation programs for width $2$.  It is easy to see that any
program over $\Z_2$ simply yields the parity of some subset of the
$x_i$.  The $\AND_n$ function, which accepts only the input with
$x_i=1$ for all $i$, is not of this form, and so this function cannot
be recognized by a width-2 permutation program.  However, it can
easily be recognized by a  stochastic program $P$ with
bounded error which queries each variable once as follows: for $i < n$
it maps $x_i=1$ and $0$ to the
identity $\mat 1 & 0 \\ 0 & 1 \rix$ and the matrix $\mat 1/2 & 1/2 \\
1/2 & 1/2 \rix$ respectively, and for $x_n$ it maps $1$ and $0$ to
$\mat 3/4 & 0\\ 1/4 & 1 \rix$ and $\mat 3/8 & 3/8 \\ 5/8 & 5/8 \rix$
respectively. Taking the first state to be both the initial and final
state, $P$ accepts with probability $3/4$ if $x_i = 1$ for all $i$ and
$3/8$ otherwise.  Note that except for one matrix this is in fact a
doubly stochastic program; if we had treated the variable $x_n$ in the
same fashion as the other variables we would have gotten a syntactic
doubly stochastic program accepting $\AND_n$ with one-sided error.

Despite being stronger than their permutation counterparts, the next
% CM: this sentence is kind of weak, since the previous paragraph
% doesn't show that doubly-stochastic programs are stronger
% than permutation programs except with one-sided error
% (which we haven't defined)
%CP deleted that
result shows width-$2$ doubly stochastic branching programs are not that
strong. Let $\MULT^n_k$ be the Boolean function which computes the
$k$'th bit of the product of two $n$-bit integers. Define $\MULT^n$ to
be $\MULT^n_{n-1}$, i.e.,  the middle bit of the product. We will
argue that any width-$2$ stochastic program that calculates this function 
(i.e., that recognizes the set of inputs for which $\MULT^n = 1$) 
% CM: I added this line
requires at least exponential width.


In \cite{ak98} Ablayev and Karpinski investigated randomized OBDDs, 
i.e., those which accept with bounded error. 
% CM: I changed the above sentence.  Is this ok?
% FA: Yes, its ok. 
\begin{theorem}[\cite{ak98}] 
Any randomized $\OBDD$ that correctly computes $\MULT^n$ has width at least
% CM: this was BP-OBDD, which hasn't been defined.  Is this correct?
% FA: OBDDs are ordered read-once branching programs and hence have
% length at most $n$. their main complexity measure is width. I
% changed the writing "length" to "width" in the  theorem and
% the cor. below according to this.   
$2^{\Omega(n/{\log n})}$.
\end{theorem}
So by Lemma~\ref{ordering} we have immediately:
\becor
$\MULT^n$ can not be computed by a width-$2$ doubly stochastic program.
\eecor

While width-$2$ doubly stochastic programs are quite weak, 
% CM: again, our argumentation here comes off as somewhat weak
% given that we haven't proved that singly stochastic width-2 programs
%are weak. 
% 
% FA: YESSSS!. the problem $2-\BSBP=NC^1$ or $2-\BSBP\subset NC^1$  is open!
%
the next result shows that width-$2$ {\em quantum} programs are surprisingly 
strong.  Note that a width-$2$ quantum program has a state space
equivalent to a single qubit, such as a single spin-$1/2$ particle.
% \cite{nc00}.

\begin{theorem}
\label{thm:width2}
$\NC^1$ is contained in syntactic $2$-$\EQBP$.
\end{theorem}

\noindent
{\em Proof.}  
Recall that the smallest non-Abelian simple group $A_5$ is isomorphic 
to the set of rotations of the icosahedron.  Therefore, the group $\SO(3)$
of rotations of $\R^3$, i.e., the $3 \times 3$ orthogonal matrices
with determinant $1$, contains a subgroup isomorphic to $A_5$.

There is a well-known 2-to-1 mapping from $\SU(2)$, the group of $2
\times 2$ unitary matrices with determinant $1$, to $\SO(3)$.
Consider a qubit $a\ket{0} + b\ket{1}$ with $|a|^2+|b|^2 = 1$; we can
make $a$ real by multiplying by an overall phase.  The {\em Bloch
sphere} representation (see e.g.~\cite{nc00}) views this state as the
point on the unit sphere with latitude $\theta$ and longitude $\phi$ ,
i.e., $(\cos\phi \cos\theta, \sin\phi \cos\theta, \sin\theta)$, where
$a \cos \theta/2$ and $b = e^{i \phi} \sin \theta/2$.

Given this representation, an element of $\SU(2)$ is equivalent to some
rotation of the unit sphere.  Recall the {\em Pauli matrices}
\[ \sigma_x = \mat 0 & 1 \\ 1 & 0 \rix, \quad
   \sigma_y = \mat 0 & i \\ -i & 0 \rix, \quad
   \sigma_z = \mat 1 & 0 \\ 0 & -1 \rix
\]
Then we can rotate an angle $\alpha$ around the $x$, $y$ or $z$ axes
with the following operators:
\begin{eqnarray*}
R_x(\alpha) = e^{i (\alpha/2) \sigma_x} & = & 
\mat \cos \alpha/2 & -i \sin \alpha/2 \\ 
  -i \sin \alpha/2 & \cos \alpha/2 \rix \\
R_y(\alpha) = e^{i (\alpha/2) \sigma_y} & = &
\mat \cos \alpha/2 & -\sin \alpha/2 \\ 
     \sin \alpha/2 & \cos \alpha/2 \rix, 
\mbox{ and} \\
R_z(\alpha) = e^{i (\alpha/2) \sigma_z} & = &
\mat e^{-i \alpha/2} & 0 \\ 
     0 & e^{i \alpha/2} \rix \enspace . 
\end{eqnarray*} 
This makes $\SU(2)$ a {\em double cover} of $\SO(3)$, where each element
of $\SO(3)$ corresponds to two elements $\pm U$ in $\SU(2)$.  (Note that
angles get halved by this mapping.)  Therefore, $\SU(2)$ has a subgroup
which is a double cover of $A_5$.  One way to generate this subgroup
is with $2\pi/5$ rotations $a$ and $b$ around two adjacent vertices of an
icosahedron.  Since two such vertices are an angle $\tan^{-1} 2$
apart, if one lies on the $z$ axis and the other lies in the
$x$-$z$ plane, we have
\begin{eqnarray*}
a & = & R_z(2\pi/5)  =  \mat e^{i \pi/5} & 0 \\ 0 & e^{-i \pi / 5} \rix \\
b & = & R_y(\tan^{-1} 2) \cdot a \cdot R_y(-\tan^{-1} 2)\\
  & = & \frac{1}{\sqrt{5}} 
  \mat e^{i \pi/5} \tau + e^{-i \pi/5} \tau^{-1} &
     - 2 i \sin \pi/5 \\
     - 2 i \sin \pi/5 &
       e^{-i \pi/5} \tau + e^{i \pi/5} \tau^{-1} \rix
\end{eqnarray*}
where $\tau = (1+\sqrt{5})/2$ is the golden ratio.  Now consider the
group element $c = a \cdot b \cdot a$; this rotates the icosahedron by
$\pi$ around the midpoint of the edge connecting these two vertices.
In $\SU(2)$, this maps each of the eigenvectors of $\sigma_y$ to the
other times an overall phase.  These eigenvectors are
\[ e_+ = \frac{\ket{0} + i \ket{1}}{\sqrt{2}},
   \quad e_- = \frac{\ket{0} - i \ket{1}}{\sqrt{2}} \]
so we have
\[ | \langle e_+ | \pm c | e_- \rangle |^2 = 1 \]
while, since they are orthogonal, 
\[ | \langle e_+ | 1 | e_- \rangle |^2 = 0 \enspace . \]

Now, Theorem~\ref{thm:barrington} tells us that for any language $L$ in
$\NC^1$ we can construct a polynomial-length program over $A_5$ that
yields the element equivalent to $c$ if the input is in the language 
and $1$ otherwise.  Using the embedding of $A_5$ in $\SO(3)$ and then 
lifting to $\SU(2)$ gives a program which yields $\pm c$ or $1$.  
If we take the initial state to be $\mu_0 = e_-$ and the 
accepting subspace to be that spanned by 
$e_+$, this program accepts $L$ exactly.
\Endproof


\section{Deterministic Simulations of Syntactic Stochastic and
  Quantum Branching Programs}

In this section we give general results on simulating syntactic
stochastic and quantum programs with deterministic ones.
Specifically, Theorem~\ref{l-ub} shows that syntactic stochastic and
quantum programs that accept with bounded error can be simulated by
deterministic programs of the same length and larger (but still
bounded) width.  Below we use this to place upper bounds on the
computational power of stochastic programs with various widths and
error thresholds.

\begin{theorem} \label{l-ub}
Let $P$ be a syntactic stochastic or quantum branching program 
of width $k$ and length $\ell$ that recognizes a language $L$
with probability $1/2+\eps$.  Then, there exists a 
deterministic branching program $P'$ of width $k'$ and length $\ell$ 
that recognizes $L$, where
\begin{equation} 
\label{eq:widthstoch}
%k' \leq \left(1+ \frac{1}{\eps}\right)^k 
k' \leq \left(\frac{1}{\eps}\right)^{k-1} 
\end{equation}
if $P$ is  stochastic, and 
\begin{equation}
\label{eq:widthquant}
k' \leq \left(\frac{2}{\eps}\right)^{2k} 
\end{equation}
if $P$ is quantum.
\end{theorem}

\noindent {\em Proof.}  Our proof is a simple generalization of
arguments of Rabin~\cite{rabin} and Kondacs and Watrous~\cite{kw97} 
to the non-uniform case.  
For each step of the program, we define an equivalence relation 
on state vectors, where two state vectors are equivalent if they 
lead to the same outcome (acceptance or rejection).  
Since $P$ recognizes $L$ with bounded error, inequivalent 
states must be bounded away from each other, and 
since the state space is compact the number of
equivalence classes is finite.  These equivalence classes then
become the states of our deterministic program $P'$.  

%In the remainder of the proof, $\| \cdot \|$ will denote 
%$\| \cdot \|_1$ if $P$ is stochastic, and $\| \cdot \|_2^2$
%if $P$ is quantum. 

First, we construct a much larger deterministic branching program
$P''$ whose states at each level $j$ consist of the state vectors
(consistent and nonconsitent) $\mu$ that $P$ can reach after $j$ steps
(computational or noncomputational).
%given all possible inputs.  
%That is, for all $1 \le m \le \ell+1$,  
%\[ V''_m = \left\{ \left.
% \prod_{j=m-1}^1 M_j(x_{i_j}) \ket{\mu_0} \right|
% (x_i) \in \{0,1\}^n 
%\right\} \enspace . \]
$V''_1$ consists of 
the initial state $\mu_0$, and for all $1 \le j \le \ell$ each 
$\mu \in V''_j$ has two outgoing edges to
$M_j(0) \mu, M_j(1) \mu \in V''_{j+1}$.
The syntactic property provides partition the final states $\mu
\in V''_{\ell+1}$ into accepting and rejecting subsets $\cal A$ and
$\cal R$ according to equations~\eqref{eq:pstoch}
and~\eqref{eq:pquant}.

In the stochastic case, $\mu \in {\cal A}$ (resp.\ $\mu \in {\cal R}$) 
if $\| \Pi_\Accept \mu \|_1 \ge 1/2+\eps$
(resp.\ $\| \Pi_\Accept \mu \|_1 \le 1/2-\eps$), and 
similarly in the quantum case except that $\|\cdot\|_1$ 
is replaced with $\|\cdot\|_2^2$.
Clearly if ${\cal A}$ is the accepting subset of $V''_{\ell+1}$, 
then $P''$ recognizes $L$ deterministically.

Now we inductively define an equivalence relation $\equiv_j$
on $V''_j$ for each level $j$.  First, we let 
${\cal A}$ and ${\cal R}$ be the equivalence classes of $\equiv_{\ell+1}$
(note that  $V''_{\ell+1} = {\cal A} \,\cup\, {\cal R}$
since $P$ recognizes $L$ with bounded error).
Then, for each $1 \le j \le \ell$, define 
\[ \mu \equiv_j \mu' \;\Leftrightarrow\; M_j(0) \mu \equiv_{j+1} M_j(0) \mu'
 \,\mbox{ and }\, M_j(1) \mu \equiv_{j+1} M_j(1) \mu' 
\enspace . \]
We now define $P'$ as the branching program whose states 
$V'_j$ for each level $j$ are the equivalence classes of $\equiv_j$ 
and whose accepting subset is the singleton $\{ {\cal A} \}$.
Clearly $P'$ is well-defined and recognizes $L$ deterministically; 
it just remains to show that the number of equivalence classes 
for each $j$ is bounded.

First we show that two inequivalent state vectors in $V''_j$ must
be far apart, using the following standard argument~\cite{rabin,kw97}.
\belem\label{theta} Suppose $\mu, \mu' \in V''_j$
and $\mu \not \equiv_j \mu'$.  Then 
\[ \|\mu-\mu'\|_1 \geq 4 \eps \]
if $P$ is stochastic, and
\[ \|\mu-\mu'\|_2 \geq 2 \eps \]
if $P$ is quantum.
\eelem

{\noindent \em Proof.}  Since stochastic and unitary matrices both
preserve or decrease the appropriate norm, it suffices to show this
for the last step.  Therefore, suppose that $j=\ell+1$, $\mu \in {\cal
  A}$ and $\mu' \in {\cal R}$.  We can decompose both vectors into
their components inside the accepting subspace and transverse to it,
writing $\mu = \mu_A + \mu_R$ where $\mu_A = \Pi_\Accept \mu$ and
$\mu_R = (1-\Pi_\Accept) \mu$ and similarly for $\mu'$.  In the
stochastic case, $\|\mu_A\|_1 \ge 1/2+\eps$ and $\|\mu'_A\|_1 \le
1/2-\eps$, and so

\begin{eqnarray*}
\|\mu- \mu'\|_1 & = & \| \mu_A - \mu'_A \|_1 + \| \mu_R - \mu'_R \|_1 \\
% & \ge & \| \mu_A \|_1 - \| \mu'_A \|_1 + \| \mu'_R \|_1 - \| \mu_R \|_1 \\
& \geq & 2 \left[ \left(1/2+\eps\right) - \left(1/2-\eps\right) \right] \\
& = & 4 \eps \enspace . 
\end{eqnarray*}
In the quantum case, $\|\mu_A\|_2 \ge \sqrt{1/2+\eps}$ and 
$\|\mu'_A\|_2 \le \sqrt{1/2-\eps}$, so
\begin{eqnarray*}
\|\mu-\mu'\|_2^2 & = & \|\mu_A-\mu'_A\|_2^2 + \|\mu_R-\mu'_R\|_2^2 \\
& \ge & 2 \left[ \sqrt{1/2+\eps} - \sqrt{1/2-\eps} \right]^2 \\
& = & 2 \left( 1 - \sqrt{1-4\eps^2} \right) \\
& \ge & 4\eps^2
\end{eqnarray*}
so $\|\mu-\mu'\|_2 \ge 2\eps$.
\Endproof

It follows that the width $k'$ of $P'$ is at most the largest number
of balls of radius $2 \eps$ or $\eps$ (in the stochastic and quantum
case respectively) one can fit inside the state space. 
%yielding the bounds~\eqref{eq:widthstoch} and~\eqref{eq:widthquant}.  
In the stochastic case, the state space is a $(k-1)$-dimensional
simplex.  Its $L_1$-diameter is $2$, so each ball of radius $2\eps$
covers a fraction at least $(1/\eps)^{k-1}$ of its volume,
yielding~\eqref{eq:widthstoch}.  This bound is crude in that it
assumes that the center of each ball is at a corner of the simplex;
balls whose center are in the interior of the simplex cover up to
$2^{k-1}$ times as much volume.  In particular, if $k=2$ then $k' \le
1+1/(2 \eps)$.

In the quantum case, the state space is isomorphic to the surface of
the $2k$-dimensional sphere of radius $1$.  The crude bound 
of~\eqref{eq:widthquant} comes from noticing that this sphere, 
and the balls of radius $\eps$ whose centers lie on its surface, 
are all contained in a $2k$-dimensional ball of radius $2$. 
% CM: I opted for the crudest bound here, since all we care about 
% is that it's a constant.
\Endproof

Theorem~\ref{l-ub} shows that bounded-error syntactic stochastic and
quantum programs of constant width can be simulated by deterministic
programs of constant (albeit exponentially larger) width, and are
therefore contained in $\NC^1$.  Conversely, we showed in
Theorem~\ref{thm:width2} that $\NC^1$ is contained in width-$2$
syntactic quantum programs.  Therefore, the following classes all
coincide with $\NC^1$:
  %
\becor
For syntactic programs,
\[ \mbox{$2$-$\EQBP$} = \mbox{$2$-$\BQBP$} = \EQBP = \BQBP = \BSBP = \BWBP 
= \NC^1 \enspace .
\]
\eecor
  %
Of all the program classes discussed in this paper, the only ones {\em
  not} included in this collapse are stochastic programs of width less
than $5$.  Theorem 4 allows us to place upper bounds on their
computational abilities if their error margins are sufficiently large.
For instance, since Yao~\cite{yao83} showed that width-2 deterministic
programs require superpolynomial length to compute the majority
function, we have 
\becor For the syntactic case, width-$2$ stochastic branching programs of
polynomial length cannot recognize the majority function with
probability $1/2+\eps$ if $\eps > 1/4$.  \eecor

Similarly, recall that $\ACC = \cup_p \ACC[p]$ where 
$\ACC[p]$ is the class of languages 
recognizable by constant-depth circuits with AND, OR, and 
mod-$p$ counting gates of arbitrary fan-in.  It is known that 
$\ACC[p] \subsetneq \NC^1$ for prime $p$~\cite{razborov,smolensky}, 
and strongly believed, but not known, that $\ACC \subsetneq \NC^1$.
Since its is known~\cite{bt88} that deterministic programs of width 
less than $5$ recognize languages in $\ACC[6]$, we have
% CM: added ACC[6] (I checked this with Denis Therien)
\becor
Suppose $L$ is recognized with probability $1/2+\eps$ by a
width-$k$ stochastic syntactic branching program of polynomial length.  
If $k=2$ and $\eps > 1/8$, or $k=3$ and $\eps > 1/3$, 
or $k=4$ and $\eps > 3/8$, then $L \in \ACC$.
\eecor

\noindent
{\em Proof.}  For each $k$ we consider the problem of how small 
$\eps$ has to be to fit $5$ points into the $(k-1)$-dimensional simplex
with an $L_1$ distance $4\eps$ between them.  While these values of $\eps$ are
smaller that those given by~\eqref{eq:widthstoch}, they follow easily from 
assuming without loss of generality that $k$ of the points lie on the 
simplex's corners.
\Endproof

However, we conjecture that stochasticity doesn't greatly increase the
power of bounded-width branching programs, in the following sense:
\begin{conjecture}
If $L$ is recognized with bounded error by a stochastic branching program
of width less than $5$, then $L \in \ACC$.
\end{conjecture}


\bigskip {\bf Acknowledgments.}  We grateful to Sasha Razborov for
numeric suggestions on the results presentations. We thank Denis
Th\'erien for helpful discussions on $\ACC$ and Sasha Shen for
productive discussions on syntactic model.





\bibliographystyle{plain}

\begin{thebibliography}{1}


\bibitem{amp02} F. Ablayev, C. Moore, and C. Pollett,
Quantum and stochastic branching programs of bounded width. 
{\em Proc.\ 29th Intl.\ Colloquium on Automata, Languages and Programming} 
% Lecture Notes in Computer Science, Springer-Verlag}, 
343--354, 2002.
%Preliminary version appeared as 
%{\em Electronic Colloquium on Computational Complexity} 
%TR 02-013, 2002, available at {\tt http://www.eccc.uni-trier.de/eccc/}

\bibitem{agk01} F. Ablayev, A. Gainutdinova, and M. Karpinski, 
On the computational power of quantum branching programs.
\newblock {\em Proc.\ FCT 2001}, Lecture Notes in Computer Science 
2138: 59--70, 2001.

\bibitem{ak98} F. Ablayev and M. Karpinski, 
A lower bound for integer multiplication on randomized 
read-once branching programs.
{\em Electronic Colloquium on Computational Complexity} TR 98-011, 
1998. {\tt http://www.eccc.uni-trier.de/eccc}

%\bibitem{al84} P. Alexandrov, 
%{\em Introduction to set theory and general topology.}
%Berlin, 1984.

%\bibitem{amfr98} A. Ambainis and R. Freivalds, 
%1-way quantum finite automata: strengths, weaknesses and generalization. 
%{\em Proc.\  39th IEEE Conf.\ on Foundation of Computer Science}  
%332--342, 1998.
% See also {\tt quant-ph/9802062}.

%\bibitem{af98} A. Ambainis and R. Freivalds. 
%\newblock 1-way quantum finite automata: strengths, weakness, and
%generalizations.
%\newblock {\em Proc.\ 39th IEEE Symp.\ on Foundations of
%Computer Science (FOCS)}, 332--342, 1998.

% \bibitem{barenco} A. Barenco, C. Bennett, R. Cleve, D.P. DiVincenzo,
% N. Margolus, P. Shor, T. Sleator, J.A. Smolin and H. Weinfurter.
% \newblock Elementary gates for quantum computation.
% \newblock quant-ph/9503016, {\em Phys. Rev. A} 52: 3457-3467, 1995.

\bibitem{asv00} A. Ambainis, L. Schulman, and U. Vazirani, 
Computing with highly mixed states.
{\em Proc.\ 32nd ACM Symp.\ on Theory of Computing} 697--704, 2000.

\bibitem{bar85}
D.A.~Barrington, 
Bounded-width polynomial branching programs recognize exactly 
those languages in {$NC^1$}.
{\em Journal of Computer and System Sciences} 38(1): 150--164, 
1989.

\bibitem{bt88}
D.A.~Barrington and D.~Therien, 
Finite Monoids and the Fine Structure of {$NC^1$}. 
{\em Journal of the ACM} 35(4): 941--952, 1988.

\bibitem{brs93} A. Borodin, A. Razborov, and R. Smolensky, On lower
bounds for read-$k$-times branching programs, {\em Computational
Complexity}, 3, (1993), 1-18.


\bibitem{kesn60} J.G. Kemeny and J.L. Snell, 
{\em Finite Markov Chains.} 
Van Nostrand, 1960.

\bibitem{kw97}
A.~Kondacs and J.~Watrous, 
On the power of quantum finite automata. 
{\em Proc.\  38th IEEE Conf.\ on Foundations of Computer Science} 
66--75, 1997.

\bibitem{mc97}
C.~Moore and J.P.~Crutchfield, 
Quantum automata and quantum grammars.
{\em Theoretical Computer Science} 237: 275--306, 2000.

% \bibitem{mn00}
% C.~Moore and M.~Nilsson.
% \newblock Parallel quantum computation and quantum codes. 
% \newblock To appear SIAM J. Computing.

\bibitem{mtlbd00}
C.~Moore, D.~Th\'erien, F.~Lemieux, J.~Berman, and A.~Drisko.
\newblock Circuits and Expressions with Non-Associative Gates.
\newblock {\em Journal of Computer and System Sciences} 60:
368--394, 2000.

\bibitem{nahaka00}  M. Nakanishi, K. Hamaguchi, and T. Kashiwabara, 
Ordered quantum branching programs are more powerful than ordered
probabilistic branching programs under a bounded-width restriction.
{\em Proc.\ 6th Intl.\ Conf.\ on
Computing and Combinatorics (COCOON)} Lecture Notes in Computer
Science 1858: 467--476, 2000.

\bibitem{nc00}
M.A.~Nielson and I.L.~Chuang, 
{\em Quantum Computation and Quantum Information.} 
Cambridge University Press, 2000.

\bibitem{papa} C. Papadimitriou, 
{\em Computational Complexity.}  Addison-Wesley, 1994.

\bibitem{rabin}
M. Rabin,
Probabilistic automata.
{\em Information and Control} 6: 230--245, 1963. 

\bibitem{razborov} A.A. Razborov,
Lower bounds for the size of circuits of bounded depth with basis $\{\&, \oplus\}$.
{\em Math. Notes Acad. Sci. USSR} {\bf 41(4)} 333--338, 1987.

% \bibitem{rot94}
% Joseph J. Rotman
% \newblock {\em An Introduction to the Theory of Groups}, $4$th ed. 
% \newblock Springer-Verlag. 1994.

\bibitem{shor97}
P. Shor, 
Polynomial-time algorithms for prime factorization and discrete
logarithms on a quantum computer.
{\em SIAM Journal on Computing} 26(5): 1484--1509, 1997.

\bibitem{smolensky} R. Smolensky,
Algebraic methods in the theory of lower bounds for Boolean circuit
complexity. {\em Proc. 19th ACM Symposium on the Theory of Computing}
77--82, 1987.


 \bibitem{lw01}
 J. H. van Lint and R. M. Wilson.
 \newblock {\em A Course in Combinatorics}, $2$nd ed. 
 \newblock Cambridge. 2001.

\bibitem{we00}
Ingo~Wegener, 
{\em Branching Programs and Binary Decision Diagrams.} 
SIAM Monographs on Discrete Mathematics and Applications, 2000.

\bibitem{yao83}
A.C.~Yao,
Lower Bounds by Probabilistic Arguments. 
{\em Proc.\  24th IEEE Conf.\ on Foundations of Computer Science} 
420--428, 1983.


\end{thebibliography}


\end{document}


${\rm span}\{\ket{i}: i\in \Accept\}$.  
In the quantum
case it is allowed to perform measurements with respect to an arbitrary
subspace spanned by a system of orthonormal vectors.  Below we will
also use the projection of $\mu(x)$ onto other subspaces to extract
$\Pr(x)$.  

\paragraph{Proof of Theorem \ref{thm:sim} } \label{pr-lb}
Denote by $(w,\ell)$-$P$ 
an oblivious branching program of width $w$ and length $\ell$.  
The idea is that given a
stochastic (quantum) $(w,\ell)$-$P$ that recognizes a language $L$ with
margin $\eps$, we construct a deterministic $(k,\ell)$-$P'$
that recognizes the same language. Here
$k \leq \left( 1+1/\eps\right)^{w}$
when $P$ is stochastic, and 
$k \leq \left( 1+1/\eps\right)^{2w}$
when $P$ is quantum.  

We will simulate a stochastic or quantum $(w,\ell)$-$P$ with an
length-$\ell$ deterministic oblivious branching program $P'$ of
exponential (but bounded) width as follows.  Each node of $P'$ 
is represented as a vector $\mu$ in the state space of $P$. The level $V_1$
contains the initial node $\mu_0$.  Each node $\mu$ on level $i$,
$i\in\{1,\dots,\ell\}$ has two outgoing edges labelled $x_{j_i}=0$ and
$x_{j_i}=1$ where $x_{j_i}$ is the variable tested on the level $V_i$.
Edge $x_{j_i}=1$ is directed from a parent $\mu$ on a level $V_i$ to a
child $\mu'$ on the level $V_{i+1}$ if $P$ in step $i$ of its
computation is in general state $\mu$, tests $x_{j_i}=1$, and
transforms its general state in step $i+1$ to $\mu'$.  Similarly, edge
$x_{j_i}=0$ is directed from parent $\mu$ on a level $V_i$ to child
$\mu''$ on level $V_{i+1}$ if $P$ in step $i$ of its computation is in
general state $\mu$, tests $x_{j_i}=0$, and transforms its general
state in step $i+1$ to $\mu''$.



>From the above we have the following property:

\beprop\label{dp=p}
The deterministic branching program $DP$ recognizes the same language
$L$ as $P$.
\eeprop


In what follows, we use different norms depending on whether $P$
is stochastic or quantum.  Specifically, we define
 $\| \mu \|=\| \mu \|_1=\sum_{i=1}^w |\mu_i|$ if $P$ is stochastic, 
and $\| \mu \|=\| \mu \|_2 = \sqrt{\sum_{i=1}^w |z_i|^2}$ if $P$ is quantum. 

Since $L$ is ($1/2+\eps$)-recognized, we have that $\sum_{i\in Accept}
\mu_i\geq 1/2+\eps$  and   $\sum_{i\in Accept}
\mu'_i\leq 1/2-\eps$. Thus, it follows that   
 \[\|\mu- \mu'\|_1 \geq 1/2 +\eps -
(1/2-\eps)=2\eps. \] 

{\noindent \em Proof.}  Let $DP$ be the oblivious length-$\ell$
deterministic $\bp$ for $P$ constructed following the description
before Property \ref{dp=p}. The oblivious property of $DP$ implies
that for all nodes $\mu$ on level $V_i$ of $DP$, the same variable
$x_{j_i}$ is tested and the same linear transition is applied. This
transformation is $M_{x_{j_i}}(1)$ if $x_{j_i}=1$ and $M_{x_{j_i}}(0)$
if $x_{j_i}=0$, where $M_{x_{j_i}}(a)$ is a stochastic matrix when $P$
is stochastic $\bp$ and where $M_{x_{j_i}}(a)$ is a unitary when $P$
is quantum $\bp$.

It is known (and it can be easily verified) that the transformation
determined by a stochastic matrix $M$ does not increase distances.
That is, if $\alpha'=M\alpha$ and $\beta'=M\beta$ then $\|\alpha'-
\beta'\|\leq \|\alpha -\beta\|$.  Further, any unitary matrix $M$
preserves distances. That is, $\|\alpha'-\beta' \|=\|\alpha -
\beta\|$. Notice we are implicitly using that the norm is $\|\cdot
\|=\|\cdot \|_1$ for the stochastic case and $\|\cdot \|=\|\cdot \|_2$
for the quantum case.



For a $\equiv_\theta^i$ equivalence class $C\in{\cal C}_\theta^i$ and
a matrix $M$, let $MC=\{ \mu' : \mu'=M\mu, \mu\in C\}$.
>From the non-increasing distance property of the linear transformations
we are considering, it holds in both the stochastic and quantum case 
that for $i\in\{1,\dots,l\}$ and for arbitrary $C\in{\cal C}_\theta^i$ 
there exists $C'\in {\cal C}_\theta^{i+1}$ such that $MC\subseteq C'$.

Let $k=\max_{1\le i\le \ell+1}\{|{\cal C}_\theta^i|\}$.  We define a
deterministic $(k,l)$-$P$ named $DP'$ based on $DP$ as follows: The
levels $V_i$ of $DP'$ are the $\equiv_\theta^i$ equivalence classes
$C\in {\cal C}_\theta^i$.  The level $V_1$ contains the initial node
$C\in{\cal C}_\theta^1$, where $C=\{\mu_0\}$ and $\mu_0$ is the
initial node of $DP$.  As in $DP$, the test variable on the level
$V_i$ is $x_{j_i}$. In $DP'$, we have an edge labelled $x_{j_i}=a$
that goes from $C\in {\cal C}_\theta^i$ to node $C'\in {\cal
C}_\theta^{i+1}$ if and only if $M_{x_{j_i}}(a)C\subseteq C'$.

The set $V_{\ell+1}$ is partitioned into two subsets $Accept$ and
$Reject$ as follows: For a node $C\in V_{\ell+1}$ we put $C\in{Accept}$
if for $\mu\in C$ it holds that $\mu\in{\cal A}$ and we put
$C\in{Reject}$ if for $\mu\in C$ it holds that $\mu\in{\cal R}$.  It
follows from Lemma~\ref{theta} that $Accept\cap Reject=\emptyset$.

>From the above, it follows that $DP'$ recognizes the same language
as $DP$.  From Lemma~\ref{l-ub1} it follows that $ k \leq \left(1+
1/{\eps}\right)^{w}$ when $P$ is stochastic $\bp$, and $k \leq
\left(1+ 1/{\eps}\right)^{2w}$ when $P$ is quantum $\bp$.  \Endproof

In the stochastic case, $\mu \in {\cal A}$ (resp.\ $\mu \in {\cal R}$) 
if $\| \Pi_\Accept \mu \|_1 \ge 1/2+\eps$
(resp.\ $\| \Pi_\Accept \mu \|_1 \le 1/2-\eps$), 
and in the quantum case
$\mu \in {\cal A}$ (resp.\ $\mu \in {\cal R}$) 
if $\| \Pi_\Accept \mu \|_2^2 \ge 1/2+\eps$
(resp.\ $\| \Pi_\Accept \mu \|_2^2 \le 1/2-\eps$).  

Let $\| \cdot \|$ denote the 1-norm or the 2-norm if 
$P$ is stochastic or quantum respectively.  

%Let $\mu=(\mu_1\dots,\mu_w) $ and $\mu'=(\mu'_1\dots,\mu'_w) $. Then

%= \sum_{i=1}^w |\mu_i-\mu'_i| 
%\geq \!\!\sum_{i \in \Accept}\!\!\! \left| \mu_i-\mu'_i \right| 
%\geq \left| {\sum_{i \in \Accept}\!\!\! \mu_i} - \!\!\!\! {\sum_{i \in \Accept} \!\!\!\mu'_i} \right| 


Now consider the case where $P$ is quantum.
Let $\mu=(z_1,\dots, z_d)$ and $\mu'=(z'_1,\dots z'_d)$.
Since $L$ is ($1/2+\eps$)-recognized,
\EQN{
 2\eps \le \sum_{i \in Accept}{(|z_i|^2-|z'_i|^2)} &=&
\sum_{i \in Accept}{(|z_i|-|z'_i|)(|z_i| + |z'_i|)}\\
&\le& \sum_{i \in Accept}{(|z_i-z'_i|)(|z_i| + |z'_i|)}
}
and similarly 
\EQN{
 2\eps \le \sum_{i \in Reject}{(|z'_i|^2-|z_i|^2)} &=&
\sum_{i \in Reject}{(|z'_i|-|z_i|)(|z_i| + |z'_i|)}\\
&\le& \sum_{i \in Reject}{(|z_i-z'_i|)(|z_i| + |z'_i|)}.
}
This gives
\[ 4\eps \le \sum_{i=1}^w{(|z_i-z'_i|)(|z_i| + |z'_i|)}. \]
>From the above, using H\"{o}lder's Inequality:
 $\sum_{i=1}^d a_i b_i \le
\sqrt{\sum_{i=1}^d a_i^2} \sqrt{\sum_{i=1}^d b_i^2}$,
and the triangle inequality for the norm, we get that
\[4\eps \le \|\mu-\mu'\|_2\|\, |\mu|+|\mu'|\, \|_2
\le \|\mu-\mu'\|_2(\|\mu\|_2+\|\mu'\|_2)=2\|\mu-\mu'\|_2. \]





Let $\theta=2\eps $. For each level $V_i$, $1\le i \le \ell+1$, of $DP$,
we define an equivalence relation $\equiv_\theta^i$ on the set $V_i$
as follows: For $\mu,\mu'\in V_i$ we write $\mu\equiv_\theta^i\mu'$ if
and only if there exists a sequence $\mu_1, \dots, \mu_t$ of nodes
from $V_i$ such that $\mu=\mu_1$, $\mu'=\mu_t$ and for all
$j\in\{1,\dots,t-1\}$ it holds that $\|\mu_j-\mu_{j+1}\|<\theta$.
Denote by ${\cal C}_\theta^i$ the set of equivalence classes of
$\equiv_\theta^i$.

\belem\label{l-ub1} 
For  $i\in \{1,\dots, \ell+1\}$, the following inequalities hold: 
 \[|{\cal C}_\theta^i| \le \left(1+
\frac{2}{\theta}\right)^{w} \]
 for stochastic $P$ and 
 \[|{\cal C}_\theta^i| \le \left(1+ \frac{2}{\theta}\right)^{2w}\]
 for quantum $P$.
 \eelem

{\noindent \em Proof.} For each $\equiv_\theta^i$ equivalence class
$C\in {\cal C}_\theta^i$ select one point $\mu\in C$ and consider
spheres of radius $\theta/2$ centered at these $\mu$. Any two spheres
in this collection of spheres will be non-intersecting. Further, all
these $|{\cal C}_\theta^i|$ spheres are in a large sphere of radius
$1+\theta/2$ centered at $(0,0,\dots,0)$. The volume of a sphere of a
radius $r$ in ${\cal H}_w$ is $cr^w$ when ${\cal H}_w$ is a real space
and is $cr^{2w}$ when ${\cal H}_w$ is a complex space (in the complex
space ${\cal H}_w$ each complex point is a 2-dimensional point). The
constant $c$ depends on the metric of ${\cal H}_w$. Now for the
stochastic and for the quantum case respectively, we have that

 \[ |{\cal C}_\theta^i| \leq \frac{c\left(1+\theta/2\right)^{w}}{
c\left(\theta/2\right) ^{w}}
= \left(1+ \frac{2}{\theta}\right)^{w},
  \quad
|{\cal C}_\theta^i| \leq \frac{c\left(1+\theta/2\right)^{2w}}{
c\left(\theta/2\right)^{2w}}
= \left(1+ \frac{2}{\theta}\right)^{2w}. 
  \]



Now consider the case where $P$ is quantum.
Let $\mu=(z_1,\dots, z_d)$ and $\mu'=(z'_1,\dots z'_d)$.
Since $L$ is ($1/2+\eps$)-recognized,
\EQN{
 2\eps \le \sum_{i \in Accept}{(|z_i|^2-|z'_i|^2)} &=&
\sum_{i \in Accept}{(|z_i|-|z'_i|)(|z_i| + |z'_i|)}\\
&\le& \sum_{i \in Accept}{(|z_i-z'_i|)(|z_i| + |z'_i|)}
}
and similarly 
\EQN{
 2\eps \le \sum_{i \in Reject}{(|z'_i|^2-|z_i|^2)} &=&
\sum_{i \in Reject}{(|z'_i|-|z_i|)(|z_i| + |z'_i|)}\\
&\le& \sum_{i \in Reject}{(|z_i-z'_i|)(|z_i| + |z'_i|)}.
}
This gives
\[ 4\eps \le \sum_{i=1}^w{(|z_i-z'_i|)(|z_i| + |z'_i|)}. \]
>From the above, using H\"{o}lder's Inequality:
 $\sum_{i=1}^d a_i b_i \le
\sqrt{\sum_{i=1}^d a_i^2} \sqrt{\sum_{i=1}^d b_i^2}$,
and the triangle inequality for the norm, we get that
\[4\eps \le \|\mu-\mu'\|_2\|\, |\mu|+|\mu'|\, \|_2
\le \|\mu-\mu'\|_2(\|\mu\|_2+\|\mu'\|_2)=2\|\mu-\mu'\|_2. \]






\begin{theorem}
\label{thm:sim}
$2$-$\SBP$ and $2$-$\QBP$ are contained in  $\NC^1$. 
\end{theorem}

Now Theorem~\ref{thm:sim} follows
immediately from Lemma~\ref{l-ub} and the fact that $\BWBP = \NC^1$.
\Endproof

\item Unlike Definition~\ref{oblivious}, we do not restrict the width of
  the branching program to be constant. 
\end{enumerate} 

$\Bigl( 2 \pi \, l(\sigma)k/p_n \Bigr) \in
[\pi/4+2\pi j, 3\pi/4 + 2\pi j]$ iff $\Bigl( 2 \pi \, (l(\sigma)k
\bmod{p_n})/p_n\Bigr)\in [\pi/4, 3\pi/4 ]$. 






%FA: I put the preliminary part with read-once program and the section
%on read-once programs here. 


\section{Preliminaries}

Finally, we investigate the properties of read-once quantum branching
programs, which were defined in~\cite{agk01}.  We show that, just as
in the classical deterministic case, ordered read-once permutation
branching programs of exponential width (and hence $\qbps$) can
recognize arbitrary languages.  Next we exhibit a symmetric Boolean
function which is computable by a read-once $\qbp$ with $O(\log n)$
width, but which requires $\Omega(n)$ width for deterministic $\bps$,
and for randomized classical $\bps$ with a certain restriction on
their transitions.
%which requires a width
%$\Omega(n)$ on any deterministic read-once $\bp$ and (classical)
%randomized read-once $\bp$ with permanent transitions on each level.
Finally, we present a general lower bound on the width of read-once 
$\qbps$, and show that our $O(\log n)$ upper bound for this symmetric 
function is almost tight.




\section{Read-once Branching Programs (OBDDs)}

In this section we investigate the computational power of 
{\em read-once} branching programs, i.e., those in which
each variable $x_i$ is queried only once during a computation. 
% CM: It might be worth mentioning that the order in which
% the variables are queried can depend on the input; 
% in other words, these are not necessarily oblivious.
In particular, a read-once branching program on $n$ variables
has length $n$.  Read-once programs  have been well-studied 
and are more commonly  called Ordered Binary
Decision Diagrams (OBDDs) \cite{we00}.  We define quantum and stochastic
OBDDs using the definitions of acceptance given above.
%CP changed next to last sentence in previous paragraph

First, we note that quantum OBDDs of exponential width can compute arbitrary 
Boolean functions. This is simply because quantum branching programs
include permutation programs, and it is easy to see that a permutation 
program with width $2^n$ can simply read the input and devote a 
different final state to every possible input.

% CM: I commented out the following and replaced it with the 
% explanation above...
\comment{
\beprop 
%CP reworded this property
Any Boolean function $f(x_1,\dots,x_n)$ can be exactly computed by a
read-once $\qbp$ of width $2^n$.
 \eeprop
 {\em Proof.} Consider the following read-once width-$2^n$ quantum
branching program: $P$ has basis vectors for its configurations.  That
is, a configuration $\qs{\psi}$ of $P$ contains exactly one 1 and all
the rest components of $\qs{\psi}$ are 0.  An initial configuration of
$P$ is $\qs{\psi_0}=(1,0,\dots,0)$.  $P$ reads input variables in the
order $x_1,x_2,\dots,x_n$ .

In each step $ i, 1\leq i \leq n $ , $P$ reads input $\sigma_i$ and
transforms its current configuration $\qs{\psi}$ as follows: If
$\sigma_i=0$ then $\qs{\psi}$ does not changed.  If
$\sigma_i=1$, then the 1 of the configuration  $\qs{\psi}$ is
``moved'' to $2^{n-i}$ positions to the right in the next
configuration $\qs{\psi'}$.

For an input sequence $\sigma=\sigma_1,\dots,\sigma_n$ denote by
$l_{\sigma}$ coordinate of 1 in the final (after reading
$\sigma$) configuration of $P$. It should be clear 
that $l_{\sigma}\not = l_{\sigma'}$ iff $\sigma \not = \sigma'$.

Now determine  the set of accepting states $F$ of $P$ as
follows: if $f(\sigma)=1$, then $q_{l_\sigma} \in F$. If $f(\sigma)=0$,
then $q_{l_\sigma} \not \in F$.  
 \Endproof
}

% CM: added "To show..."
% CM: I changed p_n to p and put the restriction p < n/2 in the 
% statement of Thm 5 (if you like this change, can you propagate it
% below?) rather than the definition of the function.
% I also added a macro \MOD to fix the typesetting.
%
To show that quantum OBDDs are more powerful than classical ones,
consider the following symmetric Boolean function $\MOD_p$: On input
$\sigma=\sigma_1,\dots,\sigma_n \in \{0,1\}^n$ we have
$\MOD_p(\sigma)=1$ if and only if the number of ones in $\sigma$ is
divisible by $p$.

\bethm\label{qbp-robdd}
Let $p < n/2$.  Then $\MOD_p$ can be computed by a read-once 
quantum branching program of width $O(\log p)$ with 
one-sided error $\eps \ge 0$.
 \eethm
%
% CM: we haven't defined 1-sided error.  Also "for any $\eps > 0$
% should appear above somehow.

The proof of this theorem will be presented in the sub-section below. 
In contrast to this result, it should be easy to see that any
deterministic OBDD for $\MOD_p$ has 
$\Omega(p)$ width. 

\subsection{Proof of Theorem \ref{qbp-robdd} }

% CM: fixed typos in this para and changed to the active voice...
%
We will start by giving a quantum branching program $P$ that
accepts inputs $\sigma \in \MOD^{-1}_p(1)$ with probability $1$ 
and rejects inputs $\sigma \in \MOD^{-1}_p(0)$ with probability 
at least $1/8$.
We will then apply standard techniques 
to reduce the error to an arbitrarily small $\epsilon$.
The program $P$ is defined using a
width-$2$ program $P^k$ for $k \in \{1,\dots,p_n-1\}$. 
We will construct $P$ by selecting 
a good set of these $P^k$'s and running them in superposition.

% CM: Is there any reason to use p_n here instead of p?
% I have changed it to p
%
For a given $k$, $P^k$ has as its start vector
$\qs{\psi_0^k}=\left(\begin{array}{c} 1 \\ 0 \\ \end{array}\right)$
and has transition matrices $T^k = (\langle i, U^k(0), U^k(1)\rangle
)_{i=1}^n$ where

 \[ U^k(0)= \left(\begin{array}{cc} 1 & 0\\ 0 &1 \\
\end{array}\right), U^k(1)=\left(\begin{array}{cc} \cos(2\pi k/p) &
-\sin(2\pi k/p)\\ \sin(2\pi k/p) & \cos(2\pi k/p) \\
\end{array}\right). \]
The accept state $F^k$ of $P^k$ is $\bra{1}$.

Let $\ell(\sigma)$ the number of 1's in the sequence $\sigma$. i.e.,
$\ell(\sigma)= \sum_{i=1}^n \sigma_i$.  Then:

\belem \label{l-ind}
 After reading an input $\sigma=\sigma_1,\dots,\sigma_n$ the
superposition of $P^k$ is
 \[ \qs{\psi}= (\cos \theta_k) \qs{1} + (\sin \theta_k) \qs{2} \]
where $\theta = 2 \pi \,k (\ell(\sigma) \bmod p) / p$.
\eelem

{\noindent \em Proof.}  This follows from the definition of $P^k$.
\Endproof

%CP added a close parenthesis and a comma below
If the $\ell(\sigma)$ is a multiple of $p$, then $\theta_k$ 
is a multiple of $2 \pi$ for all $k$ and $\cos \theta_k =1$,
%$\sin \Bigl (2 \pi \, l(\sigma)k/p_n \Bigr) =0$.  
Therefore, all $P^k$ accept inputs $\sigma \in f^{-1}_{n,p}(1)$ with
probability $1$. 

Call $P^k$ {\em``good"} for input $\sigma \in
\MOD^{-1}_{p}(0)$ if $P^k$ rejects $\sigma$ with probability at least
$1/2$.
 
\belem
 For  any $\sigma \in \MOD^{-1}_{p}(0)$, at least $(p-1)/2$ of
all  $P^k$ are  ``good''.
\eelem

{\noindent \em Proof.}  According to Lemma~\ref{l-ind} after reading
an input $\sigma=\sigma_1,\dots,\sigma_n$ the superposition of $P^k$
is $\qs{\psi}= (\cos \theta_k) \qs{1} + (\sin \theta_k) \qs{2}$. %CP added period

Therefore, the probability of accepting an input $\sigma \in
\MOD^{-1}_{p}(0)$ is $\cos^2 \theta_k$, 
which is less than or equal to $1/2$ if and only if
$\theta_k \in [\pi/4, 3\pi/4]$ or
$\theta_k \in [5\pi/4j, 7\pi/4]$.  As $p$ is prime and
$\ell(\sigma)$ is relatively prime with $p$, it must be that $\ell(\sigma)
\bmod p$, $2\ell(\sigma) \bmod p , \dots,$ $ (p-1)\ell(\sigma)
\bmod p$ are some permutation of $1,2,\dots,p-1$. Consequently,
it is enough to find the size of the set $I=\{i_1,\dots, i_l\}\subset
\{1,\dots, p-1\}$ such that $ 2 \pi \, i_j \, /p \in [\pi/4,
3\pi/4]$ or $ 2 \pi \, i_j \, /p \in [5\pi/4, 7\pi/4]$.  Since the
$p$ points $2\pi/p,\dots, 2\pi(p-1)/p, 2\pi$ are regularly
distributed on the circumference of the circle and the sectors
$[\pi/4,3\pi/4 ]$ and $[5\pi/4,7\pi/4]$ are exactly half of the
circumference, we have $|I|\geq \lfloor p/2 \rfloor \geq
(p-1)/2.$
 \Endproof

% CM: I stopped here

We call a set of quantum programs $S=\{P^{i_1},
\dots, P^{i_t}\}$    ``good'' for
$\sigma \in f^{-1}_{n,p}(0)$
if at least $1/4$ of all its elements are ``good'' for this
$\sigma$.

\belem 
There is a set $S$ of width-$2$ quantum branching programs  with 
$|S|=t=\ceiling{16 \ln p}$ which is
``good'' for all inputs $\sigma \in \MOD^{-1}_{p}(0).$
\eelem

{\noindent \em Proof.}  The following procedure ${\cal A}$ is used to
construct the set $S$:

\begin{quote}
 For a fixed input $\sigma$ with $l(\sigma)
\leq p-1 $, ${\cal A}$ selects a quantum branching program uniformly at
random from $\{P^1,\dots, P^{p-1}\} .$
\end{quote}

The probability of selecting a ``good'' $\qbp$ at each step is at least
$1/2$. Using Chernoff bounds, we get the probability that less than
$1/4$ of all $\qbp$s from the set $S$ are ``good'' for any fixed
$\sigma$ with $l(\sigma)\leq p-1$ is at most
\[ \exp((-16 \ln p)/2 (1/2)^2/2=1/p.\]
Hence, the probability of constructing a set that is not ``good'' for at
least one input $\sigma$ with $l(\sigma)\leq p-1$ is at most
$(p-1)/p>0$. Therefore, there exists a set which is ``good'' for all
inputs $\sigma$ with $l(\sigma)\leq p-1.$ This set is ``good'' for
inputs $\sigma$ with $l(\sigma)> p$ as well, since any $\qbp$, $P^k$,
returns the current superposition to the starting superposition
after reading every $p$ ones, and hence, works the same way on any inputs
$\sigma, \sigma'$ with $l(\sigma)=l(\sigma')\bmod p. $
% CP edited last sentence above
 \Endproof

A program $P$ accepting inputs $\sigma \in \MOD^{-1}_{p}(1)$ with
probability $1$ and rejecting inputs $\sigma \in \MOD^{-1}_{p}(0)$
with probability at least $1/8$ can now be described: $P$'s start and
accepting states are the same as for the $P^k$'s. Its transitions
consist of a superposition of the transitions of $\qbp$'s from a
``good'' set $S=\{P^{i_1}, \dots, P^{{i_{t}}}\}$, weighted with equal
amplitudes.

Notice the inputs $\sigma \in \MOD^{-1}_{p}(1)$ are always accepted by
$P$ with probability $1$ because all $P^k$'s accept them. On the other
hand, for any input $\sigma \in \MOD^{-1}_{p}(0)$ at least $1/4$ of
all $P^k \in S$ reject it with probability at least $1/2$ and the
total probability of rejecting any $\sigma \in \MOD^{-1}_{p}(0)$ is
at least $1/8$.

The error can now be made as small as needed using standard techniques
for reducing error in one-sided error computations. That is,
$d=d(\eps)$ copies of $P$ are taken and run uniformly at random.  In
this case the width of the resulting program will be $O(\log p)$.
\Endproof

%CP I changed this to a definition
\bedef
A branching program $P$ is called {\em stable} if its transformations
do not depend on the level of $P$, i.e., $M_j(0)$ and $M_j(1)$
do not depend on $j$.
\eedef
% CM: added the i.e., above

Observe that the proof of the above theorem constructs a quantum
branching program for $\MOD_{p}$ that is stable.

\becor 
 The function $\MOD_{p}$ can be presented by a stable, read-once,
width-$O(\log p)$ quantum branching program with one-sided error $\eps >0.$
 \eecor

% CP that --> that the ; OBDD --> OBDD's
Now we show that the $\MOD_{p}$ function is hard for randomized OBDD's.

\subsection{Lower Bound for randomized OBDD for $\MOD$}

Randomized OBDD's were first defined and investigated in
\cite{ak98}. See also the book by Wegener~\cite{we00}.

 \bethm
Any stable probabilistic  OBDD computing $\MOD_{p}$ has width at least 
$p$.
\eethm

{\noindent \em Proof.}  Assume that there is a stable probabilistic
OBDD $P$ of width $q < p$ computing $\MOD_{p}$ with probability
$1/2+\eps$ for some fixed $\eps\in (0,1/2]$. We can suppose each level of
$P$ has exactly $q$ nodes without loss of generality. Let
$\mu^j=(\mu^j_1,\dots,\mu^j_q)$ be a probability distribution of
states of $P$ on the $j$-th level, where $\mu^j_i$ is the probability
of being in the $i$-th node of the $j$-th level. We can describe a
computational process of $P$ on an input $\tilde
\sigma=\sigma_1,\dots,\sigma_n$ as follows:
 
\begin{itemize}

\item The computation of $P$ starts from an initial probability
distribution vector $\mu^0$.  

%CP added a comma below
\item On the $j$-th step, $1\leq j \leq n$, $P$ reads $\sigma_{i_j}$
and transforms $\mu^{j-1}$ to $\mu^j=\mu^{j-1} A$, where
$A$ is the $q 
\times q$ stochastic matrix, $A=A(0)$ if $\sigma_{i_j}=0$ and $A=A(1)$ if
$\sigma_{j_k}=1$.

\item After the last ($n$-th) step of the computation, $P$ accepts the input
$\tilde \sigma$ with probability $P_{acc}(\tilde \sigma)=\sum_{i \in
F}\mu_i$. If $f(\tilde \sigma)=1$ then $P_{acc}(\tilde
\sigma)\geq 1/2 + \eps$; otherwise, $P_{acc}(\tilde
\sigma)\leq 1/2 - \eps$.

\end{itemize}

Without loss of generality, assume $P$ reads the inputs in the
natural order $x_1,\dots,x_n$.   
Consider all inputs $\tilde
\sigma_n,\dots,\tilde \sigma_1$, such that
$\tilde\sigma_i=\tilde\sigma_i^0 \tilde\sigma_i^1,$ where
$\tilde\sigma_i^0=\underbrace{0 \dots 0}_{n-i},$
$\tilde\sigma_i^1=\underbrace{1 \dots 1}_{i}.$
 
For $i \in \{1,\dots, n\}$, then denote by $\mu^i$ the probability
distribution after reading the part $\tilde \sigma_i^0$. That is,
$\mu^i=\mu^0 A(0)\cdots A(0)=\mu^0 A^{n-i}(0)$.  There are only ones
in $\tilde \sigma_i^1$, hence a computation after reading $\tilde
\sigma_i^0$ can be described by a Markov chain. In this case $\mu^i$
is the initial probability distribution for a Markov process and $A(1)$
is the transition probability matrix. According to the classification
of Markov chains described in the Section 2 of \cite{kesn60}, the
states of the Markov chain are divided into ergodic and transient
states. An {\em ergodic set of states} is a set which a process cannot
leave once it has entered. A {\em transient set of states} is a set
which a process can leave, but cannot return once it has left. An {\em
ergodic state} is an element of an ergodic set. A {\em transient
state} is an element of a transient set.
 
An arbitrary Markov chain $C$ has at least one ergodic set. It is possible to
have a Markov chain $C$ without any transient set. If a Markov chain $C$ has
more than one ergodic set, then there is absolutely no interaction
between these sets. Hence, we have two or more unrelated Markov chains
lumped together.  These chains can be studied separately. If a Markov
chain consists of a single ergodic set, then the chain is called an
{\em ergodic chain}. According to the classification mentioned above,
every ergodic chain is either regular or cyclic.


If an ergodic chain is regular, then for sufficiently high powers of
the state transition matrix, $A$ has only positive elements. Thus, no
matter where the process starts, after a sufficiently large number of
steps it can be in any state. Moreover, there is a limiting vector of
probabilities of being in the states of the chain, and this vector does not
depend on the initial state.

If a Markov chain is cyclic, then the chain has a period $t$ and all
its states are subdivided into $t$ cyclic subsets $(t>1)$. For a given
starting state a process moves through the cyclic subsets in a
definite order, returning to the subset with the starting state every 
$t$ steps. It is known that after sufficient time has elapsed,
the process can be in any state of the cyclic subset appropriate for
the moment. Hence, for each of the $t$ cyclic subsets, the $t$-th power
of the state transition matrix $A^t$ describes a regular Markov chain.
Moreover, if an ergodic chain is a cyclic chain with the period $t$ it
has at least $t$ states.

From the assumption that $q < p$, we get that $t < p$ for
each cyclic chain. Denote by $D$ the least common multiple of all
such $t$. Because $p$ is prime, $t$ is relatively prime to $p$,
$D$ is relatively prime to $p$, and so is any positive
degree $D^m$ of $D$.

 Let $\alpha^k$ be the probability distribution after reading the part
 $\tilde \sigma_k^1$ of $\tilde\sigma_k.$ That is, $\alpha^k=\mu^k A^k
 (1).$ We can assume that there is a single accepting state without
 loss of generality. Let $\alpha^k_{acc}$ be the probability of being
in the accepting state after reading the input $\tilde\sigma^1_k.$
Since
 after every $D$ steps a process can be in any set of states containing the
 accepting state, the $D$-th power of $A$ describes a regular
 Markov chain for this set. From the theory of Markov chains we have
 that there exists an $\alpha_{acc}$ such that $\lim_{k \to
 \infty}\alpha^{kD}_{acc}=\alpha_{acc}$. Hence, for any $\eps>0$
 it holds that
 \[|\alpha^{D^m}_{acc}-\alpha^{D^m p}_{acc}|<2\epsilon\] for $m$
 large enough. As $P$ is supposed to $1/2+\eps$ computes $\MOD_{p}$, we have
 $\alpha^{D^m p}_{acc}\geq 1/2+\eps$ and
 $\alpha^{D^m}_{acc}\leq 1/2-\eps.$ This contradicts the
 inequality above.
\Endproof



%therefore the probability distributions vector

% Let's $\alpha_k$ is a
%probability being in accepting state after $k$ steps. Since a
%probability distributions vector strives for limiting vector of
%probabilities, $\alpha_k$ strives for $\alpha$ when $k\rightarrow
%\infty$. Therefore for a fixed $\epsilon>0$ there is $k$, that it is
%hold $|\alpha_k-\alpha_{k+i}|<2\eps$ for any $i\in N$.



%Since $f(\tilde\sigma_{D^m})=0$ but $f(\tilde \sigma_{D^m{p_n}})=1$,
%the total of the probability to be in the accepting state must be less
%than $(1/2-\epsilon)$ for $\tilde\sigma_D^1$ and greater than
%$(1/2+\epsilon)$ for $\tilde \epsilon_{D{p_n}}^1$, not depended of the
%initial state. Contradiction. \Endproof


\section{General Lower Bound for Quantum OBDDs}

A general lower bound on the width of read-once
quantum branching programs is now presented. 

 \begin{theorem}\label{lb1}
 Let $\eps\in(0,1/2)$. Let $f(x_1,\dots,x_n)$ be a Boolean function
 $(1/2+\eps)$-computed (computed with margin $\eps$) by
 a quantum read-once branching program  $Q$. Then
 \[ width(Q)=\Omega(\log width(P)) \]
 where $P$  is a deterministic OBDD of minimal width computing
 $f(x_1,\dots,x_n)$. 
 \end{theorem}

%CP use --> uses provving --> proving
The proof of the Theorem~\ref{lb1} uses the same idea used in proving
Theorem~\ref{l-ub} and directly follows that proof.  A deterministic OBDD $P$  
that represents the same function $f$ is constructed such that
%CP added a \cdot
%\[ width(P) \leq \left( 1+\frac{1}{\eps}\right)^{2\cdot width(Q)}. \]
\[ width(P) \leq \left( \frac{2}{\eps}\right)^{2 \cdot width(Q)}. \]
% CM: changed this eq to match the current version of Thm 4
The lower bound on $width(Q)$ given by Theorem~\ref{lb1} proves that
the quantum OBDD constructed for the $\MOD_{p}$ function has the
optimal width possible.

\bigskip
{\bf Acknowledgments.}  We thank Denis Th\'erien for helpful discussions on 
$\ACC$.




quant-ph0201139.extracted_bib
\begin{thebibliography}{1}


\bibitem{amp02} F. Ablayev, C. Moore, and C. Pollett,
Quantum and stochastic branching programs of bounded width. 
{\em Proc.\ 29th Intl.\ Colloquium on Automata, Languages and Programming} 
% Lecture Notes in Computer Science, Springer-Verlag}, 
343--354, 2002.
%Preliminary version appeared as 
%{\em Electronic Colloquium on Computational Complexity} 
%TR 02-013, 2002, available at {\tt http://www.eccc.uni-trier.de/eccc/}

\bibitem{agk01} F. Ablayev, A. Gainutdinova, and M. Karpinski, 
On the computational power of quantum branching programs.
\newblock {\em Proc.\ FCT 2001}, Lecture Notes in Computer Science 
2138: 59--70, 2001.

\bibitem{ak98} F. Ablayev and M. Karpinski, 
A lower bound for integer multiplication on randomized 
read-once branching programs.
{\em Electronic Colloquium on Computational Complexity} TR 98-011, 
1998. {\tt http://www.eccc.uni-trier.de/eccc}

%\bibitem{al84} P. Alexandrov, 
%{\em Introduction to set theory and general topology.}
%Berlin, 1984.

%\bibitem{amfr98} A. Ambainis and R. Freivalds, 
%1-way quantum finite automata: strengths, weaknesses and generalization. 
%{\em Proc.\  39th IEEE Conf.\ on Foundation of Computer Science}  
%332--342, 1998.
% See also {\tt quant-ph/9802062}.

%\bibitem{af98} A. Ambainis and R. Freivalds. 
%\newblock 1-way quantum finite automata: strengths, weakness, and
%generalizations.
%\newblock {\em Proc.\ 39th IEEE Symp.\ on Foundations of
%Computer Science (FOCS)}, 332--342, 1998.

% \bibitem{barenco} A. Barenco, C. Bennett, R. Cleve, D.P. DiVincenzo,
% N. Margolus, P. Shor, T. Sleator, J.A. Smolin and H. Weinfurter.
% \newblock Elementary gates for quantum computation.
% \newblock quant-ph/9503016, {\em Phys. Rev. A} 52: 3457-3467, 1995.

\bibitem{asv00} A. Ambainis, L. Schulman, and U. Vazirani, 
Computing with highly mixed states.
{\em Proc.\ 32nd ACM Symp.\ on Theory of Computing} 697--704, 2000.

\bibitem{bar85}
D.A.~Barrington, 
Bounded-width polynomial branching programs recognize exactly 
those languages in {$NC^1$}.
{\em Journal of Computer and System Sciences} 38(1): 150--164, 
1989.

\bibitem{bt88}
D.A.~Barrington and D.~Therien, 
Finite Monoids and the Fine Structure of {$NC^1$}. 
{\em Journal of the ACM} 35(4): 941--952, 1988.

\bibitem{brs93} A. Borodin, A. Razborov, and R. Smolensky, On lower
bounds for read-$k$-times branching programs, {\em Computational
Complexity}, 3, (1993), 1-18.


\bibitem{kesn60} J.G. Kemeny and J.L. Snell, 
{\em Finite Markov Chains.} 
Van Nostrand, 1960.

\bibitem{kw97}
A.~Kondacs and J.~Watrous, 
On the power of quantum finite automata. 
{\em Proc.\  38th IEEE Conf.\ on Foundations of Computer Science} 
66--75, 1997.

\bibitem{mc97}
C.~Moore and J.P.~Crutchfield, 
Quantum automata and quantum grammars.
{\em Theoretical Computer Science} 237: 275--306, 2000.

% \bibitem{mn00}
% C.~Moore and M.~Nilsson.
% \newblock Parallel quantum computation and quantum codes. 
% \newblock To appear SIAM J. Computing.

\bibitem{mtlbd00}
C.~Moore, D.~Th\'erien, F.~Lemieux, J.~Berman, and A.~Drisko.
\newblock Circuits and Expressions with Non-Associative Gates.
\newblock {\em Journal of Computer and System Sciences} 60:
368--394, 2000.

\bibitem{nahaka00}  M. Nakanishi, K. Hamaguchi, and T. Kashiwabara, 
Ordered quantum branching programs are more powerful than ordered
probabilistic branching programs under a bounded-width restriction.
{\em Proc.\ 6th Intl.\ Conf.\ on
Computing and Combinatorics (COCOON)} Lecture Notes in Computer
Science 1858: 467--476, 2000.

\bibitem{nc00}
M.A.~Nielson and I.L.~Chuang, 
{\em Quantum Computation and Quantum Information.} 
Cambridge University Press, 2000.

\bibitem{papa} C. Papadimitriou, 
{\em Computational Complexity.}  Addison-Wesley, 1994.

\bibitem{rabin}
M. Rabin,
Probabilistic automata.
{\em Information and Control} 6: 230--245, 1963. 

\bibitem{razborov} A.A. Razborov,
Lower bounds for the size of circuits of bounded depth with basis $\{\&, \oplus\}$.
{\em Math. Notes Acad. Sci. USSR} {\bf 41(4)} 333--338, 1987.

% \bibitem{rot94}
% Joseph J. Rotman
% \newblock {\em An Introduction to the Theory of Groups}, $4$th ed. 
% \newblock Springer-Verlag. 1994.

\bibitem{shor97}
P. Shor, 
Polynomial-time algorithms for prime factorization and discrete
logarithms on a quantum computer.
{\em SIAM Journal on Computing} 26(5): 1484--1509, 1997.

\bibitem{smolensky} R. Smolensky,
Algebraic methods in the theory of lower bounds for Boolean circuit
complexity. {\em Proc. 19th ACM Symposium on the Theory of Computing}
77--82, 1987.


 \bibitem{lw01}
 J. H. van Lint and R. M. Wilson.
 \newblock {\em A Course in Combinatorics}, $2$nd ed. 
 \newblock Cambridge. 2001.

\bibitem{we00}
Ingo~Wegener, 
{\em Branching Programs and Binary Decision Diagrams.} 
SIAM Monographs on Discrete Mathematics and Applications, 2000.

\bibitem{yao83}
A.C.~Yao,
Lower Bounds by Probabilistic Arguments. 
{\em Proc.\  24th IEEE Conf.\ on Foundations of Computer Science} 
420--428, 1983.


\end{thebibliography}