Vorlesung im Wintersemester 2002/2003

Quantenalgorithmen

(Prof. Dr. Th. Beth, Dr. M. Rötteler, Dr. M. Grassl)

Quantenrechner eröffnen im Vergleich zu klassischen Berechnungsmodellen neue Möglichkeiten für den Algorithmenentwurf. Allen voran sind als Beispiele der Algorithmus von Shor zur Faktorisierung ganzer Zahlen in polynomialer Zeit sowie der Algorithmus von Grover zur Urbildsuche zu nennen.

Unitäre Transformationen, wie etwa die diskrete Fouriertransformation, spielen eine wichtige Rolle beim Entwurf von Quantenalgorithmen. In dieser zweistündigen Vorlesung werden daher, ausgehend von einer Einführung in das Modell der Quantenschaltkreise, Quantenalgorithmen unter anderem aus dem Blickwinkel schneller Signaltransformationen betrachtet. Ein Ergebnis, das sich unter Verwendung solcher Transformationen gewinnen lässt, ist die Trennung der Komplexitätsklassen BPP und BQP bezüglich geeignet gewählter Orakel.

Die prüfbare Vorlesung wendet sich an Studierende im Hauptstudium der Fachrichtungen Informatik, Mathematik, Physik und Elektrotechnik. Kenntnisse aus den Vorlesungen Quanten-Codierungstheorie oder Quantencomputing sind hilfreich, aber nicht Voraussetzung. Die erforderlichen Grundlagen aus den Bereichen Quantenmechanik, Fouriertransformationen endlicher Gruppen und Quantum Computing werden in der Vorlesung vermittelt.


Vorlesungen

Materialien zur Vorlesung (Kopien von Artikeln etc.) gibt es in Zimmer 272, Neubau Informatik.

Literatur

allgemeine Einführungen zum Thema Quantum Computing


Weitere Informationen bei:


Vorlesungsverzeichnis (I3V): Link auf diese Vorlesung
Diese Seite wird betreut von
Markus Grassl (grassl@ira.uka.de), IAKS, Arbeitsgruppe Quantum Computing, Fakultät für Informatik, Universität Karlsruhe
Letzte Änderung: 11.02.2003