Einführung

Quantenalgorithmen bieten im Abfragemodell der Berechnung nachweisbare Vorteile gegenüber klassischen Algorithmen. Aber wie sieht es mit einem standardmäßigeren Berechnungsmodell aus, bei dem Probleminstanzen explizit und nicht in Form eines Orakels oder einer Black Box eingegeben werden? Das erweist sich als eine weitaus schwierigere Frage, und um sie anzugehen, müssen wir zunächst eine solide Grundlage für unsere Untersuchung schaffen. Genau das ist der Hauptzweck dieser Lektion.

Wir beginnen mit der Erörterung von Berechnungskosten – sowohl für klassische als auch für Quantenberechnungen – und wie diese gemessen werden können. Dies ist ein allgemeines Konzept, das auf eine Vielzahl von Berechnungsproblemen angewendet werden kann – aber der Einfachheit halber betrachten wir es hauptsächlich durch die Linse der algorithmischen Zahlentheorie, die mit Berechnungsaufgaben befasst, die den meisten Lesern vertraut sein dürften: grundlegende Arithmetik, Berechnung des größten gemeinsamen Teilers und ganzzahlige Faktorisierung. Obwohl die algorithmische Zahlentheorie ein enges Anwendungsgebiet ist, eignen sich diese Probleme gut zur Veranschaulichung der grundlegenden Fragen (und sie sind zufällig auch sehr relevant für die darauffolgende Lektion).

Unser Fokus liegt auf Algorithmen und nicht auf der sich ständig verbessernden Hardware, auf der sie ausgeführt werden. Entsprechend interessiert uns weniger, wie viele Sekunden, Minuten oder Stunden eine bestimmte Berechnung benötigt, sondern vielmehr, wie die Kosten der Ausführung eines Algorithmus skalieren, wenn die Probleminstanzen, für die er ausgeführt wird, größer werden. Wir konzentrieren uns auf diesen Aspekt der Berechnungskosten in der Erkenntnis, dass Algorithmen von grundlegender Bedeutung sind und mit zunehmend leistungsfähigerer und zuverlässigerer Hardware natürlich auf immer größere Probleminstanzen angewendet werden.

Schließlich wenden wir uns einer kritisch wichtigen Aufgabe zu: dem Ausführen klassischer Berechnungen auf Quantencomputern. Diese Aufgabe ist nicht deshalb wichtig, weil wir hoffen, klassische Computer durch Quantencomputer zu ersetzen – was in absehbarer Zeit, wenn überhaupt, äußerst unwahrscheinlich erscheint –, sondern weil sie viele interessante Möglichkeiten für Quantenalgorithmen eröffnet. Konkret werden klassische Berechnungen, die auf Quantencomputern ablaufen, als Unterroutinen verfügbar, wodurch Jahrzehnte der Forschung und Entwicklung an klassischen Algorithmen für Quantenvorteile nutzbar gemacht werden.

Lektionsvideo

Im folgenden Video führt John Watrous durch den Inhalt dieser Lektion zu den algorithmischen Grundlagen der Quantenberechnung. Alternativ kannst du das YouTube-Video für diese Lektion in einem separaten Fenster öffnen. Folien herunterladen für diese Lektion.