On Comparative Computational Power of Classical and Quantum Branching Programs

Farid Ablayev^{∗}

Abstract

We describe a model of a Quantum Branching Program (QBP) and study its computational power. We define several natural restrictions of a general QBP model, such as a constant width and a read-once QBP.

• Constant width. We present upper and lower bounds on the power of quantum and stochastic branching programs of bounded width. We show any NC^{1} function 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. Next, 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}.

• Read-once. We display certain symmetric Boolean function which is computable by a read-once QBP with a O(log n) width, which requires a width Ω(n) on any deterministic read-once BP and (classical) randomized read-once BP with the permanent transitions on each level. We present also a general lower bound on the width of readonce QBPs, showing that the upper bound for the considered symmetric function is almost tight.

∗MPIM, Bonn, Dept. of Theoretical Cybernetics of Kazan State University. Email:

ablayev@ksu.ru

1 Preliminaries

Interest in quantum computation has been steadily increasing since Shor’s discovery of a polynomial time quantum algorithm for factoring [17]. 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 [18]. Remind that polynomial size branching programs as powerful as log space Turing machines.

Also branching program (BP) (see for example book [18]) is a very convenient nonuniform model for implementing different restricted variants of the computational model. Leveled oblivious permutation BPs are well known in complexity theory, their computational power is strong enough. Remind that 5 width polynomial size BPs as powerful as log depth circuits.

Moreover it is appeared that branching programs are very natural model for comparing the computational power of the quantum models with the deterministic ones. Recently, several models of quantum branching programs have been proposed [1, 2, 7, 14].

In this paper we present several results for quantum branching programs of bounded width [1]. 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 NC^{1} function exactly. This is surprising, since such programs act on 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 [19] showed that width-2 deterministic programs require superpolynomial length to compute the majority function, and Barrington [8] showed that width 5 is sufficient for deterministic programs to capture NC^{1}.

Next, we show that bounded-error quantum and stochastic programs can be simulated by deterministic programs of the same length and larger, but still bounded, width. Therefore these classes are contained in NC^{1}, and in fact for bounded-width quantum programs exact acceptance is just as strong as acceptance with bounded probability. We use the techniques of this result to show that polynomial-length width-2 stochastic programs accepting with error margin more than ϵ = 1/4 cannot compute majority. In addition, we show that polynomial-length width-2 stochastic programs accepting with error margin more than ϵ = 1/8 and polynomial-length width-3 stochastic programs accepting with error margin more than ϵ = 1/\sqrt{5} must compute functions in ACC.

Finally, we investigate the properties of the quantum read-once BPs [2]. We first show that read-once exact quantum BPs can compute an arbitrary Boolean function. Next we display a certain symmetric Boolean function which is computable by a read-once QBP with O(log n) width, which requires a width Ω(n) on any deterministic read-once BP and (classical) randomized read-once BP with permanent transitions on each level. We present a general lower bound on the width of read-once QBPs, showing that the upper bound for some symmetric functions is almost tight.

1.1 Branching Programs

We begin by discussing the classical model of branching programs and then show how to quantize it. A good source of information on branching programs is Wegener’s book [18], and for an introduction to quantum computation see Nielsen and Chuang [15].

Definition 1 A branching program is a finite directed acyclic graph which recognizes some subset of {0, 1}^{n}. Each node (except for the sink nodes) is labeled with an integer 1 ≤ i ≤ n and has two outgoing arrows labeled 0 and 1. This corresponds to querying the ith 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 there is a subset A of the sink nodes corresponding to accepting states. An input x is accepted if and only if it induces a chain of transitions leading to a sink node in A.

A branching program is oblivious if the nodes can be partitioned into levels V_{1}, …, V_{l} such that the nodes in V_{l} are the sink nodes, nodes in each level V_{j} with j < l 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 length l, and width k if each level has at most k nodes.

Oblivious branching programs have an elegant algebraic definition. Recall that a monoid is a set with an associative binary operation · and an identity 1 such that 1 · a = a · 1 = a for all a.

Definition 2 Let M be a monoid and S ⊂ M an accepting set. Let x_{i}, 1 ≤ i ≤ n be a set of Boolean variables. A branching program over M of length l is a string of l instructions; the jth instruction is a triple (i_{j}, a_{j}, b_{j}) ∈ {1, …, n} × M × 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 yield Y (x) of the program is the product in M of all its instructions. We say that the input x is accepted if Y (x) ∈ S, and the set of such inputs is the function f recognized by the program.

Such programs are often called non-uniform deterministic finite automata (NUDFAs); a computation over a deterministic finite automaton consists of taking a product in its syntactic monoid, while in a NUDFA we allow the same variable to be queried many times, and for “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 states, where the k states correspond, according to an arbitrary ordering, to the k vertices in each level V_{j}.

Definition 3 An oblivious width-k branching program is a branching program over T_{k}, where the accepting set S ⊂ T_{k} consists of those elements of T_{k} that map an initial state s ∈ {1, …, k} to a final state t ∈ F for some subset F ⊂ {1, …, k}.

2 Bounded Width Branching Programs

We define function classes recognized by (non-uniform) families of boundedwidth branching programs whose length increases polynomially with n:

Definition 4 k-BWBP is the class of functions recognized by polynomiallength branching programs of width k, and BWBP = ∪_{k} k-BWBP.

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

Barrington [8] studied branching programs over the permutation group on k objects S_{k} ⊂ T_{k}; such programs are called permutation programs. He showed that polynomial-length programs over S_{5}, and therefore width-5 branching programs, can recognize any function in NC^{1}, the class of functions recognizable by boolean circuits of polynomial width and logarithmic depth. The version of Barrington’s result that we will use is:

