On Computational Power of Quantum Branching Programs

Farid Ablayev^{∗} Aida Gainutdinova^{†} Marek Karpinski^{‡}

Abstract

In this paper we study a model of Quantum Branching Program (QBP) and investigate its computational power. We define several natural restrictions of a general QBP model, such as a read-once and a read-k-times QBP, noting that obliviousness is inherent in a quantum nature of such programs.

In particular we show that any Boolean function can be computed deterministically (exactly) by a read-once QBP in width O(2^{n}), contrary to the analogous situation for quantum finite automata. Further we display 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 at each level.

We present a general lower bound for the width of read-once QBPs, showing that the upper bound for a considered symmetric function is almost tight.

1 Introduction

Richard Feynman observed in 1982 ([9]) that certain quantum mechanical effects cannot be simulated effectively on a classical computer. This observation led to a general idea that perhaps computation based on quantum effects could be much more efficient than the classic one. During the last decade the area of research of quantum computation was an intensively growing area. Shor’s quantum algorithm for factoring integers [15] that runs in polynomial time is well known now.

∗Max-Planck Institute for Mathematics, Bonn. Visiting from University of Kazan.

Supported in part by Russia Fund for Basic Research 99-01-00163 and Fund ”Russia Universities” 04.01.52. ablayev@ksu.ru

†Dept. of Computer Science, University of Kazan. Supported in part by Russia Fund for Basic Research 99-01-00163 and Fund ”Russia Universities” 04.01.52.aida@ksu.ru

‡Dept. of Computer Science, University of Bonn, and Mathematical Sciences Research Institute, Berkeley. Supported in part by DFG grants, DIMACS, IST grant 14036 (RAND-APX), and Max-Planck Research Prize. Research at MSRI was supported by NSF grant DMS-9810361. marek@cs.uni-bonn.de

As mentioned in [4] quantum computers may consist of two parts: a quantum part and a classical part with communication between them. In such a case, a quantum part could be considerably more expensive than the classical part. Therefore, it might be useful to construct a quantum part as simple as possible. This motivates a study of restricted models of quantum computation.

During the last decade many different restricted quantum computation models have been investigated. In particular the quantum analogs of Boolean circuitsNC and ACC [13, 8] has been introduced. Another model — quantum finite automata has been introduced and first studied by Kondacs and Watrous [12], see [7] for more information on the subject. It has been shown that uniform one-way quantum finite automata with bounded error probability cannot accept all regular languages [12]. But Ambainis and Freivalds [4] presented a regular language which can be computed by a quantum finite automaton with bounded error probability of exponentially smaller size than the corresponding classical randomized finite automaton. One of the more recent papers comparing classical and restricted quantum computation models is [16].

A classical branching program (BP)(see, e.g., [17]) is a convenient nonuniform model for studying various restricted variants of computational models. Leveled oblivious permutation BPs are well known in the complexity theory, their computational power is remarkable (deterministic leveled oblivious permutation BPs with constant width have the same power as log n depth circuits [6]). It seems also that the branching programs are well suited for comparing restricted quantum models with their classical counterparts.

Nakanishi, Hamaguchi, and Kashiwabara introduced also in [14] a variant of quantum model of BPs as an extension of probabilistic BPs. In this paper we introduce a model of quantum BPs different from that of [14]. Without loss of generality we consider leveled BPs. For a leveled BP P, all the paths in a BP are of the same length, and one can move only from the nodes of the i-th level to the nodes of the i + 1-th level. We denote by w(P) a width of P. That is, w(P) is a maximum number of nodes on various levels of P. In our case a superposition of P is any element |ψ⟩ = ∑_{i=1}^{w(P)} z_{i}|q_{i}⟩. We notice that we may need much less quantum bits than in a model of [14].

In ths paper we investigate a restricted computational variant of a quantum branching program— a quantum read-once BP. First we show that a read-once (exact) quantum BPs (noting that the obliviousness is inherent in a quantum nature of such programs) 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 on any (classical) randomized read-once BP with permanent transitions at each level. We present a general lower bound for the width of read-once QBPs, showing that the upper bound for a considered symmetric function is almost tight.

2 Preliminaries and Definitions

We consider a d-dimensional Hilbert complex space H^{d} with a norm ||.||.

That is, for z ∈ H^{d}, z = \{z_{1}, …, z_{d}\}, ||z|| = \sqrt{∑_{i=1}^{d} |z_{i}|^{2}}.

