Quantum Applications

Veranstalter	Prof. Dr. Claudia Linnhoff-Popien Dr. Sebastian Feld
Sprechstunde	auf Anfrage
Hörerkreis	Umfang: V2Ü2 mit 6 ECTS-Punkte Hörerkreis: Vertiefendes Thema der Informatik/Medieninformatik für Bachelor Master Informatik Master Medieninformatik
Vorlesungstermin(e) (Beginn:16.10.2019)	Vorlesung: Mittwochs, 14-16 Uhr c.t., Pettenkoferstr. 14 - "Großer Hörsaal" F 1.02   Übung: Freitags, 10-12 Uhr c.t., Frauenlobstr. 7  - "Sektionshörsaal" 060 Dienstags, 10-12 Uhr c.t., Pettenkoferstr. 14 - "Großer Hörsaal" F 1.02
Übungsbetrieb	Hinweise zu den Übungen siehe unten
Klausur	Die Klausur findet am Freitag, den 07. Februar 2020 von 18:15-19:45 Uhr im Hauptgebäude am Geschwister-Scholl-Platz 1 sowie ggfs. in Räumen der Theresienstr. 39 statt. Der Einlass beginnt ab 18:00 Uhr. Die fristgerechte Anmeldung über Uni2Work ist Zulassungsvoraussetzung. Die An- bzw. Abmeldung ist bis zum Sonntag, 02. Februar 2020, 23:59 Uhr freigeschaltet. Die genaue Raumaufteilung wird nach Ende der Anmeldefrist hier bekanntgegeben. Die Klausureinsicht findet am Freitag, den 14. Februar 2020 von 9-10 Uhr im Raum G010 in der Oettingenstr. 67 statt. Bitte beachten Sie, dass es genau einen Termin für die Klausureinsicht gibt, nämlich den hier genannten Termin. Weitere Hinweise zur Klausur siehe unten.
Nachholklausur	!!! Aufgrund der aktuellen Entwicklungen rund um das Coronavirus muss die Nachklausur "Quantum Applications" am 3. April 2020 bis auf Weiteres verschoben werden. Weitere Informationen finden Sie auf der Webseite der LMU. Sobald wir weitere Informationen haben, werden wir dies unverzüglich über Uni2Work sowie durch einen Hinweis auf der Homepage mitteilen. !!! Die Nachklausur findet am Freitag, den 03.04.2020 von 14:15-15:45 Uhr statt. Der Einlass beginnt ab 14:00 Uhr. Die fristgerechte Anmeldung über Uni2work ist Zulassungsvoraussetzung. Die An- bzw. Abmeldung ist bis zum Sonntag, 29.03.2020, 23:59 Uhr freigeschaltet. Die genaue Raumaufteilung wird nach Ende der Anmeldefrist hier bekanntgegeben. Weitere Hinweise zur Klausur siehe unten.
Material zur Vorlesung	Siehe weiter unten.

Aktuelles

