Navigation

Springe zum Hauptinhalt
Fakultät für Informatik
Informatik-Kolloquien

119. Informatik-Kolloquium

Herr Sebastian Doern


Quantum Query Komplexität von algebraischen Eigenschaften




Mittwoch, 23.05.2007
14.00 Uhr, 1/Altes Heizhaus

Alle interessierten Personen sind herzlich eingeladen!


Abstract:

In diesem Vortrag werden neue Quantenalgorithmen für das Testen von algebraischen Eigenschaften vorgestellt. Für eine Menge S und eine binäre Operation auf S, betrachten wir die Entscheidungsprobleme ob S eine Semigruppe ist, oder ein Einselement besitzt. Falls S ein Monoid ist, wollen wir entscheiden ob S eine Gruppe bildet.
Wir präsentieren Quantenalgorithmen für diese Probleme, welche schneller sind als die besten klassischen Algorithmen. Wir stellen die erste Anwendung der neuen Quantum Random Walk Technik von Magniez, Nayak, Roland, and Santha vor.
Weiterhin geben wir untere Schranken für die Query Komplexität zum Testen algebraischer Eigenschaften an.

Der Vortrag basiert auf einer Arbeit, die ich gemeinsam mit Thomas Thierauf erstellt habe, und welche auf der FCT?07 präsentiert wird.

Presseartikel