Recall some basic notations from the quantum mechanics. A pure quantum state (or superposition) of a quantum system QS with d stable states {1, …, d} (d-state QS) can be expressed by associating an amplitude z_{i} (a complex number) to each state i of a QS. Quantum mechanics uses for that the following notations. Consider the quantum basis states {|1⟩, …, |d⟩} where {|i⟩} is the set of d-dimensional orthogonal basis vectors of H^{d} where |i⟩ denotes the unit vector with the value 1 at i and 0 elsewhere. A pure quantum state or a configuration of a QS can be written as

|ψ⟩ = ∑_{i=1}^{d} z_{i}|i⟩

or just |ψ⟩ = (z_{1}, …, z_{d}) where |ψ⟩ ∈ H^{d}. The specific notation |ψ⟩ corresponds to the Dirac ’ket’-notation for a column-vector (z_{1}, …, z_{d}). An element z_{i} of |ψ⟩ is called an amplitude of the basis state |i⟩ of a QS, and |z_{i}|^{2} is the probability of finding a QS in the state i when QS is beeing measured.

A time evolution of configurations of a QS in discrete steps is reversible and conveniently expressed using Heisenberg’s matrix mechanics. That is, if in a current step a configuration of a QS is |ψ⟩, then in the next step a configuration of a QS would be |ψ′⟩ where |ψ′⟩ = U|ψ⟩ and U is a d × d unitary matrix.

We are going to define now a quantum transformation as follows. Let X = {x_{1}, …, x_{n}} be a set of Boolean variables. Define quantum transformation (d-dimensional quantum transformation) on |ψ⟩ ∈ H^{d} as a triple ⟨j, U(0), U(1)⟩ where j is the index of a variable x_{j} ∈ X, and U(0), U(1) are reversible transformations of H^{d} presented by unitary d × d matrices. A quantum transformation ⟨j, U(0), U(1)⟩ of |ψ⟩ acts as follows: U|ψ⟩ = |ψ′⟩. If x_{j} = 1 then U = U(1) else U = U(0).

2.1 Definition of a QBP

A Quantum Branching Program of width d and length l ((d, l)-QBP) based on a QS is defined by a triple

P = ⟨T, |ψ_{0}⟩, F ⟩

where T is a sequence (of length l) of d-dimensional quantum transformations of a d-state QS:

T = (⟨j_{i}, U_{i}(0), U_{i}(1)⟩)_{i=1}^{l},

with |ψ(0)⟩ an initial configuration of P, and F ⊆ {1, …, d} a set of accepting states.

We define a computation of P over an input σ = σ_{1}, …, σ_{n} ∈ {0, 1}^{n} as follows:

1. Computation of P starts from the superposition |ψ_{0}⟩. On the i-th step, 1 ≤ i ≤ l, P transforms a superposition |ψ⟩ to a superposition |ψ′⟩ = U_{i}(σ_{j_{i}})|ψ⟩.

2. After the l-th (last) step of a quantum transformation, P measures its configuration |ψ_{σ}⟩ where |ψ_{σ}⟩ = U_{l}(σ_{i_{l}})U_{l−1}(σ_{i_{l−1}}) … U_{1}(σ_{i_{1}})|ψ_{0}⟩. The measurement is presented by a diagonal zero-one projection matrix M where M_{ii} = 1 if i ∈ F and M_{ii} = 0 if i ∉ F. The probability p_{accept}(σ) of P accepting an input σ is defined by

p_{accept}(σ) = ||M|ψ_{σ}⟩||^{2}.

We call a QBP P read-once, if each variable x ∈ {x_{1}, …, x_{n}} occurs in a sequence T of quantum transformations of P at most once.

2.2 Computation of a Boolean Function

• A QBP P is said to compute (with an unbounded error) a Boolean function f_{n} : {0, 1}^{n} → {0, 1} if for all σ ∈ f^{−1}(1) the probability of P accepting σ is greater than 1/2 and for all σ ∈ f^{−1}(0) the probability of P accepting σ is at most 1/2.

• A QBP P computes a Boolean function f_{n} with a bounded error if there exists an ε > 0 such that for all σ ∈ f^{−1}(1) the probability of P accepting σ is at least 1/2 + ε and for all σ ∈ f^{−1}(0) the probability of P accepting σ is at most 1/2 − ε. We call ε a margin, and say that P (1/2 + ε)-computes f_{n}.