Theorem 1 ([8, 13]) Let G be a non-Abelian simple group, and let a ≠ 1 be any non-identity element. Then any function f 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 ∈ L and 1 otherwise.

Since the smallest non-Abelian simple group is A_{5} ⊂ S_{5}, the group of even permutations of 5 objects, and since we can choose a to map 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 l 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 ⊂ NC^{1}, so we have

5-BWBP = BWBP = NC^{1} .

To define stochastic and quantum branching programs, we write the probability of acceptance as an inner product. Let e_{s} and e_{t} be k-dimensional vectors whose entries are 1 for the initial state and accepting final states respectively and 0 otherwise, and M_{j} the matrix corresponding to the jth instruction. Then write

P (x) = ⟨e_{s} |∏_{j=1}^{l} M_{j}| e_{t}⟩

In the deterministic case P = 1 or P = 0 for all x, since the transition matrix corresponding to an element of T_{k} has exactly one 1 in each column. For a group this is true of the rows as well, in which case the M_{j} are permutation matrices. We can generalize this by letting the M_{j} be stochastic matrices, i.e. mmatrices with non-negative entries where each column sums to 1, and letting e_{s} be an initial probability distribution over the set of states. Then P is the probability that the program accepts. If the transpose of a stochastic matrix is also stochastic the matrix is called doubly stochastic. If all the matrices in a program are doubly stochastic then we say the program is a doubly stochastic program.

In the quantum case, we let the M_{j} be complex-valued and unitary, i.e. M_{j}^{−1} = M_{j}^{†} where † denotes the Hermitian conjugate, and e_{s} and e_{t} be initial and final state vectors with |e_{s}|^{2} = |e_{t}|^{2} = 1. Then the program accepts with probability

P (x) = |⟨e_{s} |∏_{j=1}^{l} M_{j}| e_{t}⟩|^{2}

Note that this is a “measure-once” model analogous to the quantum finite automata of [12], 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 the state as a density matrix and making the M_{i} superoperators instead of purely unitary operators; we do not do this here.

We can define recognition in several ways for the quantum case. We say that a function f is accepted with bounded probability if there is some ϵ > 0 such that P (x) > 1/2 + ϵ if x ∈ L and P (x) < 1/2 − ϵ if x ∉ L, and accepted exactly if P (x) = 1 if x ∈ L and P (x) = 0 if x ∉ L as in the deterministic case.

We denote by B· (where we will drop the ‘·’ when clear) the function classes recognized with bounded probability, and E· those recognized exactly. Writing SBP and QBP for stochastic and quantum branching programs respectively, we define the classes of functions recognized by width-k stochastic and quantum programs of polynomial length k-BSBP, k-BQBP, and k-EQBP. Note that we remove “BW” to avoid acronym overload. We write BSBP for ∪_{k}k-BSBP and define BQBP and EQBP similarly. We have

BWBP ⊆ EQBP ⊆ BQBP

and BWBP ⊆ BSBP

but in principle k-BSBP could be incomparable with k-EQBP or k-BQBP.

2.1 Width-2 Doubly Stochastic and Quantum Programs

In this section we show that width-2 quantum programs with exact acceptance contain NC^{1} and also show that these programs are stronger than width-2 doubly stochastic programs.

First we note that stochastic programs are stronger than permutation programs for width 2. It is easy to see that any program over ℤ_{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 ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) and the matrix ( \begin{matrix}1/2 & 1/2 \\ 1/2 & 1/2 \end{matrix} ) respectively, and for x_{n} it

maps 1 and 0 to ( \begin{matrix}3/4 & 1/4 \\ 0 & 1 \end{matrix} ) and ( \begin{matrix}3/8 & 5/8 \\ 3/8 & 5/8 \end{matrix} ) 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 doubly stochastic program accepting AND_{n} with one-sided error.

Despite being stronger than their permutation counterparts, the next result shows width-2 doubly stochastic branching programs are not that strong. Let MULT _{k}^{n} be the boolean function which computes the kth bit of the product of two n-bit integers. Define MULT^{n} to be MULT _{n−1}^{n}. i.e., the middle bit of the product. We will argue that this function requires at least exponential lengthed width 2 stochastic programs.

Lemma 1 Any width-2 doubly stochastic program on n variables is equivalent to one which queries each variable once and in the order 1,2,3,…,n.

Proof. Any 2 × 2 stochastic matrix can be written as ( \begin{matrix}p & 1 − p \\ 1 − p & p \end{matrix} ) for

some p ∈ [0, 1]. It is easy to verify that matrices of this kind commute. Hence, if we have a product of such matrices ∏_{j}^{n} M_{x_{j_{i}}} 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}. □

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). The next result is proved in Ablayev and Karpinski [3].

Theorem 2 A BP-OBDD that correctly computes MULT^{n} has length at least 2^{Ω(n/log n)}.

So by Lemma 1 we have immediately:

Corollary 1 Any width 2 doubly stochastic program correctly computing MULT^{n} with bounded error has length at least 2^{Ω(n/log n)}.

So width-2 stochastic programs are not that strong. However, width-2 quantum programs are surprisingly strong, as the next result shows. Note that a width-2 quantum program has a state space equivalent to a single qubit such as a single spin-1/2 particle [15].

Theorem 3 NC^{1} is contained in 2-EQBP.

Proof. First, recall that A_{5}, the smallest non-Abelian simple group, is the set of rotations of the icosahedron. Therefore, the group SO(3) of rotations of ℝ^{3}, i.e. the 3 × 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×2 unitary matrices with determinant 1, to SO(3). Consider a qubit a|0⟩+b|1⟩ with |a|^{2} + |b|^{2} = 1; we can make a real by multiplying by an overall phase. The Bloch sphere representation (see e.g. [15]) views this state as the point on the unit sphere with latitude θ and longitude ϕ, i.e. (cos ϕ cos θ, sin ϕ cos θ, sin θ), where a = cos θ/2 and b = e^{iϕ} sin θ/2.

