05.12.2007

We consider the problems of computing certain types of boolean functions which we call Equality, Semi-Simon and Periodicity functions. For all these problems, we prove linear lower complexity bounds on oblivious Ordered Read-Once Quantum Branching Programs (quantum Ordered Binary Decision Diagrams). We present also two different approaches to prove existence of efficient quantum branching programs for those boolean functions matching the lower complexity bounds.