Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2007 Copyright 2007 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope