Komplexitätstheorie und Quanten-Computer

WS 2009/10

Aktuelles

  • Die Übungsscheine für Studenten in Diplomstudiengängen können im Sekretariat des Lehrstuhls abgeholt werden..
  • Bitte melden Sie sich bis zum 28. Januar per E-Mail oder persönlich bei Prof. Grädel, um einen Prüfungstermin zu vereinbaren.
  • Das sechste Kapitel des Skripts ist vervollständigt.
  • Wenn Sie beabsichtigen am Übungsbetrieb teilzunehmen, beachten Sie bitte untenstehende Informationen.

Termine

Art Termin Ort   Veranstalter
V4 Mo 10:00 – 11:30 AH II ab 19. Oktober E. Grädel
Do 10:00 – 11:30 AH V ab 22. Oktober E. Grädel
Ü2 Mi 15:00 – 16:30 AH I ab 28. Oktober D. Fischer, T. Ganzow, B. Puchala

Übungsbetrieb

Die Übungsblätter stehen jeweils ab Montag auf dieser Webseite zum Download bereit. Sie können die Übungen in Gruppen von bis zu drei Studierenden bearbeiten und Ihre Lösungen bis zum darauffolgenden Montag in der Vorlesung abgeben oder bis spätestens 12 Uhr am Institut in den dafür vorgesehenen Kasten einwerfen.

Das erste Übungsblatt erscheint am Montag, den 26.10., die erste Übung findet bereits am Mittwoch, 28.10. statt.

Für Studierende in einem Diplomstudiengang ist das Vorrechnen von Übungsaufgaben Teil der Prüfungsleistung für den Erwerb eines Übungsscheins.

Übungen

Skript Complexity Theory

Skript Quantum Computing

Inhalt

Komplexitätstheorie

Die Komplexitätstheorie klassifiziert algorithmische Probleme aufgrund der zur ihrer Lösung benötigten Ressourcen (wie Rechenzeit, Speicherplatz, Hardware, ....). In der Vorlesung werden die wichtigsten Komplexitätsklassen für deterministische, nichtdeterministische, parallele und probabilistische Berechnungen behandelt. Von besonderer Bedeutung sind die Zusammenhänge zwischen verschiedenen Berechnungsmodellen und vollständige Probleme in den wichtigsten Komplexitätsklassen.

Quanten Computer

You have nothing to do but mention the quantum theory, and people will take your voice for the voice of science, and believe anything. (George Bernard Shaw)

Ziel der Entwicklung von Quanten-Computern ist es, quantenmechanische Effekte auszunutzen um nicht-klassische Rechnersysteme zu bauen. Es ist zwar noch nicht sicher, ob Quanten-Computer mit mehr als ein paar wenigen Qubits überhaupt je gebaut werden können, aber in der Theorie zumindest erlauben Quanten-Phänomene fundamental neue Formen von Berechnungen. So hat die in den letzten Jahren entwickelte Theorie interessante und zum Teil sehr überraschende Resultate ergeben.

Formale Modelle für Quanten-Computer sind Quanten-Turingmaschinen und Quantum Gate Arrays. Es handelt sich hier um probabilistische Berechnungsmodelle jedoch mit Interferenz von Konfigurationen sowie Übergangsregeln, die durch Wahrscheinlichkeitsamplituden anstelle von Wahrscheinlichkeiten spezifiziert werden. Wir werden diese Modelle analysieren und verschiedene Algorithmen für Quanten-Computer behandeln. Speziell werden wir das aufsehenerregende Resultat von P. Shor zeigen, dass mit Quanten-Computern beliebig große Zahlen in polynomialer Zeit in ihre Primfaktoren zerlegt werden können, ein Problem, das im klassischen Fall offen ist und auf dessen Schwierigkeit die heutigen Public-Key-Kryptosysteme basieren. Quanten-Computer könnten also solche Kryptosysteme brechen.

Because nature isn't classical, dammit... (Richard P. Feynman)

Literatur

Einführende Literatur Komplexitätstheorie

[1] D. P. Bovet and P. Crescenzi. Introduction to the theory of complexity. Prentice Hall, New York, 1994.
[2] C. Papadimitriou. Computational complexity. Addison-Wesley, 1994.
[3] K. R. Reischuk. Einführung in die Komplexitätstheorie. Teubner, Stuttgart, 1990.

Weiterführende Literatur Komplexitätstheorie

[1] P. Bürgisser, M. Clausen, and M. Shokrollahi. Algebraic Complexity Theory. Springer-Verlag, 1997.
[2] J. Balcazar, J. Diaz, and J. Gabarro. Structural complexity. Springer-Verlag, 1988.
[3] R. Downey and M. Fellows. Parametrized complexity. Springer-Verlag, 1999.
[4] R. Greenlaw, H. J. Hoover, and L. Ruzzo. Limits to parallel computation: P-completeness theory. Oxford University Press, 1995.
[5] J. Hartmanis. Feasible computations and provable complexity properties. SIAM, Philadelphia, 1978.
[6] N. Immerman. Descriptive complexity. Springer-Verlag, 1999.
[7] D. Johnson. Handbook of Theoretical Computer Science (J. V. Leeuwen, ed.). Elsevier Science Publishers B.V., 1990.
[8] K. Wagner and G. Wechsung. Computational complexity. Reidel, 1986.
[9] I. Wegener. Grenzen der Effizienz von Algorithmen. Springer-Verlag, Berlin u.a., 2003.
[10] I. Wegener. The complexity of Boolean functions. Teubner, Stuttgart, 198.

Literatur Quantum Computing

[1] J. Gruska. Quantum Computing. McGraw-Hill, 1999.
[2] M. Hirvensalo. Quantum Computing. Springer, 2001.
[3] N. D. Mermin. Quantum Computer Science: An Introduction. Cambridge University Press, 2007.
[4] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

Voraussetzungen

  • Grundbegriffe zur Berechenbarkeit und Komplexität
  • Lineare Algebra

Zuordnung

  • Mathematik (D): Reine Mathematik
  • Mathematik (B.Sc.): 5./6. Semester
  • Informatik (D): Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
  • Informatik (B.Sc.): Wahlpflicht Theoretische Informatik
  • Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science

Leistungsnachweis

  • Bachelor- und Masterstudiengänge: Lösen von 50% der Übungsaufgaben und Bestehen einer mündlichen Prüfung im Umfang von 30 Minuten
  • Diplomstudiengänge: Übungsschein bei Lösen von 50% der Übungsaufgaben und aktiver Teilnahme an den Übungen

Rückfragen

Erich Grädel, Diana Fischer, Tobias Ganzow, Bernd Puchala