Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
Preprint
Abstract
We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The "memoryless" term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. % As an application of communication complexity results, we consider Quantum Ordered Read-$k$-times Branching Programs ($k$-QOBDD). Our communication complexity result allows us to get lower bound for $k$-QOBDD and to prove hierarchies for sublinear width bounded error $k$-QOBDDs, where $k=o(\sqrt{n})$. Furthermore, we prove a hierarchy for polynomial size bounded error $k$-QOBDDs for constant $k$. This result differs from the situation with an unbounded error where it is known that an increase of $k$ does not give any advantage.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Functions computable by Boolean circuits of logarithmic depth and branching programs of a special typeJournal of Applied and Industrial Mathematics, 2008
- Lower bounds in communication complexity based on factorization normsRandom Structures & Algorithms, 2008
- On the computational power of probabilistic and quantum branching programInformation and Computation, 2005
- Quantum branching programs and space-bounded nonuniform quantum complexityTheoretical Computer Science, 2005
- Two-way finite automata with quantum and classical statesTheoretical Computer Science, 2002
- On Computational Power of Quantum Branching Programs2001
- Ordered Quantum Branching Programs Are More Powerful than Ordered Probabilistic Branching Programs under a Bounded-Width Restriction2000
- Quantum automata and quantum grammarsTheoretical Computer Science, 2000
- Hierarchy theorems for kOBDDs and kIBDDsTheoretical Computer Science, 1998
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Journal of Computer and System Sciences, 1989