Given this representation an element of SU(2) is equivalent to some rotation of the unit sphere. Recall the Pauli matrices

σ_{x} = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) , σ_{y} = ( \begin{matrix}0 & i \\ −i & 0 \end{matrix} ) , σ_{z} = ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} )

Then we can rotate an angle α around the x, y or z axes with the following operators:

R_{x}(α) = e^{i(α/2)σ_{x}} = ( \begin{matrix}cos α/2 & −i sin α/2 \\ −i sin α/2 & cos α/2 \end{matrix} )
R_{y}(α) = e^{i(α/2)σ_{y}} = ( \begin{matrix}cos α/2 & − sin α/2 \\ sin α/2 & cos α/2 \end{matrix} ) , and
R_{z}(α) = e^{i(α/2)σ_{z}} = ( \begin{matrix}e^{−iα/2} & 0 \\ 0 & e^{iα/2} \end{matrix} ) .

This makes SU(2) a double cover of SO(3), where each element of SO(3) corresponds to two elements ±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π/5 rotations around two adjacent vertices of an icosahedron. Since two such vertices are an angle tan^{−1} 2 apart, if one is pierced by the z axis and the other lies in the x-z plane we have

a = R_{z}(2π/5) = ( \begin{matrix}e^{iπ/5} & 0 \\ 0 & e^{−iπ/5} \end{matrix} )
b = R_{y}(tan^{−1} 2) · a · R_{y}(− tan^{−1} 2)
= \frac{1}{\sqrt{5}} ( \begin{matrix}e^{iπ/5}τ + e^{−iπ/5}τ^{−1} & −2i sin π/5 \\ −2i sin π/5 & e^{−iπ/5}τ + e^{iπ/5}τ^{−1} \end{matrix} )

where τ = (1 + \sqrt{5})/2 is the golden ratio. Now consider the group element c = a·b·a; this rotates the icosahedron by π around the midpoint of the edge connecting these two vertices. In SU(2), this maps each of the eigenvectors of σ_{y} to the other times an overall phase. Taking these as the initial and final state,

e_{s} = \frac{|0⟩ + i|1⟩}{\sqrt{2}}, e_{t} = \frac{|0⟩ − i|1⟩}{\sqrt{2}}

we have

|⟨e_{s}|c|e_{t}⟩|^{2} = 1

while, since the two eigenvectors are orthogonal,

|⟨e_{s}|1|e_{t}⟩|^{2} = 0 .

Now, Theorem 1 tells us that for any function 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 function and 1 otherwise. Mapping this function to SU(2) gives a program which yields ±c or 1, and accepts with probability 1 or 0. □

2.1.1 Deterministic Classical Simulations of Stochastic and Quantum Branching Programs

In this section we give general results on simulating stochastic and quantum programs by classical ones. We use this to show that width-2 quantum programs can be simulated by bounded-width deterministic programs, and to show that if ϵ > 1/4 then width-2 stochastic programs for majority require super-polynomial length. We also get that polynomial-length width-2 stochastic programs accepting with error margin more than ϵ = 1/8 and polynomial-length width-3 stochastic programs accepting with error margin more than ϵ = 1/\sqrt{5} must compute functions in ACC.

Theorem 4 If a function is recognized with bounded probability 1/2 + ϵ by a width-w stochastic branching program, then it is also recognized by a deterministic branching program D of the same length, and width

w′ ≤ (1 + \frac{1}{ϵ})^{w} .

Similarly, if a function is recognized with bounded probability 1/2 + ϵ by a width-w quantum branching program, it is recognized by a deterministic program of the same length, and width

w′ ≤ (1 + \frac{1}{ϵ})^{2w} .

Proof of Theorem 4 We start with the idea of lower bounds proof and notations we use for formal proof.

Let us denote (w, l)-P an w width and l length BP. The idea of proofs of theorem 4 is that having stochastic (quantum) (w, l)-P that computes a function f with margin ϵ we construct a deterministic BP (w′, l) - P′ such that P′ computes the same function f and

w′ ≤ (1 + \frac{1}{ϵ})^{w}

when P is stochastic BP and

w′ ≤ (1 + \frac{1}{ϵ})^{2w}

when P is quantum BP.

The construction of P′ is based on the following properties. We will view on computation by oblivious (stochastic and quantum) BP (w, l)-P as an l step linear process of transformation of vectors α of a current internal description (ID) of P. In stochastic case α = μ, where μ = (p_{1}, …, p_{w}) is a current probability distribution of a states of P, and in quantum case α = |ψ⟩, where |ψ⟩ = (z_{1}, …, z_{w})^{T} is a current distribution of amplitudes of states of P.

We represent this l step linear process as an (l + 1)-leveled deterministic branching program DP, as follows: each node of DP labeled by vector α corresponds to an ID of P, and each level i ∈ {0, …, l} represents a step of the computation. The level 0 contains initial node labeled α_{0} — the initial distribution of P. From each node α on the level i, i ∈ {0, …, l − 1}, out goes two edges labeled x_{j_{i}} = 0 and x_{j_{i}} = 1 where x_{j_{i}} is a variable tested in the computational step i. Edge x_{j_{i}} = 1, directed from parent α on a level i to child α′ on the level i + 1 iff P being on the step i of computation in ID α tests x_{j_{i}} = 1 and transforms its ID on the step i + 1 to α′.