• 16.09.2020: Soeben wurden die Noten zur Präsenz-Nachklausur vom 8.9. eingetragen. Diese dürften nun über uni2work ersichtlich sein. Ich freue mich, dass die Durchführung vor Ort so reibungslos geklappt hat. Wie vor einiger Zeit angekündigt findet die Einsicht am Montag, den 21.9. von 11:30-12:30 im Raum G010 in der Oettingenstr. 67 statt. Bitte bringen Sie einen gültigen Personalausweis/Führerschein/Reisepass mit, da wir Sie sonst nicht einlassen lassen können.
• 07.09.2020: Für die Präsenz-Nachklausur zur Vorlesung „Quantum Applications“ aus dem WiSe19/20 folgen nun Erläuterungen zur Vorgehensweise für das Betreten des Gebäudes und der Klausurräume. Weitere Informationen zum gesamten Ablauf finden sich im Hygienekonzept (http://www.mobile.ifi.lmu.de/wp-content/uploads/Hygienekonzept-MVS.pdf) und werden vor Ort nochmals erläutert. Die Klausur wird in der Oettingenstr. 67 in den Hörsälen B001 und BU101 sowie im Seminarraum 151 geschrieben. Die Aufteilung lautet (Nachname beginnend mit): B001 (A-M), BU101 (N-S), 151 (T-Z). Der Einlass beginnt um 14:00 Uhr. Bitte benutzen Sie ausschließlich den markierten Eingang (links vom Hörsaal, siehe http://www.mobile.ifi.lmu.de/wp-content/uploads/NK_BS_Gebaudeplan.png). Beim Einlass in den Prüfungsraum nennen Sie bitte Ihren Namen und zeigen Ihren Ausweis vor. Achten Sie hier bitte auf genügend Abstand zu anderen Personen. Anschließend wird Ihnen ein Platz zugewiesen mit genügend Abstand zu weiteren Personen. Nehmen Sie dort Platz. Auf dem Platz liegt ein verschlossener Umschlag, der die Klausur enthält. Die Umschläge dürfen erst zum Beginn der Bearbeitungszeit geöffnet werden. Die Bearbeitung beginnt um 14:30 Uhr. Bitte beachten Sie, dass wir nur Personen einlassen, die zur Klausur angemeldet sind und sich ausweisen können. Wenn Sie Erkrankungsanzeichen haben, kommen Sie keinesfalls zur Klausur. Lesen Sie bitte nochmals das Hygienekonzept. Sollten Sie Fragen haben, so melden Sie sich bitte.
• 18.08.2020: Es folgen weitere Informationen zur Präsenznachklausur. Die Nachklausur findet am Dienstag, den 8. September von 14:30-16:00 Uhr statt. Vorgesehen sind die Hörsäle B001 und BU101 in der Oettingenstr. 67. Der Einlass beginnt um 14:00. Sie dürfen ausschließlich die markierten Ein- und Ausgänge benutzen, um zu den Klausurräumen zu gelangen (http://www.mobile.ifi.lmu.de/wp-content/uploads/NK_BS_Gebaudeplan.png). Mit der Anmeldung zur Nachklausur im Uni2work haben Sie bestätigt, dass sie alle 6 Seiten des Hygienekonzepts (http://www.mobile.ifi.lmu.de/wp-content/uploads/Hygienekonzept-MVS.pdf) gelesen haben, sich strikt daran halten werden und dass Sie im Falle von Erkrankungsanzeichen (wie z.B. Fieber, Husten, etc.) auf keinen Fall in die Universität kommen und nicht an der Prüfung teilnehmen. Die Bekanntgabe der Noten erfolgt am Donnerstag, den 17. September via Uni2work. Die Klausureinsicht erfolgt am Montag, den 21. September von 11:30-12:30 im Raum G010 in der Oettingenstr. 67. Bitte bringen Sie sowohl zur Klausur als auch zur Klausureinsicht einen gültigen Personalausweis/Führerschein/Reisepass mit, da wir Sie sonst nicht einlassen lassen können. Sollten Sie weitere Fragen haben, so wenden Sie sich bitte per E-Mail an die Organisation der Veranstaltung (sebastian.feld@ifi.lmu.de).
• 03.08.2020: Wir haben nun alle Hürden nehmen können und bieten eine Präsenz-Nachklausur (Dienstag, 08. September, 14:30-16:00) für die Vorlesung “Quantum Applications” (QA) aus dem WiSe19/20 an. Bitte beachtet: es ist die erste und letzte Möglichkeit, an einer Nachklausur QA teilzunehmen. Es wird keine neue Vorlesung QA geben und somit auch keine weiteren Klausuren und Nachklausuren für QA.
  Mit der Anmeldung zu dieser Nachklausur bestätigen Sie, dass Sie das Hygienekonzept (http://www.mobile.ifi.lmu.de/wp-content/uploads/Hygienekonzept-MVS.pdf) vollständig (6 Seiten) gelesen haben und sich vollständig an alle dortigen Anweisungen und Hinweise halten.
  Insbesondere dürfen Sie nicht an der Nachklausur teilnehmen, wenn Sie Anzeichen einer Erkrankung aufweisen (wie z.B. Fieber, Husten, etc.). Sollte bei Ihnen der Verdacht einer Infektion vorliegen, wenden Sie sich bitte umgehend per E-Mail an die Veranstaltungsorganisation (sebastian.feld@ifi.lmu.de) und teilen dies mit. Kommen Sie auf keinen Fall zur Nachklausur, solange der Verdacht nicht von ärztlicher Seite, durch einen Test, ausgeschlossen wurde.
  Sollten Sie Fragen zum Hygienekonzept oder ein sonstiges Anliegen diesbezüglich haben, wenden Sie sich gerne vorab per E-Mail an die Organisation der Veranstaltung (sebastian.feld@ifi.lmu.de).
• 29.05.2020: Liebe Studierende,
  ich hoffe, Sie sind alle gesund und es geht Ihnen trotz der ungewohnten Umstände gut.
  Es ist nun einige Zeit vergangen, nachdem die QA-Vorlesung geendet hat und viele von Ihnen die Hauptklausur erfolgreich bestanden haben. Am Freitag, den 3. April hätte eigentlich die Nachklausur stattfinden sollen, diese musste jedoch aufgrund der Corona-Situation ausfallen.
  In der Zwischenzeit hat die Hochschulleitung der LMU empfohlen, nach Möglichkeit alle Prüfungen online durchzuführen und zu diesem Zweck eine „Flexi-Satzung“ erlassen, die dieses und nächstes Semester gilt. Aufgrund dessen verfährt der „Mobile und Verteilte Systeme“-Lehrstuhl wie folgt: zu den aktuellen Vorlesungen „Rechnerarchitektur“ und „Intelligente Systeme“ gibt es sogenannte Online-Hausarbeiten, die wöchentlich von den Studierenden begleitend zur Vorlesung bearbeitet und abgegeben werden. Diese Online-Hausarbeiten werden bewertet und ergeben am Ende die Note anstelle einer Klausur.
  Vor diesem Hintergrund, nämlich dass die Flexi-Satzung zwei Semester (dieses und nächstes) lang gilt, möchten wir Ihnen daher dringend empfehlen, im kommenden Wintersemester 20/21 den Abschluss zur Vorlesung QA-WS19/20 zu machen. Sie brauchen in diesem Fall nichts weiter zu tun, als sich im WS20/21 für die Vorlesung „Quantum Applications“ einzuschreiben, sich dann für die angebotene Prüfungsform anzumelden und die entsprechende Leistung zu erbringen. Ein erneutes Hören der Vorlesung oder ein erneutes Besuchen der Vorlesung kann gerne erfolgen, ist jedoch nicht notwendig.
  Wir hoffen, dass Ihnen so eine planbare und zugleich gut mit dem übrigen Studium vereinbare Möglichkeit angeboten wird, um Ihren Abschluss zu machen.
  Sollten Sie ein Härtefall sein, der in diesem Semester dringend den Abschluss braucht, so schreiben Sie uns bitte bis Mittwoch, den 3. Juni 2020, 12:00 Uhr eine E-Mail und bitten um eine Nachprüfung im aktuellen Semester (sebastian.feld@ifi.lmu.de mit Betreff „Nachklausur QA“). Falls es Härtefälle gibt: Die fertigen Klausuren liegen bereit und wir würden kurzfristig abklären, ob wir eine Klausur anbieten können.
  Alles Gute und mit den besten Grüßen,
  Sebastian Feld
• 12.03.2020: Aufgrund der aktuellen Entwicklungen rund um das Coronavirus muss die Nachklausur „Quantum Applications“ am 3. April 2020 bis auf Weiteres verschoben werden. Weitere Informationen finden Sie auf der Webseite der LMU [DE, EN]. Sobald wir weitere Informationen haben, werden wir dies unverzüglich über Uni2Work sowie durch einen Hinweis auf der Homepage mitteilen.
• 20.02.2020: Die Nachklausur findet am Freitag, den 03.04.2020 von 14:15-15:45 Uhr statt. Die An- bzw. Abmeldung über Uni2work ist bis zum Sonntag, 29.03.2020, 23:59 Uhr freigeschaltet.
• 03.02.2020: Für die Klausur am 07.02.2020 gilt folgende Sitzordnung:
  

  Hörsaal	Anfangsbuchstabe Nachname
  A 240, HGB, Geschw.-Scholl-Platz 1	A – K
  M 218, HGB, Geschw.-Scholl-Platz 1	L – Z

  Innerhalb der Hörsäle wird es feste Platznummern geben. Bitte erfragen Sie diese beim Eintritt in den Hörsaal. Studenten mit Sonderbedingungen melden sich bitte vorab und kommen trotz obiger Platzordnung zum Hörsaal M 218 (HGB, Geschw.-Scholl-Platz 1). Der Einlass beginnt um 18:00 Uhr. Die Bearbeitungszeit beginnt um 18:15 Uhr. Bitte seien Sie rechtzeitig vor dem Einlass anwesend.

• 22.01.2020: Die Klausureinsicht findet am Freitag, den 14. Februar 2020 von 9-10 Uhr im Raum G010 in der Oettingenstr. 67 statt.
• 08.01.2020: Die Anmeldung zur Hauptklausur ist nun eröffnet. Die fristgerechte Anmeldung über Uni2Work ist Zulassungsvorraussetzung. Die An- bzw. Abmeldung ist bis zum Sonntag, 02. Februar 2020, 23:59 Uhr, freigeschaltet.
• 28.11.2019: Im gestrigen Vorlesungstermin wurde die Public Climate School München kurz vorgestellt und einige Gedanken zum Thema „Grüne Optimierungsprobleme“ präsentiert. Die entsprechenden Slides sind, wie immer, unten bei Vorlesungsunterlagen zu finden.
• 15.11.2019: Wie mehrfach angekündigt werden in der kommenden Woche die Vorlesung und die Übung getauscht. Das heißt: am Mittwoch, den 20.11. findet von 14-16 in der Pettenkofer die Übung statt und am Freitag, den 22.11. findet von 10-12 in der Frauenlob die Vorlesung statt.
• 22.10.2019: Der morgige Vorlesungstermin (23.10.) muss leider krankheitsbedingt ausfallen. Eine entsprechende Mail wurde auch per uni2work-Kursmitteilung versendet.
• 16.10.2019: Es wurden weitere Informationen bzgl. Übungsbetrieb und Klausuren veröffentlicht. Die erste Vorlesung findet am Mittwoch, den 16.10.2019 statt und die erste Übung am Freitag, den 25.10.2019.
• 04.09.2019: Die Seite zu dieser Veranstaltung ist ab sofort online.

Inhalt der Vorlesung

Das Feld des Quantum Computing, das auf den Prinzipien der Quantenmechanik beruht und sogenannte Qubits als Informationseinheit benutzt, wird spätestens seit den Veröffentlichungen der Quantenalgorithmen von Shor und Grover in den 90er Jahren immer relevanter. Doch die Wissenschaft beschäftigt sich bereits länger mit der Möglichkeit eines Quantencomputers – so postulierte der berühmte Physiker Richard Feynman in seinem 1982 veröffentlichten Paper Simulating Physics with Computers, dass zur Simulation eines Quantensystems auch ein Quantencomputer benötigt werde. Dabei gibt es mehrere Ansätze bzw. Modelle für solche Quanten-Rechnerarchitekturen, wie z.B. Quantum Gate Computing und Adiabatic Quantum Computing. Inzwischen gibt es mit D-Wave Systems bereits eine erste Firma, die auf Basis des Adiabatic Quantum Computing eine Quantum Annealing Hardware gebaut hat.

In der Vorlesung wird der Ansatz des Quantum Annealing diskutiert, der auf dem adiabatischen Theorem beruht und mit dem algorithmischen Verfahren des Simulated Annealing verwandt ist. In diesem Rahmen werden Anwendungen zur Lösung von (kombinatorischen) Optimierungsproblemen besprochen und dabei ein kurzer Vergleich zwischen ‚klassischer‘ Komplexität und Quantenkomplexität gegeben.

Das Ziel der Vorlesung ist es, ein Verständnis für die quantenmechanischen Grundlagen des Quantum Computing zu entwickeln, Formalisierungen und Lösungsmethoden für (kombinatorische) Optimierungsprobleme kennenzulernen, sowie deren praktische Anwendung im Rahmen des Quantum Annealing zu üben. Dabei wird sowohl auf die mathematischen und physikalischen Grundlagen (Theorie), als auch die (eigene) Anwendung (Praxis) Wert gelegt.

Eine Auswahl der behandelten Themen lautet:

• Rechnermodelle:
  • Turing Maschine, Von Neumann Architektur
  • Ansätze zur physikalischen Realisierung von Quantencomputern
  • Quantum Gate Computing vs. Adiabatic Quantum Computing
• Grundlagen der Quantenmechanik und des Quantum Computing:
  • Zustand, Observable, Messung
  • Hamiltonians, Schrödingergleichung
  • Qubits und Qubit-Operationen
  • Superposition, Verschränkung und Teleportation von Zuständen
  • Quantenalgorithmen
• Optimierung:
  • Ganzzahlige lineare / binäre / quadratische / kombinatorische Optimierung
  • Optimierungsprobleme (z.B. SAT, Knapsack, TSP, QAP, VRP)
  • klassische Komplexität / Quantenkomplexität
  • Exakte und (Meta-)Heuristische Lösungsverfahren
• Quantum Annealing
  • Adiabatischer Algorithmus, adiabatisches Theorem
  • QUBO und Simulated Annealing
  • Ising und Quantum Annealing
  • Problem Hamiltonians
  • D-Wave Systems Quantum Annealing Hardware
• Quantum Annealing Anwendungen:
  • Beispiele: Maximum Clique, Flight Gate Assignment, Robot Movement, Vehicle Routing, Portfolio Optimization

Übungen

An dieser Stelle werden Informationen zum Übungsbetrieb zur Verfügung gestellt.

• Die Übung ist stark verwoben mit den Inhalten der Vorlesung und dient der Wiederholung und Vertiefung des Vorlesungsstoffes. Die Übung bestitzt zudem einen integrierten praktischen Anteil (Python-Programmierung).
• In der Übung werden Teile des Vorlesungsstoffes nachgerechnet oder nachprogrammiert. Es soll möglichst kein neuer, über den in der Vorlesung hinaus gehender, Stoff vermittelt werden. Nach dem Übungstermin werden, sofern möglich, die Rechnungen oder der Programmcode über die Lehrstuhl-Webseite zur Verfügung gestellt.

Übungsmaterial

Siehe weiter unten.

Klausur

• Es werden zwei Klausuren (Klausur und Nachklausur) angeboten.
• Die Details finden sich weiter oben im Kopf der Seite sowie unter Aktuelles.
• Für beide Klausuren gilt:
  • Es findet eine obligatorische Klausuranmeldung statt. Wenn Sie nur an der zweiten Klausur (Nachholklausur) teilnehmen möchten, müssen Sie sich nicht für die erste Klausur anmelden.
  • Achtung: Ein Nichterscheinen bei vorliegender Anmeldung führt zu einem "durchgefallen" in den Transkripts of Records, siehe hier.
  • Anmeldungen nach dem letzten Anmeldetermin werden nicht akzeptiert.
  • Nicht angemeldete Studierende können nicht an der jeweiligen Klausur teilnehmen.
  • Zur Klausur sind keinerlei Hilfsmittel außer Fremdwörterbüchern erlaubt.
  • Bringen Sie Ihren Studentenausweis und einen amtlichen Lichtbildausweis mit zur Klausur. Personen, die sich in der Klausur nicht ausweisen können, dürfen nicht an der Klausur teilnehmen. Es werden diesbezüglich keine Ausnahmen gemacht.
  • Der Prüfungsstoff beinhaltet die gesamten Inhalte aus Vorlesung und Übung.
  • Die Klausurergebnisse werden Ihnen an Ihre CIP-Pool Email-Adresse (<kennung>@cip.ifi.lmu.de) übermittelt. Sollten Sie mit dieser Datenübermittlung nicht einverstanden sein, so melden Sie dies bitte per E-Mail vor dem Klausurtermin.

Programme und Hilfsmittel

Literatur