• We say that a QBP P exactly computes f_{n} if P computes f_{n} with the margin 1/2 (with the zero error probability).

3 Computational Properties

The following property of a simulation of QBPs with complex valued amplitudes by QBPs with real valued amplitudes is similar to simulations by quantum Turing machines cf. [5].

Property 1 Let a (d, l)-QBP P with complex valued amplitudes computes (with an unbouded error, with a bounded error, exactly) a function f_{n}. Then, there exists a (2d, l)-QBP P′ with real amplitudes within the interval [−1, +1] that computes (with an unbouded error, with a bounded error, exactly, respectively) the same function f_{n}.

Proof: Let us consider a product U|ψ⟩ of a complex valued d×d matrix U

U = ( \begin{matrix}z_{1,1} & … & z_{1,d} \\ ⋮ & & ⋮ \\ z_{d,1} & … & z_{d,d} \end{matrix} )

where z_{i,j} = a_{i,j} + \sqrt{−1}b_{i,j}, with a d-dimensional complex valued vector |ψ⟩

|ψ⟩ = ( z_{1} ; ⋮ ; z_{d} )

where z_{i} = a + \sqrt{−1}b_{i}. The above product can be simulated by a product of a A|v⟩ of 2d × 2d real valued matrix A

A = ( \begin{matrix}Z_{1,1} & … & Z_{1,d} \\ ⋮ & & ⋮ \\ Z_{d,1} & … & Z_{d,d} \end{matrix} )

where Z_{i,j} = ( \begin{matrix}a_{i,j} & b_{i,j} \\ −b_{i,j} & a_{i,j} \end{matrix} ) is matrix presentation of the complex num-

ber z_{i,j}, and |v⟩ is a 2d-dimensional real valued vector

|v⟩ = ( a_{1} ; b_{1} ; ⋮ ; a_{d} ; b_{d} )

We notice that all amplitudes z in superpositions |ψ⟩ of P are such that the real a and imaginary b part of z = a + \sqrt{−1}b are from intervals [−1, +1]. From the above it is easy to conclude that a d-dimensional l-length complex valued quantum transformations of a d-state QS

(⟨j_{i}, U_{i}(0), U_{i}(1)⟩)_{i=1}^{l},

can be simulated by the corresponding 2d-dimensional l-length real valued quantum transformations of a 2d-state QS

(⟨j_{i}, A_{i}(0), A_{i}(1)⟩)_{i=1}^{l}.
□

Below we show that a bounded error read-once QBPs are powerful enough to compute an arbitrary Boolean function. By contrast, we notice thati the uniform one-way quantum finite automata when accepting with a bounded error probability can compute only a proper subset of regular sets [12]. See also [7] for more recent results on the complexity properties of quantum finite automata.

Property 2 For arbitrary Boolean function f_{n}, there exists a read-once (2^{n}, n)-QBP that exactly computes f_{n}.

Proof: The proof is evident. The following read-once (2^{n}, n) − QBP P satisfies our 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. The 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 change. 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 by 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. □

Denote by EP-QBP_{const} the class of all Boolean functions exactly computed by the constant width and polynomial length (in the number of function variables) QBPs.

Property 3 For the complexity class NC^{1} it holds that

NC^{1} ⊆ EP-QBP_{const}.

Proof: Proof is evident by a known result of Barrington [6]. Having a permutation deterministic branching program P of width 5 computing a Boolean function f_{n} it is easy to construct a (const, poly)-QBP P′ which exactly computes f_{n}. □

Consider now 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 1 The function MOD_{p_{n}} can be computed by a read-once (O(log p_{n}), n)- QBP with a one-sided error probability.

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

The proof is similar to that of [4]. [4] introduces the following regular set L_{P}. For a prime p, a language L_{p} over a single letter alphabet is defined by L_{p} = {u : |u| is divisible by p}. It is proved that for any ε > 0, there is a QFA with O(log p) states recognizing L_{p} with probability 1 − ε.

