Vorlesung: Mo 10-12, (SR
9); Do 12-14, (SR 9)
Übung: Di, 14-16 Raum 307 (ab 1.11., Dipl.
Math. Dirk Brendel)
Im "Quantum Computing" werden quantenmechanische
Berechnungsmodelle untersucht. Dieses Forschungsgebiet zwischen
Informatik und Physik geniesst weltweit grosse Aufmerksamkeit seit der
Entdeckung der Algorithmen von Shor zur effizienten Faktorisierung ganzer
Zahlen und von Grover zum schnellen Durchsuchen von Datenbanken.
In der Vorlesung sollen die Grundlagen quantenmechanischer Berechnungsmodelle
definiert, die wichtigsten Quantenalgorithmen erläutert, Techniken zum Beweis
unterer Schranken, sowie Elemente der Quantenkommunikation/kryptographie
beschrieben werden.
Ähnliche Veranstaltung im WS 04/05: QC04.html
Vordiplom Informatik erwünscht, Kenntnisse in linearer Algebra sind hilfreich
Fachgespräch
24.10./27.10: .pps
, .pdf, .ps
[Quantenmechanik, Qubits, Dirac Notation, unitäre Transformationen,
Parallelismus]
31.10.: .pps
, .pdf, .ps [Deutsch Algorithmus, Deutsch-Josza
Algorithmus, Observablen und Messungen]
3.11.: .pps
, .pdf, .ps [No Cloning, Bell States, Teleportation,
Superdense Coding]
7.11.: .pps
, .pdf, .ps [Unterscheidbarkeit, Bellsche Ungleichung,
Schaltkreise]
10.11.: .pps
, .pdf, .ps [Quantenschaltkreise, BQP vs PSPACE,
beschränkte Präzision]
14.11.: .pps
, .pdf, .ps [Endliche Basen, Rotationsgatter, Bomb
Testing, Dekomposition unitärer Operationen]
17.11.: .pps
, .pdf, .ps [Simon Algorithmus]
21.11.: .pps
, .pdf, .ps [Ordnungsfinden, Faktorisierung, RSA]
24.11.: .pps
, .pdf, .ps [QFT]
28.11.: .pps
, .pdf, .ps [Shors Algorithmus]
1.12./5.12: .pps
, .pdf, .ps [Hidden Subgroup Problem]
8.12.: .pps
, .pdf, .ps [Grover Algorithmus]
12.12.: .pps
, .pdf, .ps [Erweiterungen Grover, Minimum]
15.12.: .pps
, .pdf, .ps [Untere Schranken für Suche, Amplitude
Amplification]
19.12./2.1.: .pps
, .pdf, .ps [Element Distinctness, Graphalgorithmen]
5.1.: .pps
, .pdf, .ps [Random Walks]
9.1.: .pps
, .pdf, .ps [Quantum Walks]
12.1./ 23.1.: .pps
, .pdf, .ps [Untere Schranken im Black Box Model]
26.1.: .pps , .pdf, .ps [Untere Schranken im Black Box Model]
30.1.: .pps
, .pdf, .ps [Quantum
Key Distribution]
2.2.: .pps , .pdf, .ps [Bit
Commitment, Dichtmatrizen]
Übungsblätter:
27.10: .ps
3.11:
.ps
10.11: .ps
17.11: .ps
24.11: .ps
1.12:
.ps
8.12 : .ps
15.12: .ps
5.1: .ps
26.1: .ps
6.2: .ps .pdf
Literatur:
Bücher:
Nielsen/Chuang: Quantum Computation and Quantum Information
Homeister: Quantum Computing verstehen
Ebenfalls empfohlen (und kostenlos):
John Preskill's lecture notes
Umesh Vazirani's
course
Einige
Übersichtsartikel
Sonstiges:
Bomb Testing Experiment
H. Buhrman and R. de
Wolf. Complexity Measures and Decision
Tree Complexity: A Survey.
In Theoretical Computer Science, 288:21-43, 2002.
6.2.2006, Hartmut Klauck