Physics – Quantum Physics
Scientific paper
2005-04-26
Physics
Quantum Physics
35 pages. Lower bound for disjointness: Error in application of info theory corrected and regularity of quantum read-once BPs
Scientific paper
The paper presents the first nontrivial upper and lower bounds for (non-oblivious) quantum read-once branching programs. It is shown that the computational power of quantum and classical read-once branching programs is incomparable in the following sense: (i) A simple, explicit boolean function on 2n input bits is presented that is computable by error-free quantum read-once branching programs of size O(n^3), while each classical randomized read-once branching program and each quantum OBDD for this function with bounded two-sided error requires size 2^{\Omega(n)}. (ii) Quantum branching programs reading each input variable exactly once are shown to require size 2^{\Omega(n)} for computing the set-disjointness function DISJ_n from communication complexity theory with two-sided error bounded by a constant smaller than 1/2-2\sqrt{3}/7. This function is trivially computable even by deterministic OBDDs of linear size. The technically most involved part is the proof of the lower bound in (ii). For this, a new model of quantum multi-partition communication protocols is introduced and a suitable extension of the information cost technique of Jain, Radhakrishnan, and Sen (2003) to this model is presented.
No associations
LandOfFree
Quantum vs. Classical Read-once Branching Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum vs. Classical Read-once Branching Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum vs. Classical Read-once Branching Programs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-199807