We construct a QBP P accepting the inputs σ ∈ MOD_{p_{n}}^{−1}(1) with the probability 1 and rejecting the inputs σ ∈ MOD_{p_{n}}^{−1}(0) with the probability at least 1/8. Consider a (2, n)-1QBP P^{k} for k ∈ {1, …, p_{n} −1}. A quantum program P^{k} = ⟨T^{k}, |ψ_{0}^{k}⟩, F^{k}⟩ is based on the following 2-state quantum system, 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 1 ([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 a 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 QBPs P^{k} accept inputs σ ∈ f_{n,p_{n}}^{−1}(1) with probability 1.

Following [4], we call P^{k} ”good” for input σ ∈ MOD_{p_{n}}^{−1}(0) if P^{k} rejects σ with probability at least 1/2.

Lemma 2 For any σ ∈ MOD_{p_{n}}^{−1}(0), at least (p_{n}−1)/2 of all P^{k} are “good”.

Proof: According to Lemma 1, 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, and 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 a half of the circumference, we have |I| ≥ ⌊p_{n}/2⌋ ≥ (p_{n} − 1)/2.

□

Following [4], 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 3 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 the following procedure A for a construction of a set S.

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

The probability of selecting a “good” QBP at each step is at least 1/2. Using Chernoff inequality, we have that 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 a constructed 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 exists a set which is “good” for all inputs σ with l(σ) ≤ p_{n} − 1. This set is “good” for the inputs σ with l(σ) > p_{n} as well, since any QBP P^{k} returns a current superposition of a starting superposition after reading all p_{n} ones, and hence it 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. A 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 have equal amplitudes.

The inputs σ ∈ MOD_{p_{n}}^{−1}(1) are always accepted with the probability 1 because all the 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 a standard technique for reducing an error probability for a one-sided error computation. That is, we take d = d(ε) copies of such a 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 do not depend on the level of P.

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

Corollary 1 The function MOD_{p_{n}} can be computed by a stable read-once (O(log p_{n}), n)-QBP with a one-sided error.

Below we show that MOD_{p_{n}} function is hard, in fact, for the randomized OBDDs.

3.2 Lower Bound for Randomized OBDDs for MOD

Randomized OBDDs were introduced and firstly investigated in [1], see also [17].

Theorem 2 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 assume without loss of generality that each level of P has exactly q nodes. Let μ^{j} = (μ_{1}^{j}, …, μ_{q}^{j}) be a probability distribution of states of P on the j-th level, where μ_{i}^{j} is the probability of being in the i-th node of the j-th level. We can describe a computation of P on an input σ̃ = σ_{1}, …, σ_{n} as follows:

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

• At the j-th step, 1 ≤ j ≤ n, P reads an input σ_{i_{j}} and transforms a vector μ^{j−1} to μ^{j} = μ^{j−1}A, where A is a 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 the 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 without loss of generality that P reads inputs in the natural order x_{1}, …, x_{n}. 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 by μ^{i} a 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. The states of this Markov chain are either ergodic or transient cf., e.g., [11]. An ergodic set of states is a 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 no interaction between these sets. Hence we have two or more unrelated Markov chains lumped together. Those chains can be studied separately. If a Markov chain consist of a single ergodic set, then the chain is called an ergodic chain. According to the usual classification, every ergodic chain is either regular or cyclic.

If an ergodic chain is regular, then a sufficiently high power of a state transition matrix A has only positive elements. Thus no matter where the process starts, after a sufficient 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 which do not dependent on the initial state.

If a Markov chain is cyclic, then a 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 known that after the sufficient time elapsed, the process can be in any state of a cyclic subset appropriate at the given moment. Hence for each of t cyclic subsets, the t-th power of a state transition matrix A^{t} describes a regular Markov chain. Moreover, if an ergodic chain is a cyclic chain with a period t, it has at least t states.

From the assumption q < p_{n} in the proof, we get that t < p_{n} for every cyclic chain. We denote by 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 power 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 the probability of being in accepting state after reading the input σ̃_{k}^{1}. Since after every D steps a process can be in any state comprising an accepting state, D-th power of matrix A describes a regular Markov chain for that set. From the theory of Markov chains we have that there exists α_{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 that α_{acc}^{D^{m}p_{n}} ≥ 1/2 + ε and α_{acc}^{D^{m}} ≤ 1/2 − ε, a contradiction with the inequality above.

□

4 Lower Bounds

Below we present a general lower bound on the width of 1QBPs and compare it with the width of deterministic OBDDs computing the same function.

Theorem 3 Let ε ∈ (0, 1/2). Let f_{n} be a Boolean function which is (1/2 + ε)-computed (computed with a margin ε) by a 1QBP Q. Then it holds that

width(Q) = Ω (\frac{log width(P)}{log log width(P)})

where P is a deterministic OBDD of minimal width which computes f_{n}.

The next theorem presents a more precise lower bound for a particular margin ε of computation.

Theorem 4 Let ε ∈ (3/8, 1/2). Let f_{n} be a Boolean function which is (1/2 + ε)-computed (computed with a margin ε) by a 1QBP Q. Then it holds that

width(Q) = Ω (\frac{log width(P)}{2 log(1 + 1/τ)})

where P is a deterministic OBDD of minimal width computing f_{n} and τ = \sqrt{1 + 2ε − 4\sqrt{1/2 − ε}}.

Proofs of the above theorems are presented in the section below.

4.1 Proofs of Theorems 3 and 4

Proofs of Theorems 3, and 4 use a similar idea. We construct a deterministic OBDD P that computes the same function f_{n} and

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

Proofs of Theorems 3, 4 differ only in an estimation of a parameter θ > 0 depending on ε.

4.1.1 A Deterministic OBDD-Presentation of a 1QBP

Let d = width(Q). Let π = {i_{1}, i_{2}, …, i_{n}} be an ordering of testing variables of Q. From now on we assume that the input sequences σ ∈ {0, 1}^{n} are ordered by an order π determined by Q. We define a deterministic OBDD LQ based on Q as follows. LQ use the ordering π of testing variables represented by the following labeled complete binary tree.

• The initial node of LQ is marked by an initial configuration |ψ_{0}⟩ of Q. Two outgoing vertices of the initial node are marked by x_{i_{1}} = 1 and x_{i_{1}} = 0.

• Two nodes of LQ on the level 1 are marked by the configurations |ψ_{1}(0)⟩ and |ψ_{1}(1)⟩ of Q where |ψ_{1}(σ_{1})⟩ is the configuration after the first step of computation after reading x_{i_{1}} = σ_{1} for σ_{1} ∈ {0, 1}.

A vertex x_{i_{1}} = σ_{1} leads from the node |ψ_{0}⟩ to the node |ψ_{1}(σ_{1})⟩ iff |ψ_{1}(σ_{1})⟩ = U_{1}(σ_{1})|ψ_{0}⟩.

• Consider a level j of LQ. 2^{j} nodes of LQ of the level j are marked by the configurations {|ψ_{j}(σ_{1} … σ_{j})⟩ ∈ Ψ : σ_{1} … σ_{j} ∈ {0, 1}^{j}} where |ψ_{j}(σ_{1} … σ_{j})⟩ is a configuration of Q after reading the first part σ_{1} … σ_{j} of the input σ ∈ {0, 1}^{n}.

A vertex (marked by x_{i_{j+1}} = σ_{j+1}) from the node |ψ_{j}(σ_{1} … σ_{j})⟩ leads

to the node |ψ_{j+1}(σ_{1} … σ_{j}σ_{j+1})⟩ iff |ψ_{j+1}(σ_{1} … σ_{j}σ_{j+1})⟩ = U_{j+1}(σ_{j+1})|ψ_{j}(σ_{1} … σ_{j})⟩.

• Consider the last level n of LQ. We mark 2^{n} nodes of LQ on the level n by the configurations |ψ_{n}(σ_{1} … σ_{n})⟩ ∈ Ψ : (σ_{1} … σ_{n}) ∈ {0, 1}^{n} and in addition we mark them by 0 and 1 as follows. We mark node |ψ_{n}(σ_{1} … σ_{n})⟩ by 1 if for configuration |ψ_{n}(σ_{1} … σ_{n})⟩ it holds that p_{accept}(σ_{1} … σ_{n}) ≥ 1/2 + ε. We mark a node |ψ_{n}(σ_{1} … σ_{n})⟩ by 0 if for configuration |ψ_{n}(σ_{1} … σ_{n})⟩ it holds that p_{accept}(σ_{1} … σ_{n}) ≤ 1/2 − ε.

Property 4 A deterministic OBDD LQ computes the same Boolean function f_{n} as Q.

Proof: Evident and follows from the construction of LQ. □

4.1.2 A Metric Automaton Characterization of LQ

We view now an OBDD LQ with an ordering π of testing variables as the following metric time-variant automaton that reads its input sequences σ ∈ {0, 1}^{n} in an order π:

LQ = ⟨{0, 1}, Ψ, {δ_{j}}_{j=1}^{n}, |ψ_{0}⟩, F_{ε}⟩

where {0, 1} is the input alphabet, Ψ = {|ψ⟩} is a set of states (set of all possible configurations of Q during its computations on inputs from {0, 1}^{n}). That is, Ψ = ∪_{j=0}^{n}Ψ_{j} where Ψ_{j} is a set of states of LQ on the level j. An automaton transition function δ_{j} : Ψ_{j−1}×{0, 1} → Ψ_{j} determines transitions in the step j, 1 ≤ j ≤ n, (δ_{j} is defined according to the transitions of LQ in the level j − 1). Finally |ψ_{0}⟩ is the initial state and F_{ε} = {|ψ⟩ ∈ Ψ_{n} : ||M|ψ⟩||^{2} ≥ 1/2 + ε} is the accepting set of states of LQ.

For j ∈ {1, …, n}, we denote by Δ_{j} : Ψ_{j−1} × {0, 1}^{n−j+1} → Ψ_{n} the automaton transitive closure of the sequence δ_{j}, …, δ_{n} of the transition functions. That is,

Δ_{j}(|ψ⟩, σ_{j} … σ_{n}) = δ_{n}(… (δ_{j}(|ψ⟩, σ_{j}), …, σ_{n}).

Lemma 4 Let f_{n} be a Boolean function (1/2 + ε)-computed by a LQ. Let θ > 0, and for arbitrary |ψ⟩ ∈ F_{ε} and arbitrary |ψ⟩′ ∈ Ψ_{n}\F_{ε} it holds that

|| |ψ⟩ − |ψ′⟩ || ≥ θ.

Then, there exists a deterministic OBDD B which computes f_{n} and

width(B) ≤ (1 + \frac{2}{θ})^{2d} .

Proof: We recall first some known notions concerning metric spaces (see [3]). A Hilbert space H_{d} is a metric space with a metric defined by the norm ||·||. The points μ, μ′ from H_{d} are connected through a θ-chain if there exists a finite set of points μ_{1}, μ_{2}, …, μ_{m} from H_{d} such that μ_{1} = μ, μ_{m} = μ′ and ||μ_{i} − μ_{i+1}|| ≤ θ for i ∈ {1, …, m − 1}. A subset C of H_{d} is called a θ-component if arbitrary two points μ, μ′ ∈ C are connected through a θchain. It is known [3] that if D is a finite diameter subset of a subspace of H_{d} (a diameter of D is defined as sup_{μ,μ′∈D}{||μ − μ′||} then for θ > 0 D is partitioned to a finite number t of its θ-components.

A set Ψ of states of LQ belongs to the sphere of radius 1 which has center (0, 0, …, 0) in H_{d} because for all |ψ⟩ ∈ Ψ it holds that || |ψ⟩ || = 1. For each j ∈ {0, …, n}, denote by [Ψ_{j}] = {C_{1}, …, C_{t_{j}}} the set of θ-components of Ψ_{j} ⊂ H_{d}.

From the condition of our Lemma it follows that a subset F_{ε} of Ψ_{n} is a union of some θ-components of Ψ_{n}. The transition functions δ_{j}, 1 ≤ j ≤ n, preserve the distance. That is, for arbitrary |ψ⟩ and |ξ⟩ from Ψ_{j} and arbitrary γ ∈ {0, 1}, it holds that

|| |ψ⟩ − |ξ⟩ || = ||δ_{j}(|ψ⟩, γ) − δ_{j}(|ξ⟩, γ)||.  (2)

From (2) we have that for C ∈ [Ψ_{j}] and for γ ∈ {0, 1} there exists C′ ∈ [Ψ_{j+1}] such that δ_{j}(C, γ) = C′. Here δ_{j}(C, γ) is defined as δ_{j}(C, γ) = ∪_{|ψ⟩∈C}δ_{j}(|ψ⟩, γ).

Now we describe a deterministic OBDD B in terms of a time-variant finite automaton that computes f_{n}.

B = ⟨{0, 1}, [Ψ], {δ_{j}}_{j=1}^{n}, C_{0}, F ⟩

where [Ψ] = ∪_{j=0}^{n}[Ψ_{j}] is a set of states of B ([Ψ_{j}] is a set of states on the step j of a computation of B); δ_{j} : [Ψ_{j−1}] × {0, 1} → [Ψ_{j}] is a transition function of B in the step j; an initial state C_{0} = {|ψ_{0}⟩} is a one-element θ-component of Ψ_{0}; we define F by F = {C_{i} ∈ [Ψ_{n}] : C_{i} ⊆ F_{ε}}.

From our construction we have that B and LQ compute the same function f_{n}. The width of B is t = max{t_{0}, …, t_{n}}.

Let t = t_{j} We estimate a number t of θ-components (number of states of B) of Ψ_{j} as follows. For each θ-component C, we 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 spheres (t many) are in a larger sphere of radius 1 + θ/2 which has center (0, 0, …, 0). The volume of a sphere of radius r in H_{d} is cr^{2d}, where the constant c depends on a metric of H_{d}. Note that for estimating the volume of the sphere we should take into account that H_{d} is a d-dimensional complex space and each complex point is a 2-dimensional point. So it holds that

width(B) ≤ \frac{c (1 + θ/2)^{2d}}{c (θ/2)^{2d}} = (1 + \frac{2}{θ})^{2d} .

□

Below we formulate a technical lemma that estimates a number of components of Ψ for different ε.

Lemma 5 Let an LQ (1/2+ε)-computes a function f_{n}. Then for arbitrary |ψ⟩ ∈ F_{ε} and arbitrary |ψ′⟩ ∉ F_{ε} it holds that

1. || |ψ⟩ − |ψ′⟩ || ≥ θ_{1} = ε/\sqrt{d}

and

2. || |ψ⟩ − |ψ′⟩ || ≥ θ_{2} = \sqrt{1 + 2ε − 4\sqrt{1/2 − ε}}.

Proof: For the sake of simplification we denote a configuration |ψ⟩ = z_{1}|1⟩ + ⋯ + z_{d}|d⟩ just by ψ = (z_{1}, …, z_{d}). Let ψ = (z_{1}, …, z_{d}) and ψ′ = (z′_{1}, … z′_{d}). Consider a norm ||.||_{1} defined as ||ψ||_{1} = ∑_{i=1}^{d} |z_{i}|.

1. From the definition of LQ it holds that

2ε ≤ ∑_{s_{i}∈F} (|z_{i}|^{2} − |z′_{i}|^{2}) = ∑_{s_{i}∈F} (|z_{i}| − |z′_{i}|)(|z_{i}| + |z′_{i}|) ≤

≤ 2 ∑_{s_{i}∈F} (|z_{i}| − |z′_{i}|) ≤ 2 ∑_{s_{i}∈F} |z_{i} − z′_{i}| ≤ 2||ψ − ψ′||_{1}

Using an inequality

a_{1}b_{1} + a_{2}b_{2} + ... + a_{d}b_{d} ≤ \sqrt{a_{1}^{2} + a_{2}^{2} + ... + a_{d}^{2}}\sqrt{b_{1}^{2} + b_{2}^{2} + ... + b_{d}^{2}}, (3)

for b_{1} = b_{2} = … = b_{d} = 1 we get that ||ψ||_{1} ≤ \sqrt{d}||ψ||. Therefore,

2ε ≤ 2||ψ − ψ′||_{1} ≤ 2\sqrt{d}||ψ − ψ′||

Finally, we have

||ψ − ψ′|| ≥ ε/\sqrt{d}.

2. Consider now the next variant of a lower bound for ||ψ − ψ′||.

||ψ − ψ′|| = \sqrt{∑_{i=1}^{d} |z_{i} − z′_{i}|^{2}} ≥ \sqrt{∑_{i=1}^{d} (|z_{i}| − |z′_{i}|)^{2}} =

= \sqrt{∑_{i=1}^{d} |z_{i}|^{2} + ∑_{i=1}^{d} |z′_{i}|^{2} − 2 ∑_{i=1}^{d} |z_{i}||z′_{i}|} ≥

≥ \sqrt{∑_{s_{i}∈F} |z_{i}|^{2} + ∑_{s_{i}∉F} |z′_{i}|^{2} − 2 ∑_{s_{i}∈F} |z_{i}||z′_{i}| − 2 ∑_{s_{i}∉F} |z_{i}||z′_{i}|}.

From the definition of an LQ we have that ∑_{s_{i}∈F} |z_{i}|^{2} ≥ 1/2 + ε, ∑_{s_{i}∉F} |z′_{i}|^{2} ≥ 1/2 + ε. Now, from the above we get that

||ψ − ψ′|| ≥ \sqrt{1/2 + ε + 1/2 + ε − 2 ∑_{s_{i}∈F} |z_{i}||z′_{i}| − 2 ∑_{s_{i}∉F} |z_{i}||z′_{i}|}.

Using inequality (3) we get

||ψ − ψ′|| ≥ \sqrt{1 + 2ε − 2\sqrt{∑_{s_{i}∈F} |z_{i}|^{2}}\sqrt{∑_{s_{i}∈F} |z′_{i}|^{2}} − 2\sqrt{∑_{s_{i}∉F} |z_{i}|^{2}}\sqrt{∑_{s_{i}∉F} |z′_{i}|^{2}}}.

Using the property ∑_{s_{i}∉F} |z_{i}|^{2} ≤ 1/2−ε, ∑_{s_{i}∈F} |z′_{i}|^{2} ≤ 1/2−ε, ∑_{s_{i}} |z_{i}|^{2} ≤ 1, and ∑_{s_{i}} |z′_{i}|^{2} ≤ 1, we finally get that

||ψ − ψ′|| ≥ \sqrt{1 + 2ε − 4\sqrt{1/2 − ε}} = θ_{2}.
□

Note that the lower bound above for ||ψ − ψ′|| is nontrivial (positive) if ε ∈ (α, 1/2) where α is about 3/8. For ε ∈ (0, α] it holds that 1 + 2ε − 4\sqrt{1/2 − ε} ≤ 0. In that case the lower bound ||ψ − ψ′|| ≥ ε/\sqrt{d} is more precise.

Now we turn to the formal estimations of the lower bounds of Theorems 3 and 4.

Proof of Theorem 3: From Lemma 4 and Lemma 5, it follows that

t ≤ (1 + \frac{2\sqrt{d}}{ε})^{2d}

or log t = O(d log d). From that we get that

d = Ω (\frac{log t}{log log t}) .

Proof of Theorem 4: From Lemma 4 and Lemma 5, it follows that

t ≤ (1 + \frac{2}{θ_{2}} )^{2d}

or 2d ≥ log t/ log(1 + 2/θ_{2}). From this we have that

d ≥ \frac{log t}{2 log(1 + 1/θ_{2})}.

□

References

[1] F. Ablayev and M. Karpinski, On the Power of Randomized Branching programs, Electronic Colloquium in Computational Complexity, ECCC TR98-004, (1998), available at

http://www.eccc.uni-trier.de/eccc/ , also appeared in Proc.

28th ICALP (1996), LNCS Vol. 1099, Springer, 1996, 348-356.

[2] F. Ablayev and M. Karpinski, A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs, ECCC TR98-011

(1998), available at http://www.eccc.uni-trier.de/eccc/.

[3] P. Alexandrov, Introduction to Set Theory and General Topology, Berlin, 1984.

[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] Bernstein and Vazirany, Quantum Complexity Theory, SIAM J. Comput, Vol. 26, No. 5, (1997), 1411-1473. Preliminary version of this paper appeared in Proc. 25th STOC, (1993), 11-20.

[6] D. Barrington, Bounded-width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC^{1}, Journal of Comp. and System Sci. 38, (1989), 150-164.

[7] A.Brodsky and N.Pippenger. Characterization of 1-Way Quantum Finite Automata. quant-ph/9903014, available at

http://xxx.lanl.gov/archive/quant-ph. See also its Russian
mirror: http://xxx.itep.ru.

[8] F. Green, S. Homer, and Pollet, On the Complexity of Quantum ACC, in Proc. of the 15th IEEE Conf. on Computational Complexity 2000.

[9] R. Feynman, Simulation Physics with Computers, International Journal of Theoretical Physics, (1982), 21, 467.

[10] R. Freivalds, Quantum Finite Automata, Manuscript 2000, personal communication.

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

[12] A.Kondacs and J.Watrous. On the Power of Quantum Finite State Automata. In proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, 66-75.

[13] C. Moore and M. Nilson, Some Notes on Parallel Quantum Computing, quant ph/9804034.

[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, in the proceedings of the 6th Annual International Conference on Computing and Combinatorics, COCOON’2000, Lecture Notes in Computer Science, Springer-Verlag, v. 1858, (2000), 467-476.

[15] P. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. on Computing, 26(5), (1997), 1484-1509.

[16] B.C. Travaglione, M.A. Nielsen, H.M. Wiseman, and A. Ambainis, ROM-based computation: quantum versus classical, arXiv: quantph/0109016 4 Sep 2001.

[17] I. Wegener, Branching Programs and Binary Decision Diagrams. Siam Monographs on Discrete Mathematics and Applications. 2000.