Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2007 Copyright 2007 University of Bonn, Department of Computer Science, Abt. V
85285

05.12.2007

Complexity of Computing Functions by Quantum Branching Programs
Farid Ablayev, Marek Karpinski and Airat Khasianov
[Download PostScript] [Download PDF]

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.

Last Change: 12/05/07 at 14:05:03
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V