Denote Accept (Reject) a set of all accepting (rejecting) sink nodes of P. Sink nodes of DP on the level l are labeled in addition by 1 (”accept”) and 0 (”reject”) as follows: in stochastic case sink node α = (p_{1}, …, p_{w}) labeled 1 if P r_{accept}(α) = ∑_{j∈Accept} p_{j} ≥ 1/2 + ϵ, and labeled 0 if P r_{accept}(α) = ∑_{j∈Accept} p_{j} ≤ 1/2 − ϵ; in quantum case node α = (z_{1}, …, z_{w})^{T} labeled 1 if P r_{accept}(α) = ∑_{j∈Accept} |z_{j}|^{2} ≥ 1/2 + ϵ, and labeled 0 if P r_{accept}(α) = ∑_{j∈Accept} |z_{j}|^{2} ≤ 1/2−ϵ. Denote A (R) a set of all sink nodes of DP labeled 1 (0).

As usual DP accepts (rejects) an input a⃗ = a_{1} … a_{n} if the computation of DP on a⃗ ends in accepting (rejecting) node.

From the above we have the following property.

Property 1 Deterministic branching program DP computes the same Boolean function f as P.

In the next section we use metric point of view to DP for constructing deterministic BP (w′, l)-P′ that computes the same function as DP and hence the same function as P.

Metric Properties of DP Denote Ψ_{i}, i ∈ {0, …, l}, a set all possible IDs of P on step i of computation. Let Ψ = ∪_{i=0}^{l}Ψ_{i}. For stochastic P we define metric on the space Ψ based on norm || · ||_{1}. That is, for α = (p_{1}, …, p_{w}) and α′ = (p′_{1}, …, p′_{w}) ρ(α, α′) = ||α − α′||_{1} = ∑_{i=1}^{w} |p_{i} − p′_{i}|. For quantum P we define metric on the space Ψ based on norm || · ||_{2}: for α = (z_{1}, …, z_{w}) and α′ = (z′_{1}, …, z′_{w}) ρ(α, α′) = ||α − α||_{2}. We will also use notation || · || for norm || · ||_{2}.

