Quantum vs. Classical Read-once Branching Programs

Simple item page
dc.creatorSauerhoff, Martin
dc.date2005-04-26
dc.date2005-09-23
dc.date.accessioned2026-07-07T06:18:54Z
dc.date.available2026-07-07T06:18:54Z
dc.descriptionThe 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^{Ω(n)}. (ii) Quantum branching programs reading each input variable exactly once are shown to require size 2^{Ω(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.
dc.description35 pages. Lower bound for disjointness: Error in application of info theory corrected and regularity of quantum read-once BPs (each variable at least once) added as additional assumption of the theorem. Some more informal explanations added
dc.identifierhttps://arxiv.org/abs/quant-ph/0504198
dc.identifierhttp://arxiv.org/abs/quant-ph/0504198
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/94894
dc.subjectQuantum Physics
dc.titleQuantum vs. Classical Read-once Branching Programs
dc.typetext

Files

Collections

arXiv