Recall known notions of metric spaces we need in the proof (see for example [5]). Denote H_{w} an w-dimensional vector space (real valued or complex valued) with metric ρ. Points μ, μ′ from H_{w} are connected through θ-chain if there exists a finite set of points μ_{1}, μ_{2}, …, μ_{m} from H_{w} such that μ_{1} = μ, μ_{m} = μ′ and ρ(μ_{i}, μ_{i+1}) < θ for i ∈ {1, …, m − 1}. For H_{w} its subset C is called θ-component if arbitrary two points μ, μ′ ∈ C are connected through θ-chain. It is known [5] that if D is a finite diameter subset of a subspace of H_{w} (diameter of D is defined as sup_{μ,μ′∈D}{ρ(μ, μ′)} then for θ > 0 D is partitioned to a finite number t of its θ-components.

Lemma 2 Let f be a Boolean function (1/2 + ϵ)-computed by P. Let DP be a corresponding deterministic BP for P. Let θ > 0 and let for sink nodes of DP the following holds: for arbitrary α ∈ A and α′ ∈ R it is holds that ρ(α, α′) ≥ θ. Then, there exists a deterministic BP (w′, l)-P which computes f and

w′ ≤ (1 + \frac{2}{θ})^{w}

when P is stochastic BP, and

w′ ≤ (1 + \frac{2}{θ})^{2w}

when P is quantum BP.

Proof. Consider D a sphere of radius 1 with center in (0, …, 0). We clearly have that Ψ ⊆ D. From the condition of the lemma it follows that subsets A and R of Ψ_{l} is a union of some θ-components of Ψ_{l}. Next. Oblivious property of BP P provides the following: on the each level i, i ∈ {0, …, l − 1}, of DP for all nodes α ∈ Ψ_{i} it is tested the same variable x_{j_{i}} and applied the same linear transition M_{x_{j_{i}}} (1) if x_{j_{i}} = 1 (M_{x_{j_{i}}} (0) if x_{j_{i}} = 0) where M_{x_{j_{i}}} (a) is stochastic matrix when P is stochastic BP and M_{x_{j_{i}}} (a) is unitary when P is quantum BP.

It is known (and it can be easily verified) that transformations determined by stochastic matrix M does not increase the distance. That is, if α′ = Mα and β′ = Mβ then ρ(α′, β′) ≤ ρ(α, β). Unitary matrix M preserves the distance. That is, it is holds that ||α′ − β′|| = ||α − β||.

Denote C_{i} the set of all θ-components of Ψ_{i}. For C ∈ C_{i} and matrix M we denote MC = {α′ : α = Mα, α ∈ C}. From the property of non increasing distance linear transformations (stochastic or uniform) it is holds that for C ∈ C_{i} and for a ∈ {0, 1} there exists C′ ∈ C_{i+1} such that MC ⊆ C′ for the stochastic P and MC = C′ for the quantum P.

Now we describe deterministic BP P′ that computes f as follows: P′ is an l-leveled oblivious BP. On the level i tested variable x_{j_{i}} (as in BP) and all nodes are labeled by θ-components C ∈ C_{i}. From the node C ∈ C_{i} edge labeled x_{j_{i}} = a goes to to node C′ ∈ C_{i+1} iff M_{x_{j_{i}}} (a)C ⊆ C′.

From the above it follows that P′ computes the same function as DP The width w(P′) of P′ is w′ = max{t_{0}, …, t_{l}} where t_{i} is the number θ-

components of Ψ_{i}. Let w′ = t_{i}. We estimate the number t of θ-components (number of nodes of B) of Ψ_{j} as follows.

For each θ-component C ∈ C_{i} select one point α ∈ C. If we draw a sphere of the radius θ/2 with the center α ∈ C then all such spheres do not intersect pairwise. All these w′ spheres are in large sphere of radius 1 + θ/2 which has center (0, 0, …, 0). The volume of a sphere of a radius r in H_{w} is cr^{w} when H_{w} is real space and is cr^{2w} when H_{w} is complex space (in the complex space H_{w} each complex point is a 2-dimensional point). Constant c depends on the metric of H_{w}. Now for stochastic and quantum case we have respectively that

w′ ≤ \frac{c (1 + θ/2)^{w}}{c (θ/2)^{w}} = (1 + \frac{2}{θ})^{w} , w′ ≤ \frac{c (1 + θ/2)^{2w}}{c (θ/2)^{2w}} = (1 + \frac{2}{θ})^{2w} ,

□

Below we present technical lemma that estimates parameter θ of the lemma 2 depending on margin ϵ of computation.

Lemma 3 Let f be a Boolean function (1/2 + ϵ)-computed by (w, l)-P. Let DP be a corresponding deterministic BP for P.

Then for arbitrary α ∈ A and α′ ∈ R for the case of stochastic P it is holds that:

||α − α′||_{1} ≥ θ = 2ϵ,

for the case of quantum P it is holds that:

||α − α′|| ≥ θ = 2ϵ.

Proof. Consider the case of stochastic P. α = (p_{1} …, p_{w})^{T}, α′ = (p′_{1} …, p′_{w})^{T},

||α − α′||_{1} = ∑_{i=1}^{w} |p_{i} − p′_{i}| ≥ ∑_{i∈Accept} |p_{i} − p′_{i}| ≥ | ∑_{i∈Accept} p_{i} − ∑_{i∈Accept} p′_{i}|

From the condition of the lemma we have that ∑_{i∈Accept} p_{i} ≥ 1/2 + ϵ and ∑_{i∈Accept} p′_{i} ≤ 1/2 − ϵ. From this we have that

||α − α′||_{1} ≥ 1/2 + ϵ − (1/2 − ϵ) = 2ϵ.

Consider the case of quantum P. α = (z_{1}, …, z_{d})^{T} and α′ = (z′_{1}, … z′_{d})^{T}.

From the condition of the lemma it is holds that

2ϵ ≤ ∑_{i∈Accept} (|z_{i}|^{2} − |z′_{i}|^{2}) = ∑_{i∈Accept} (|z_{i}| − |z′_{i}|)(|z_{i}| + |z′_{i}|) ≤ ∑_{i∈Accept} (|z_{i} − z′_{i}|)(|z_{i}| + |z′_{i}|)

and similarly

2ϵ ≤ ∑_{i∈Reject} (|z′_{i}|^{2} − |z_{i}|^{2}) = ∑_{i∈Reject} (|z′_{i}| − |z_{i}|)(|z_{i}| + |z′_{i}|) ≤ ∑_{i∈Reject} (|z_{i} − z′_{i}|)(|z_{i}| + |z′_{i}|)

or

4ϵ ≤ ∑_{i=1}^{w} (|z_{i} − z′_{i}|)(|z_{i}| + |z′_{i}|).

From the above using known inequality ∑_{i=1}^{d} a_{i}b_{i} ≤ \sqrt{∑_{i=1}^{d} a_{i}^{2}}\sqrt{∑_{i=1}^{d} b_{i}^{2}} and triangle inequality for the norm we get that

4ϵ ≤ ||α − α′||(|| |α| + |α′| || ≤ ||α − α′||(||α|| + ||α′|| = 2||α − α′||

□

Now the lower bounds of the theorem 4 follows immediately from lemmas 2 and 3. This completes the proof of theorem 4 □

While we may need an exponentially larger width to simulate a stochastic or quantum branching program, the width is still constant. Thus boundedwidth programs of all three types are equivalent, and since bounded-width classical programs are contained in NC^{1} they all are. Conversely, we showed in Theorem 3 that NC^{1} is contained in width-2 quantum programs, so we have

Corollary 2

2-EQBP = 2-BQBP = BQBP = BSBP = BWBP = NC^{1} .

In other words, width-2 quantum programs with exact acceptance are exactly as strong as quantum or stochastic programs of arbitrary bounded width, with exact or bounded-error acceptance.

3 Read-once Branching Programs (OBDDs)

We investigate computational power of read-once branching programs in this section. In according to definitions 3 we use here the following model of branching programs:

1. each variable of a branching program is tested only once during a computation.

2. We do not restrict a width of branching program to constant.

We clearly have that read-once branching program has length n where n is a number of Boolean variables of branching program. This model of branching programs is well known and usually called Ordered Binary Decision Diagram (quantum OBDD) [18].

The next statement says that exponential width read-once quantum branching can computes arbitrary Boolean function. This is not surprised. This is true for classical deterministic OBDDs as well. We present this statement for the complete of presentation.

Property 2 For an arbitrary Boolean function f(x_{1}, …, x_{n}), there exists a read-once 2^{n}QBP that exact computes f.

Proof. The proof is simple. For example, the following read-once 2^{n}QBP P is a QBP satisfied the proposition. All possible configurations of P are trivial. That is, a configuration |ψ⟩ of P contains exactly one 1 and all the rest components of |ψ⟩ are 0. An initial configuration of P is |ψ_{0}⟩ = (1, 0, …, 0). P reads input variables in order x_{1}, x_{2}, …, x_{n} .

In each step i, 1 ≤ i ≤ n , P reads input σ_{i} and transforms its current configuration |ψ⟩ as follows. If σ_{i} = 0 then |ψ⟩ does not changed. If σ_{i} = 1, then the 1 of the configuration |ψ⟩ is “moved” to 2^{n−i} positions to the right in the next configuration |ψ′⟩.

For an input sequence σ = σ_{1}, ….σ_{n} denote l_{σ} the number of position of 1 in the final (after reading σ) configuration of P. Clearly we have that l_{σ} ≠ l_{σ′} iff σ ≠ σ′.

Now determine the set of accepting states F of P as follows: if f(σ) = 1, then q_{l_{σ}} ∈ F. If f(σ) = 0, then q_{l_{σ}} ∉ F. □

Consider the following symmetric Boolean function MOD_{p_{n}}: For an input σ = σ_{1}, …, σ_{n} ∈ {0, 1}^{n} we have MOD_{p_{n}}(σ) = 1 iff a number of ones in σ is divisible by p_{n}, where p_{n} is a prime and p_{n} ≤ n/2.

Theorem 5 The function MOD_{p_{n}} can be presented by a read-once O(log p_{n})QBP with one-sided error ϵ ≥ 0.

The proof of this theorem will be presented in the section below. We have clearly that any deterministic OBDD for MOD_{p_{n}} has Ω(p_{n}) width.

3.1 Proof of the Theorem 5

We construct a QBP P accepting inputs σ ∈ MOD_{p_{n}}^{−1}(1) with probability 1 and rejecting inputs σ ∈ MOD_{p_{n}}^{−1}(0) with probability at least 1/8. Consider 2QBP P^{k} for k ∈ {1, …, p_{n} − 1}. Quantum program P^{k} = ⟨T^{k}, |ψ_{0}^{k}⟩, F^{k}⟩ based on 2-state quantum system. Here T^{k} = (⟨i, U^{k}(0), U^{k}(1)⟩)_{i=1}^{n} where

U^{k}(0) = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) , U^{k}(1) = ( \begin{matrix}cos(2πk/p_{n}) & − sin(2πk/p_{n}) \\ sin(2πk/p_{n}) & cos(2πk/p_{n}) \end{matrix} ) , |ψ_{0}^{k}⟩ = ( \begin{matrix}1 \\ 0 \end{matrix} ) , F^{k} = \{1\}.

Denote by l(σ) a number of 1-s in the sequence σ, l(σ) = ∑_{i=1}^{n} σ_{i}. Lemma 4 After reading an input σ = σ_{1}, …, σ_{n} the superposition of P^{k} is

|ψ⟩ = cos (\frac{2π l(σ)k}{p_{n}} ) |1⟩ + sin (\frac{2π l(σ)k}{p_{n}} ) |2⟩.

Proof: The proof follows from the description of QBP P^{k}.

□

If the number of ones in an input σ is divisible by p_{n} then 2π l(σ)k/p_{n} is a multiple of 2π and cos(2π l(σ)k/p_{n}) = 1, sin(2π l(σ)k/p_{n}) = 0 . Therefore all QBP P^{k} accept inputs σ ∈ f_{n,p_{n}}^{−1}(1) with probability 1.

Call P^{k} ”good” for input σ ∈ MOD_{p_{n}}^{−1}(0) if P^{k} reject σ with probability at least 1/2. Lemma 5 For any σ ∈ MOD_{p_{n}}^{−1}(0), at least (p_{n}−1)/2 of all P^{k} are “good”.

Proof: According to the Lemma 4 after reading an input σ = σ_{1}, …, σ_{n} the superposition of P^{k} is

|ψ⟩ = cos (\frac{2π l(σ)k}{p_{n}} ) |1⟩ + sin (\frac{2π l(σ)k}{p_{n}} ) |2⟩.

Therefore, the probability of accepting the input σ ∈ MOD_{p_{n}}^{−1}(0) is cos^{2}(2π l(σ)k/p_{n}). cos^{2}(2π l(σ)k/p_{n}) ≤ 1/2 iff |cos(2π l(σ)k/p_{n})| ≤ 1/\sqrt{2}. This happens if and only if (2π l(σ)k/p_{n}) is in [π/4 + 2πj, 3π/4 + 2πj] or in [5π/4 + 2πj, 7π/4 + 2πj] for some j ∈ N. (2π l(σ)k/p_{n}) ∈ [π/4 + 2πj, 3π/4 + 2πj] iff (2π (l(σ)k mod p_{n})/p_{n}) ∈ [π/4, 3π/4]. p_{n} is prime, l(σ) is relatively prime with p_{n}. Therefore, l(σ) mod p_{n}, 2l(σ) mod p_{n}, …, (p_{n} − 1)l(σ) mod p_{n} is 1, 2, …, p_{n} − 1 in different order. Consequently, it is enough to find the power of a set I = {i_{1}, …, i_{l}} ⊂ {1, …, p_{n} − 1} such that 2π i_{j} /p_{n} ∈ [π/4, 3π/4] or 2π i_{j} /p_{n} ∈ [5π/4, 7π/4]. Since p_{n} points 2π/p_{n}, …, 2π(p_{n} − 1)/p_{n}, 2π are regularly distributed on a circumference and sectors [π/4, 3π/4] and [5π/4, 7π/4] are exactly half of the circumference, therefore |I| ≥ ⌊p_{n}/2⌋ ≥ (p_{n} − 1)/2.

□

We call a set of quantum programs S = {P^{i_{1}}, …, P^{i_{t}}} “good” for σ ∈ f_{n,p_{n}}^{−1}(0) if at least 1/4 of all its elements are “good” for this σ.

Lemma 6 There is a set S of 1QBPs with |S| = t = ⌈16 ln p_{n}⌉ which is “good” for all inputs σ ∈ MOD_{p_{n}}^{−1}(0).

Proof: We consider following procedure A for construction the set S.

For a fixed input σ with l(σ) ≤ p_{n} −1 A selects quantum branching program uniformly at random from {P^{1}, …, P^{p_{n}−1}}.

The probability of selecting a “good” QBP on each step is at least 1/2. Using Chernoff inequality, we have the probability that less than 1/4 fraction of all QBPs from the set S are “good” for any fixed σ with l(σ) ≤ p_{n} − 1 is at most

exp((−16 ln p_{n})/2(1/2)^{2}/2 = 1/p_{n}.

Hence the probability that constructing set is not “good” for at least one input σ with l(σ) ≤ p_{n} − 1 is at most (p_{n} − 1)/p_{n} > 0. Therefore there exist a set which is “good” for all inputs σ with l(σ) ≤ p_{n} − 1. This set is “good” for inputs σ with l(σ) > p_{n} as well since any QBP P^{k} returns a currently superposition to starting superposition after reading every p_{n} ones, and hence works the same way on inputs σ, σ′ with l(σ) = l(σ′) mod p_{n}.

□

We construct a 1QBP P accepting inputs σ ∈ MOD_{p_{n}}^{−1}(1) with probability 1 and rejecting inputs σ ∈ MOD_{p_{n}}^{−1}(0) with probability at least 1/8 as follows. The 1QBP P consists of QBPs from “good” set S = {P^{i_{1}}, …, P^{i_{t}}}, which work in parallel. In the starting superposition of P all these programs represented with equal amplitudes.

Inputs σ ∈ MOD_{p_{n}}^{−1}(1) are always accepted with probability 1 because all P^{k}s accept them. For any input σ ∈ MOD_{p_{n}}^{−1}(0) at least 1/4 of all P^{k} ∈ S reject it with probability at least 1/2 and the total probability of rejecting any σ ∈ MOD_{p_{n}}^{−1}(0) is at least 1/8.

We can make the error as small as possible using standard technique for reducing error for one-sided error computation. That is, we take d = d(ϵ) copies of such 1QBP P and run them uniformly at random. In this case the width of 1QBP will be O(log p_{n}). □

• We call a branching program P stable if its transformations does not depend on the level of P.

From the proof of the theorem we have that a constructed QBP for MOD_{p_{n}} is a stable branching program.

Corollary 3 The function MOD_{p_{n}} can be presented by a stable read-once (O(log p_{n})QBP with one-sided error ϵ > 0.

Below we show that MOD_{p_{n}} function is hard for randomized OBDD.

3.2 Lower Bound for randomized OBDD for MOD

Randomized OBDDs are defined and investigated first in [3]. See also book [18].

Theorem 6 Any stable probabilistic OBDD computing MOD_{p_{n}} has width at least p_{n}.

Proof: Assume that there is a stable probabilistic OBDD P of width q < p_{n} computing MOD_{p_{n}} with probability 1/2 + ϵ for a fixed ϵ ∈ (0, 1/2]. We can suppose each level of P has exactly q nodes without loss of generality. Let μ^{j} = (μ_{1}^{j}, …, μ_{q}^{j}) be a probability distribution of states of P on j-th level, where μ_{i}^{j} is probability of being in the i-th node of the j-th level. We can describe a computational process of P on an input σ̃ = σ_{1}, …, σ_{n} as follows:

• Computation of P starts from the initial probability distributions vector μ^{0}.

• On j-th step, 1 ≤ j ≤ n P reads input σ_{i_{j}} and transforms vector μ^{j−1} to μ^{j} = μ^{j−1}A, where A is q ×q stochastic matrix, A = A(0) if σ_{i_{j}} = 0 and A = A(1) if σ_{j_{k}} = 1.

• After the last (n-th) step of computation P accepts the input σ̃ with probability P_{acc}(σ̃) = ∑_{i∈F} μ_{i}. If f(σ̃) = 1 then we have P_{acc}(σ̃) ≥ 1/2 + ϵ, else we have P_{acc}(σ̃) ≤ 1/2 − ϵ.

We assume P reads inputs in the natural order x_{1}, …, x_{n} without loss of generality. We consider all inputs σ̃_{n}, …, σ̃_{1}, such that σ̃_{i} = σ̃_{i}^{0}σ̃_{i}^{1}, where

σ̃_{i}^{0} = \underbrace{0 … 0}_{n−i}, σ̃_{i}^{1} = \underbrace{1 … 1}_{i} .

For i ∈ {1, …, n} we denote μ^{i} probability distribution after reading the part σ̃_{i}^{0}. That is, μ^{i} = μ^{0}A(0) ⋯ A(0) = μ^{0}A^{n−i}(0). There are only ones in the σ̃_{i}^{1}, hence a computation after reading σ̃_{i}^{0} can be described by a Markov chain. In this case μ^{i} is the initial probability distribution for a Markov process, A(1) is the transition probability matrix. According to the classification of Markov chains described in the Section 2 of [10], the states of the Markov chain are decided into ergodic and transient states. An ergodic set of states is set which a process cannot leave if it once entered. A transient set of states is a set which a process can leave, but cannot return if it once left. An ergodic state is an element of an ergodic set. A transient state is an element of transient set.

An arbitrary Markov chain C has at least one ergodic set. C can be a Markov chain 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 we can study separately. If a Markov chain consist of a single ergodic set, then the chain called an ergodic chain. According to the classification, every ergodic chain is either regular or cyclic.

If an ergodic chain is regular, then sufficiently high power of the state transition matrix A has only positive elements. Thus no matter where the process starts, after sufficient large time of steps it can be in any state. Moreover there is the limiting vector of probabilities of being in the states of the chain, not dependent of 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 after every t steps. It is know that after sufficient time has elapsed, the process can be in any state of the cyclic subset appropriate for the moment. Hence for every of t cyclic subsets the t-th power of state transition matrix A^{t} describes a regular Markov chain. Moreover if an ergodic chain is cyclic chain with the period t it has at least t states.

From the assumption q < p_{n} of the proof we get that t < p_{n} for every of cyclic chains. We denote D the least common multiply of all such t. Because p_{n} is prime, t is relatively prime to p_{n}, D is relatively prime to p_{n}, and so is any positive degree D^{m} of D.

Let α^{k} be a probability distribution after reading the part σ̃_{k}^{1} of σ̃_{k}. That is, α^{k} = μ^{k}A^{k}(1). We can assume that there is a single accepting state without loss of generality. Let α_{acc}^{k} be a probability of being on accepting state after reading the input σ̃_{k}^{1}. Since after every D steps a process can be in any state of set consisting accepting state, D-th power of matrix A describes a regular Markov chain for this set. From the theory of Markov chains we have that there exist α_{acc} that lim_{k→∞} α_{acc}^{kD} = α_{acc}. Hence for any ϵ > 0 it holds that

|α_{acc}^{D^{m}} − α_{acc}^{D^{m}p_{n}}| < 2ϵ

for m large enough. As P 1/2+ϵ computes MOD_{p_{n}} we have α_{acc}^{D^{m}p_{n}} ≥ 1/2+ϵ and α_{acc}^{D^{m}} ≤ 1/2 − ϵ. The contradiction with the inequation above.

□

4 General Lower Bound for Quantum OBDDs

Below we present a general lower bound on the width of read-once quantum branching programs.

Theorem 7 Let ϵ ∈ (0, 1/2). Let f(x_{1}, …, x_{n}) be a Boolean function (1/2 + ϵ)-computed (computed with margin ϵ) by quantum read-once branching program Q. Then it is holds that

width(Q) = Ω(log width(P))

where P is a deterministic OBDD of minimal width computing f(x_{1}, …, x_{n}).

Proofs of the theorem 7 use the same idea used for proving theorem 4 and directly follows the proof. We construct a deterministic OBDD P that presents the same function f and

width(P) ≤ (1 + \frac{1}{ϵ})^{2width(Q)} .

The lower bound for width(Q) of the theorem 7 proves that the quantum OBDD constructed for MOD_{p_{n}} function has possible optimal width.

References

[1] F. Ablayev, C. Moore, and C. Pollett, Quantum and Stochastic Branching Programs of Bounded Width, in Proceedings of the ICALP’2002, Lecture Notes in Computer Science, Springer-Verlag, 343-354. See also Electronic Colloquium on Computational Complexity, TR02-013, 2002,

available at http://www.eccc.uni-trier.de/eccc/

[2] F. Ablayev, A. Gainutdinova, and M. Karpinski. On computational Power of quantum branching programs. Proc. FCT 2001, Lecture Notes in Computer Science 2138: 59–70, 2001.

[3] F. Ablayev and M. Karpinski. A lower bound for integer multiplication on randomized read-once branching programs. Electronic Colloquium on Computational Complexity TR 98-011, 1998.

http://www.eccc.uni-trier.de/eccc

[4] A. Ambainis and R. Freivalds, 1-way quantum finite automata: strengths, weaknesses and generalization, In Proceeding of the 39th IEEE Conference on Foundation of Computer Science, 1998, 332-342. See also quant-ph/9802062 v3.

[5] P. Alexandrov. Introduction to set theory and general topology. Berlin, 1984.

[6] A. Ambainis and R. Freivalds. 1-way quantum finite automata: strengths, weakness, and generalizations. Proc. 39th IEEE Symp. on Foundations of Computer Science (FOCS), 332–342, 1998.

[7] A. Ambainis, L. Schulman, and U. Vazirani. Computing with Highly Mixed States. Proc. 32nd Annual ACM Symp. on Theory of Computing (STOC), 697–704, 2000.

[8] D.A. Barrington. Bounded-width polynomial branching programs recognize exactly those languages in NC^{1}. Journal of Computer and System Sciences 38(1): 150–164, 1989.

[9] D.A. Barrington and D. Therien. Finite Monoids and the Fine Structure of NC^{1} Journal of the ACM 35(4): 941–952, 1988.

[10] J. G. Kemeny, J. L. Snell, Finite Markov Chains, Van Nostrand Company, INC, 1960.

[11] A. Kondacs and J. Watrous On the power of quantum finite automata. Proc. of the 38th IEEE Symp. on Foundations of Computer Science (FOCS), 66–75, 1997.

[12] C. Moore and J.P. Crutchfield. Quantum automata and quantum grammars. Theoretical Computer Science 237: 275–306, 2000.

[13] C. Moore, D. Thérien, F. Lemieux, J. Berman, and A. Drisko. Circuits and Expressions with Non-Associative Gates. Journal of Computer and System Sciences 60: 368–394, 2000.

[14] M. Nakanishi, K. Hamaguchi, and T. Kashiwabara. Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction. Proc. 6th Annual International Conference on Computing and Combinatorics (CO-COON) Lecture Notes in Computer Science 1858: 467–476, 2000.

[15] M.A. Nielson and I.L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press. 2000.

[16] M. Rabin. Probabilistic automata. Information and Control 6: 230– 245, 1963.

[17] P. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5): 1484–1509, 1997.

[18] Ingo Wegener. Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications. 2000.

[19] A.C. Yao. Lower Bounds by Probabilistic Arguments Proc. of the 24th IEEE Symp. on Foundations of Computer Science (FOCS), 420–428, 1983.