00:01Wie funktioniert ein Quantencomputer? Dies ist Teil 5 einer einführenden Videoserie zur Quanteninformation
00:08Andere Menschen, die sich dieses Video anschauen, haben die ersten vier Teile gesehen, Sie auch? Sonst werden Sie vielleicht nicht viel verstehen
00:14Es gibt jedenfalls in einem Kanal eine Playlist, in der alle Teile, die ich schon hochgeladen habe, in der richtigen Reihenfolge zu finden sind
00:19Im letzten Video lernten wir die große Integration kennen, das war der erste nicht triviale Algorithmus, der in dieser Serie vorgestellt wurde
00:25Heute wird es um den Shor-Algorithmus gehen, denn nach dem amerikanischen Mathematiker Peter Shor, äh, den hat sich 1994 ausgedacht
00:38Aus gewöhnlich gut unterrichteten Kreisen habe ich erfahren, dass der auch Mitglied bei den drei Fragezeichen sein soll
00:43Ich bin dafür allerdings kein Experte
00:49Wie auch immer, wenn es ein einzelnes Verfahren gibt, das Quantencomputer für die breite Öffentlichkeit interessant gemacht hat, dann ist es sicher dieses, denn mit ihm kann man Codes knacken, die heutzutage weltweit für die Verschlüsselung geheimer Daten eingesetzt werden
00:55Das schauen wir uns nun an
01:00Es gibt mehrere Krypto-Systeme, die man, wenn Wenn Quantencomputer erst einmal leistungsfähig genug sind, mit dem Shor-Algorithmus knacken kann, das bekannteste und am weitesten verbreitete ist wohl RSA
01:12Darüber gibt es von mir schon ausführliche Videos, darum will ich nur ganz kurz auf einer Folie die Grundidee demonstrieren, damit man sieht, an welcher Stelle der Angriff ansetzt
01:18Wir sehen unsere alten Bekannten Pop und alles aus dem dritten Video
01:24Rhythmus bestimmte Vorbereitungen treffen, die hier als Giulia Programm dargestellt sind, die Ergebnisse sieht man rechts davon
01:30Die Zahlen, die wir als Beispiele sehen, sind allerdings viel zu
01:33Klein, damit die Verschlüsselung sicher ist
01:37Wird in der Realität mit Zahlen gerechnet, die viele hundert Dezimalstellen haben
01:40Für uns ist momentan nur wichtig, dass Bob sich von seiner Berechnung die Zahl der merkt und sie niemandem verrät
01:45Zwei weitere Resultate, N und D, veröffentlicht er und stellt sie jedem zur Verfügung, der ihm eine verschlüsselte Botschaft schicken will
01:53Dazu publiziert er außerdem eine ganz simple Funktion in einem Skript, in die die Zahlen schon eincodiertes
02:00Will Alice Bob nun eine Nachricht schicken, so berechnet sie mit Hilfe der Funktion Crypt und des öffentlichen
02:07Schlüssels, der die Verschlüsselung SVM und schickt diese an Bord
02:14Bob kann Emmaus es rekonstruieren, indem er die Stadt de verwendet
02:20Die Idee ist natürlich, dass nur er das machen kann, weil nur RD kennt
02:27Was könnte er nun, ein potenzieller Angreifer tun, der M abhängt? Gibt es eine Möglichkeit, Box keine Zahl der zu ermitteln, wenn nur die öffentlichen Zahlen E und N bekannt sind? Ja, theoretisch gibt es die, da allseits bekannt ist, wie das erste System funktioniert
02:38Weiß der Angreifer, dass N das Produkt zweier Primzahlen P & Co ist? An dem Programm oben links kann man erkennen, wie man viel und daraus den berechnen
02:52Kann, wenn man PC kennt, man muss also nur einen Teiler von N finden, nichts leichter als das, oder? Hier steht noch mal schwarz auf weiß, was zu tun ist: Man muss die Teile einer zusammengesetzten Zahl finden, sogar noch etwas simpler, man muss einen echten Teiler finden, weil man weiß, dass es nur zwei Primzahl ergibt
03:00Man nennt das das Faktorisierungsproblem
03:07Das muss übrigens nicht zwangsläufig die einzige Möglichkeit sein, RSA zu knacken, aber bisher ist niemandem eine bessere Methode eingefallen
03:15Der Grund, warum er es bisher noch als sicher gilt, ist der, dass alle Methoden, die man für das Faktorisierung Problem bisher entwickelt hat, zu langsam sind
03:29Sie haben kein exponentielles Laufzeitverhalten, wie die Algorithmen, über die wir am Ende des letzten Videos gesprochen haben, aber sie sind nicht polymer und damit nicht zu gebrauchen, wenn die für die Verschlüsselung verwendeten Zahlen groß genug sind
03:40Da ich gerade das letzte Video erwähne, es ist nicht bekannt, ob das Faktorisierungsproblem NP-vollständig ist
03:46Es gibt da eine gewisse mathematische Unsicherheit, die man auch so ausdrücken kann: Niemand konnte bisher beweisen, dass man mit herkömmlichen Mitteln das Faktorisierungsproblem nicht mit akzeptabler Laufzeitkomplexität lösen kann
03:58Was die Sicherheit solcher Verfahren angeht, verlassen wir uns darauf, dass selbst nach Jahrzehnten intensiver Forschung keine Lösung am Horizont zu sehen ist, aber das ist ohnehin alles obsolet, sowie Quantencomputer mit genügend vielen Qubits zuverlässig sind, denn dann kann man das Faktorisierungsproblem schnell genug lösen
04:18Das macht der erwähnte Shor-Algorithmus, der seit über einem Vierteljahrhundert darauf wartet, eingesetzt werden zu können
04:23Die grobe Idee des Verfahrens sehen Sie hier: Wir wollen einen nicht-trivialen Teiler der Zahlen
04:28finden, also einen anderen Teiler als 1 oder n
04:32Das wird natürlich nicht funktionieren, wenn er in eine Primzahl ist
04:36Grundsätzlich funktioniert das Verfahren nur für ungerade Zahlen, die keine Primzahlpotenzen sind
04:41Das macht aber nichts, erstens kann man diese Fälle durch klassische Tests effizient ausschließen, und zweitens ist die Voraussetzung automatisch erfüllt, wenn die entsprechende Zahl aus dem RSA-Kryptosystem ist
04:54Der Shor-Algorithmus arbeitet mit Zufall, er liefert jedoch, anders als der große Algorithmus oder der Miller-Rabin-Test, immer ein richtiges Ergebnis
05:01Der Zufall kann lediglich dazu führen, dass mehrere Versuche nötig sind
05:07Ich werde jetzt die Grundzüge erläutern, dabei aber nicht auf jedes zahlentheoretische Detail eingehen, weil uns das zu weit vom Wege ab führen würde
05:11Es soll ja eigentlich um Quantencomputer gehen
05:15Links oben geht es damit los, dass man sich eine Zahl unterhalb von N zufällig auswählt
05:19Dann prüft man, ob A und N teilerfremd sind
05:25Ist das nicht der Fall, dann ist man offensichtlich schon fertig, andernfalls ermittelt man die Ordnung von A in der Preisklasse Gruppe bezüglich des Moduls N
05:32Falls Ihnen das nicht sagt, macht das nichts, wir suchen
05:39Schlicht und einfach die kleinste Zahl P für die hoch P Modul N 1 ist, das ist die Periode der Funktion, die XFX modulo N abbildet
05:45Sollte P ungerade sein, dann fangen wir wieder von vorne an, ansonsten testen wir, wie hoch P halbe Modul N -1 ist, umfangen auch in diesem Fall wieder von vorne an
05:59Das klingt zunächst nach einem eher wackeligen Glücksspiel, aber das ganze Verfahren ist so austariert, dass für große N, und um die geht es ja, die Wahrscheinlichkeit, dass alles klappt, ausreichend ist
06:10Am Ende berechnen wir noch den größten gemeinsamen Teiler von N und P/2, das ist der gesuchte Teiler hier ein
06:16Konkretes Beispiel, natürlich, wieder dafür, zahlen die viel, viel kleiner als die sind, um die es wirklich geht
06:21Unsere Zahlen ist das Produkt zweier Primzahlen, wie die Zahl von Portfolien
06:25Wir kennen die Faktoren nicht und suchen einen Teiler von M
06:30Im ersten Versuch wählen wir zufällig A gleich 48 aus
06:35Wir müssen zuerst einmal testen, ob die ausgewählte Zahl und N Teiler fremd sind
06:41Das wäre nur dann nicht der Fall, wenn wir das große Glück gehabt hätten, gerade 541 oder 601 auszuwählen
06:45Als Nächstes bestimmen wir die Periode von A di
06:49In diesem Fall 75 ist da, dass eine ungerade Zahl ist, müssen wir aufgeben und
06:52ein anderes wählen
06:55Jetzt fallen die Würfel auf a gleich 40
06:57In diesem Fall ist die Periode 2700, also gerade
07:00Nun berechnen wir, wie hoch 1000 Roland 50, Modell der Exponent, ist die Hälfte der Periode
07:04Leider kommt genau -1 heraus
07:08Dieses können wir auch nicht nehmen
07:13Es könnte jetzt der Eindruck entstehen, dass man sich ziemlich lange mit solchen Fehlversuchen herumplagen muss, bis man einen Treffer landet
07:16Man kann jedoch zeigen, dass das für große Zahlen nicht der Fall ist
07:20Man wird sehr selten mehr als zwei Versuche brauchen
07:24Entscheidend ist natürlich auch, dass so ein Versuch nicht lange dauern darf
07:27Dritte Punkt zeigt, wie es im Erfolgsfall abläuft
07:30Wir haben gleich 42 ausgewählt, die Periode ist gerade und die Potenz, die wir ausrechnen müssen, ist nicht ein -1
07:35An dieser Stelle wissen wir, dass wir auf jeden Fall einen nicht trivialen Teiler finden
07:41Dafür berechnen wir den größten gemeinsamen Teiler von 42 hoch 900 - 1 und N, und der ist 541
07:47Das, was wir eben gemacht haben, lässt sich in ein paar Zeilen als klassisches Programm schreiben
07:54Hier ist ein Beispiel in Giulia, und bis auf ein Detail ist alles effizient realisierbar, insbesondere gilt das für die Berechnung des größten gemeinsamen Teilers mit dem
08:01Klinischen Algorithmus und für die Berechnung großer Potenzen mit binärer Exponation, über beides gibt es Videos in einem Kanal
08:07Bevor wir uns gleich darüber unterhalten, wieso man überhaupt noch einen Quantencomputer benötigt, will ich für die fortgeschrittenen Zuschauer ganz kurz noch andeuten, warum diese Vorgehensweise zum Erfolg führt
08:19Der Trick ist, dass man auch bei -1 nach der dritten binomischen Formel als das Produkt darstellt, dass man hier sieht, dass das möglich ist, liegt daran, dass wir nur gerade Werte für z zulassen, die linke Seite der Gleichung ist durch ein teilbarer, weil
08:30Wir P so gewählt hatten, als Periode von A hoch X1
08:37Modell, der rechte Faktor auf der rechten Seite ist nicht durch N teilbar, weil wir das durch einen Test ausgeschlossen haben, und der linke Faktor ist auch nicht durch N teilbar, weil P die kleinste Zahl mit der Eigenschaft ist, dass A hoch P1 durch N teilbar ist
08:55Damit haben wir eine durch N teilbare Zahl als Produkt zweier Zahlen geschrieben, die nicht durch N teilbar sind, also können die Faktoren nicht Teiler von N sein, und auf der Basis berechnen wir am Ende den Ausgabewert Z
09:01Klingt doch super, wenn wir jetzt auch noch glauben, dass das oft Genug klappt, ist alles in Butter, bis auf, Sie haben sich vielleicht schon gedacht, das Finden der Periode in meinem kleinen Beispiel
09:11Programm habe ich das ganz naiv durchprobieren gelöst
09:21Höhere Zahlen von der Größenordnung, denen der Kryptographie Gang und Gäbe ist, ist das jedoch ein hoffnungsloses Unterfangen und könnte bis zum Sankt Nimmerleins Tag dauern, und ein effizientes klassisches Verfahren zum Ermitteln solcher Perioden ist nicht bekannt
09:29Hier kommen die Quantencomputer ins Spiel
09:36Mit anderen Worten, wir vergessen jetzt die Suche nach Thailand und kümmern uns für den Rest des Videos nur noch um das Finden von Perioden in periodischen Funktionen
09:43Wenn wir das schnell genug erledigen können, ist der gesamte Algorithmus schnell genug
09:50Wenn Sie ein bisschen Erfahrung mit mathematischen Methoden haben, dann halten Sie jetzt mal kurz das Video an und fragen sich, was Ihnen zur Analyse periodischer Funktionen einfällt
09:57Genau, die für ihn alles, auch darüber gibt es schon ausführliche Videos von mir
10:04Zu die, die noch nie davon gehört haben, gibt es nun eine minimale Einführung, die den anderen gleichzeitig als Erinnerung dienen kann, dabei gehe ich aber nur auf das
10:11Allernotwendigste ist, dass wir für den Shor-Algorithmus brauchen, insbesondere brauchen wir nur die diskrete Fourier-Transformation
10:16Das ist ein Algorithmus, der als Eingabe eine Sequenz von Zahlen bekommt, das sind ja erst Beispiel 32 Werte
10:22Ich habe absichtlich eine Beschriftung der Achsen weggelassen, weil das für die folgenden Überlegungen keine wesentliche Rolle spielt
10:28Man sieht den Zahlen eine periodische Wiederholung an, wenn Sie sich von links nach rechts einen Zeitverlauf einer Sekunde mit 32 Messwerten vorstellen, dann beobachten wir offenbar ein Signal mit einer Frequenz von
10:40Vier, die Ausgabe der diskreten Fourier-Transformation ist ebenfalls eine Zahlenfolge, und es sind ebenso viele Zahlen wie bei der Eingabe
10:46Die ausgegebenen Zahlen sind in der Regel komplexe Zahlen, von denen ich hier nur den Betrag zeige, für unsere Zwecke reicht's
10:53Die Eingabewerte können auch komplexe Zahlen sein, aber in diesem Video werden es immer reelle Zahlen sein, daher wird sich bei der Ausgabe immer eine Symmetrie ergeben, die durch den grau hinterlegten Teil angedeutet ist
10:59Die mit 0 bzw
11:0616 bezeichneten Spalten sind eine Ausnahme, abgesehen davon wird der graue Teil von Spalte 17 später 31
11:13immer ein Spiegelbild der Spalten 1 bis 15 sein
11:18Auch bei der Ausgabe verzichte ich auf die Beschriftung der vertikalen Achse, und mussten nur das Größenverhältnis der ausgegebenen Werte interessieren
11:24In diesem Beispiel gibt es, bis auf das Spiegelbild, nur in der Spalte vier einen positiven Wert
11:29Das bedeutet, dass die Fourier-Transformation in der Eingabe die Frequenz 4 entdeckt hat
11:36Mathematisch präzise heißt es, dass man mit Hilfe der Ausgabewerte eine Sinusschwingung dieser Frequenz angeben kann, die genau durch die 32 Eingabewerte verläuft, wie wir hier sehen
11:44Natürlich hatte ich für das Beispiel, die Datenpunkte gerade so gewählt, dass das klappt
11:52Ja, ein anderes Beispiel: Man sieht zwei Wiederholungen eines identischen Datensatzes, und rechts wurde treffsicher die Frequenz zwei erkannt
12:01Das entspricht der gezeigten Kurve, aber wie? Fourier Transformation wäre nicht eines der am häufigsten verwendeten Verfahren, wenn das alles wäre, was sie könnte
12:07Sie kann auch überlagerte Schwingungen erkennen, dazu hier ein erstes einfaches Beispiel
12:13Der Ausgabe entnehmen wir Werte für die Frequenzen zwei und acht, wobei der Wert für zwei deutlich größer ist
12:19Damit ist gemeint, dass wir eine dominierende Schwingung, quasi einen Grundton der Frequenz zwei haben, und eine überlagerte Schwingung, eine Art Oberton der Frequenz 8 mit geringerer Amplitude
12:28Die Eingabe bestand aus der Überlagerung dieser beiden Schwingungen
12:37Die Fourier-Transformation war in der Lage, diese beiden Frequenzen aus den Eingangsdaten zu extrahieren, die ja ein realistischeres und komplizierteres Beispiel sind
12:45In der Ausgabe sehen wir, dass diesmal alle Werte von 0 verschieden sind, man erkennt aber auch dominante Werte bei den Frequenzen 2, 4 und 8
12:51Der größte Ausgabewert steht für diese Schwingung der Frequenz 2
12:57Darauf wird eine schwächere Schwingung der Frequenz vier moduliert, und darauf eine noch schwächere der Frequenz acht
13:04Wenn man genau hinschaut, sieht man jedoch, dass die aus diesen drei Anteilen zusammengesetzte Kurve nicht exakt durch die Eingabe werde verläuft
13:10Das liegt daran, dass ich bei der Konstruktion des Beispiels noch etwas zufälliges Rauschen beigemischt habe
13:15Würden wir die rechts gezeigten kleinen Anteile für Frequenzen wie 13 oder zehn noch hinzufügen, würde die Kurve wieder genau mit der Angabe übereinstimmen
13:28Wichtig ist jedoch, dass wir festhalten, dass man an der Ausgabe insbesondere die dominanten Frequenzen der Eingabe erkennen kann
13:35Nach diesem Crashkurs zur diskreten Fourier-Transformation kommen wir nun zurück zu den Zahlenfolgen, deren Periode wir erkennen wollen
13:41Wollen wir beispielsweise Teiler von N gleich 15 finden, so könnte es sein, dass wir zufällig die Zahl gleich sieben gewählt haben und die Periode der Funktion 7 hoch x-mod 15 finden müssen
13:53Die ersten 32 Funktionswerte, beginnend bei x gleich Null, sind hier als Eingabe für eine Fourier-Transformation aufgetragen, und rechts sehen wir das Ergebnis
14:00Die Funktionswerte sind 1, 7, 4, 13, danach geht es wieder von vorne los
14:06Die Länge der Periode ist also vier
14:12In dieser Zeit wollen wir herausbekommen, da unsere Eingabe die Länge 32 hat, ergibt, dass die Frequenz acht, nämlich 32 geteilt durch vier
14:19Idealerweise würde uns die Fourier-Transformation nur den Wert 8 und sein Spiegelbild liefern, wir erhalten aber außerdem noch 16 zurück, und die ominöse Frequenz 0, die in den vorherigen Beispielen unterschlagen hatte
14:30Die 16 lässt sich relativ leicht erklären, wir sehen links eine periodische Funktion, aber es handelt sie ersichtlich nicht um eine Sinus- oder Cosinusschwingung, die Fourier
14:41Transformation liefert aber immer nur Überlagerung solcher Schwingungen, und die Funktionen links so darzustellen, muss man offensichtlich über eine Grundschwingung der Frequenz 8 nach Obertönen legen, deren Frequenzen aber wohl, zumindest anschaulich klar, ein Vielfaches der Grundfrequenz sein
14:50Das werden wir später ausnutzen
14:58Die Frequenz 0, die man in den Anwendungen auch den Gleichspannungsanteil nennt, ist so etwas wie die Nulllinie der ausgegebenen Schwingung
15:06In den Beispielen vorher war die nicht zu sehen, weil ich die Eingabe so gewählt hatte, dass ihr Mittelwert 0 war
15:12Arithmetische Mittel von 17, 4 und 13 ist jedoch 6,25, und unsere Kurve schwingt quasi um diesen Wert herum
15:17Auf diese Grundlinie wird nun die, uns interessierende, die Schwingungen der Frequenz acht gelegt und darauf eine Schwingung mit doppelter Frequenz, die dafür sorgt, dass das Endergebnis genau durch die vorgegebene Zahlenfolge läuft
15:29Auf jeden Fall ist es so, dass wir an der Zahlen 8 und 16 zweifelsfrei erkennen können, dass die gesuchte Periode 4 sein muss, weil wir 32 Eingabewerte hatten
15:35Ganz so einfach wird es aber bei Shors Algorithmus nicht werden
15:42Ein Grund dafür ist, dass die Periode nicht unbedingt einen Teiler der Eingabelänge sein muss
15:48Ich habe hier zur Illustration eine Folge mit der Periode fünf genommen, obwohl wir das Verfahren auch die 222 gar nicht anwenden würden
15:54Wir bekommen rechts ein quasi verschmiertes Ergebnis, wie vorhin bei den Daten mit dem zufälligen Rauschen, können jedoch dominante Frequenzen bei 6 und 13 erkennen, aber was sollen wir mit denen machen? Die Periode, die wir herausbekommen wollen, ist 32 geteilt durch fünf ist 6,4, und die Werte 6 und 13 sind die besten ganzzahligen Ehrungen für 6,4 und 2 x 6,4, mehr können wir nicht erwarten, wir sehen aber gleich, dass
16:26Uns das auch schon hilft, vorher müssen wir aber noch klären, inwieweit das, was wir hier zur Einstimmung sehen, vom wirklichen Shor-Algorithmus abweicht
16:31Der erste Unterschied ist, dass wir, damit man das vernünftig visualisieren kann, viel zu wenige Samples sehen
16:37Damit die Fourier-Transformation in der Lage ist, auch bei großen Perioden die dominanten Frequenzen zu erkennen, braucht man mindestens n Quadrat Samples, wenn n die Zahl ist, von der wir die Anteile suchen
16:49Für n gleich 22 wäre das 484, und man muss in der Praxis die nächste Zweierpotenz nehmen, in diesem Fall also 2 hoch 9 gleich 512
16:56Zweitens werden wir später leider niemals das gesamte Frequenzspektrum zu Gesicht bekommen, sondern nur eine Frequenz
17:03Dabei hängen die Amplituden, die wir rechts sehen, mit der Wahrscheinlichkeit dafür zusammen, welche Frequenzen sein wird
17:09Die Frequenzen, die in der Darstellung als die dominanten zu erkennen sind, sind zum Glück auch die, die wir am wahrscheinlichsten sehen werden
17:14Dass wir nur einen Wert bekommen und nicht einmal bestimmen können, würden wir sehen, liegt natürlich daran, dass die Fourier-Transformation auf einem Quantencomputer durchgeführt werden wird
17:29Sie haben vielleicht Zwischendurch gedacht, dass gleich die sogenannte schnelle die Transformation ihren Auftritt haben würde
17:36Die ist zwar erstaunlich schnell, aber für die Größenordnung, die es hier geht, immer noch viel zu langsam
17:44Bevor wir nun jedoch endlich wieder Quanten-Schaltkreise sehen, noch ein paar Details für die, die es genauer wissen möchten: Wie gehen wir mit der Frequenz um, die wir bekommen? Wie kommen wir von der auf die Periode? Da gibt es zum Glück einen recht einfachen Weg
17:49Fangen wir mit dem simplen Fall an, dass die Periode 1 Teiler der Anzahl der Samples ist
17:54In unserem Beispiel würden wir als Messergebnisse einen der Werte 0, 8, 16, 24 erwarten
17:58Die nun habe ich weggelassen, die kann immer mal wieder vorkommen und liefert uns leider keine verwertbaren Informationen
18:05Da stoßen wir wirklich an die Grenzen der uns der Zufall auferlegt und müssten den Algorithmus erneut durchlaufen, aber was machen wir, wenn wir eine Acht bekommen? Die Analyse sieht so aus: Die Frequenz 8 kommt dadurch zustande, dass die Periode 4 genau acht Mal in das Fenster von 32 Samples passt
18:23Wir müssen also nur 32 durch 8 teilen, unterhalten 4
18:28Bei der Division von 32 durch 16 hätten wir das Ergebnis vier halbe, das ist auch Sinnvoll, denn wir hatten ja gesehen, dass diese Oberschwingungen zur Rekonstruktion der Kurve nötig ist, und dass ihre Frequenz ein ganzseitiges Vielfaches der Grundfrequenz sein muss
18:41Es gibt einen kleinen Haken, der aber nicht so schlimm ist: Wenn Sie 32 / 16 dividieren, erhalten Sie nicht vier halbe, sondern zwei
18:47Sie können den Quotienten nicht direkt ansehen, dass sozusagen vier halbe gemeint ist
18:53Das heißt in der Konsequenz, dass die Zahl, die Sie durch die Division ermitteln, die Periode ist oder ein Teiler der Periode
18:59Das ist aber auch nicht so schlimm, wenn Sie aussichtsreiche Kandidaten nehmen
19:03Können Sie leicht prüfen, ob es sich wirklich um die Periode handelt
19:07Das ist nicht vergleichbar mit dem vorhin gezeigten mühsamen Verfahren, bei dem man sukzessive alle Potenzen berechnet hat
19:11Hier heißt das konkret, wenn Sie 16 messen, dann erhalten Sie als Patienten 2
19:18Sie berechnen 7 hoch 2 Modulo 15 und sehen, dass das nicht eins ist, also probieren Sie es mit 2 x 2, das heißt, Sie probieren 7 hoch 4 Modulo 15, und in diesem Fall kommt eins heraus, und Sie haben die Periode gefunden
19:32Hätte das auch nicht geklappt, hätten Sie noch 7 hoch 6, 7 hoch 8 und so weiter probieren müssen, aber nur bis maximal 7 hoch 14
19:38Weil die Periode kleiner als 15 sein muss
19:44Das klingt jetzt so, als müsste man doch wieder ganz schön viele Werte durchprobieren, aber in der Praxis werden sie fast nie so kleine Quotienten wie zwei erhalten und im Allgemeinen sehr früh einen Treffer landen
19:49Das Verfahren mit dem Dividieren klappt sogar bei den Spiegelbildern
19:56Wir würden hier vier Drittel erhalten und könnten sofort die vier testen
20:01Falls Sie sich fragen, warum das klappt, schauen Sie sich die Nebenrechnung unten an, bei der die mit den Care-Werten gerechnet habe
20:07Die drei kommen nicht daher, dass es um das Dreifache der Grundfrequenz
20:13geht potenziell weniger Aufwand hat man allerdings, wenn man nicht mit dem Messwert 24, sondern mit dem Spiegelbild 8 rechnet
20:18Entscheidend für den Algorithmus ist aber lediglich, dass wir für alle Messwerte außer 0 einfach die Anzahl der Samples durch den Messwert teilen können und dann die Periode oder ein Teiler der Periode erhalten
20:25Das war allerdings die schöne und leider seltene Variante, in der es genau passt
20:32Im allgemeinen Fall sollte man etwas vorsichtiger formulieren und eher vom Raten als vom Ermitteln der Periode sprechen, obwohl es auch hier im Endeffekt so ist, dass man in den meisten fällen den richtigen Wert erhält
20:44In unserem konstruierten Beispiel 3x Modulo 22 sind die dominanten, also bei einer Messung am häufigsten zu erwarten, denn Werte 6, 13, 19 und 26 mit der 6
20:50An die richtige Frequenz, die die Fourier-Transformation uns nicht liefern kann, wäre 32/5, also 6,4 gewesen, mit der die Division von der letzten Folie würde 32 geteilt durch 6,45 liefern und wir dann glücklich
21:08Wir müssen aber mit 6 statt 6,4 vorlieb nehmen und können nur sagen, dass 32 geteilt durch 6 ungefähr 5 ist
21:15Ebenso ist 32 geht durch 13 ungefähr fünf halbe
21:23Es sieht so aus, als bräuchten wir ein Verfahren mit
21:30dem man einen Bruch in der Nähe des berechneten Quotienten finden muss, dessen Zähler nicht so groß ist, da der Zähler die Periode oder einfach daran sein soll
21:37Außerdem kann man auch genau spezifizieren, was in der Nähe bedeuten soll, das hängt von der Anzahl der Samples ab
21:44Je mehr Champions wir haben, desto geringer kann die Abweichung der krummen Frequenz von der richtigen sein
21:50Ein Verfahren, dass solche Brüche liefert, gibt es zum Glück, wir greifen wieder verschiedene Bereiche der Mathematik ineinander, man verwendet dazu die sogenannte Kettenbruchentwicklung, die genau für solche Probleme
21:56Gedacht ist, die wird tatsächlich die Werte liefern, die wir hier sehen, und mit denen kommen wir immer direkt, oder mit wenigen Fehlversuchen, auf die richtige Periode 5
22:07Ein kleiner Wermutstropfen ist, dass die Kettenbruchentwicklung manchmal auch Brüche liefert, die ebenfalls die Bedingung erfüllen, aber nicht zur Periode führen
22:13Auch hier gilt jedoch, dass das nicht oft passiert, und man sich durch Nachrechnen leicht überzeugen kann, dass die so erhaltenen Kandidaten nicht die Periode liefern
22:20Wenn Sie noch nie etwas von Kettenbrüchen gehört haben, dann schauen Sie sich vielleicht nur ein Video
22:26Über den goldenen Schnitt, da sollte man eigentlich genug erfahren und zu verstehen, wie das funktioniert
22:32Den ganzen Ablauf vom Messwert bis zu einer Liste von Kandidaten, die Teile der Periode sein könnten, zieht man hier als Julia Programm bei
22:38Bei den dominanten Frequenzen wird die Funktion meistens einen Kandidaten auswerfen und in seltenen Fällen mehrere
22:44Sollten wir zufällig eine der sehr unwahrscheinlichen Frequenzen erwischen, so bekommen wir meistens eine leere Liste zurück und müssen uns gar nicht erst mit dem Prüfen von Kandidaten aufhalten
22:56Ich habe das meinen PC exemplarisch für den Fall, dass wir Teiler von 45 suchen, mit einer schnellen Fouriertransformation durchrechnen lassen
23:00Wir würden mit zwei hoch elf Samples arbeiten
23:05Die 13, außer der 0, wahrscheinlichsten Rückgabewerte sind zusammen mit der jeweils geratenden Zahl aufgeführt
23:09In den beiden häufigsten Fällen bekommen wir die korrekte Periode 12 auf dem Silbertablett geliefert, ansonsten einen Teil davon
23:16Nur in zwei Fällen ist das Resultat gar nicht zu gebrauchen
23:22So richtig große Zahlen sehen alle noch signifikant besser aus
23:28Wichtig ist außerdem, dass wir ein ganz simples Programm sehen, dass sich effizient Klassisch implementieren lässt, es wird nach dem Durchlaufen des Quanten-Teils des Algorithmus ausgeführt, um die Resultate dieses Teils zu analysieren
23:41Das Verfahren ist also ein gutes Beispiel für meine, schon im ersten Video der Serie ausgesprochene, These, dass man sich Quantencomputer nicht als allein stehende Geräte, sondern eher als Co-Prozessoren in einem herkömmlichen Rechner vorstellen sollte
23:47Zur Erinnerung noch einmal die Folie dazu: Der Shor-Algorithmus, das ist im Wesentlichen ein klassischer Algorithmus, der nur für die Ermittlung der Periode bzw
24:00für das Finden eines guten Kandidaten für die Periode, die Kuh befragt, und dafür nun endlich der Quanten-Schaltkreis
24:07Sie werden zugeben müssen, dass das recht übersichtlich ist, allerdings steckt der Teufel natürlich im Detail
24:11Eines dieser Details ist, dass an mehreren Stellen Punkt, Punkt, Punkt steht
24:15Es sind nicht etwa nur vier Cubits, wie man auf den ersten Blick denken könnte, sondern es werden recht viele sein
24:18Genauer, wenn wir die Periode von Arrow ECS Modulen suchen, brauchen wir unten genügend Jupes, um die Zahlen bis Ende näher darstellen zu können, und oben wollen wir sogar Zahlen des etwa drei prozentieren können, die schon
24:30Sagte, soll damit sichergestellt werden, dass die Fourier-Transformation eine ausreichend große Menge an Samples bekommt
24:36Abgesehen davon hat diese Schaltung natürlich noch das kleine Problem, dass wir zwei Bausteine bisher gar nicht kennen
24:42Oben rechts steht QFT, wie Sie sich schon gedacht haben, für Quanten-Fourier-Transformation, und das Gatter in der Mitte soll die Funktion auch ex-modul N berechnen
24:55Das Wort Quanten-Fourier-Transformation mag etwas furchteinflößender klingen, aber der aufwendigste Teil an dieser Schaltung ist die modulare Exponentiation, der wir uns zuerst zuwenden wollen
25:01Hier muss für jedes a und für jedes n eine separate Schaltung realisiert werden, und die Berechnung muss effizient durchgeführt werden
25:07Das im Detail zu erklären, würde zu weit führen
25:13Ich will im Wesentlichen nur darauf eingehen, dass es zumindest in der Theorie möglich ist, die Umsetzung überlassen wir dann den Praktikern
25:19Klären wir eine Frage, die Sie sich eventuell schon gestellt haben: Die Funktion, deren Periode wir brauchen, ist keine boolesche Funktion im Sinne des vierten Videos, denn ihr Wertebereich umfasst mehr als nur die beiden Zahlen Null und Eins, hier die Wertetabelle für unser Beispiel 7x
25:37Modus 15, bei dem sich Werte wie 13, 7 ergeben können, die würden wir natürlich sowohl in einem klassischen Computer als auch in einem Quantencomputer binär darstellen
25:44Das sähe dann so aus, und eigentlich steht hier schon alles, was man braucht
25:54Man teilt die Funktion F, die man als Gatter realisieren will, einfach in ihre Komponentenfunktionen auf
26:04F0 von X ist der Wert der Einerstelle von F von X, 111 von Access der Zweigstelle von Evonik SVWW 00 bis 1130 Schiff Funktionen, dass und wie man die als Quanten Katar realisieren kann, haben wir uns im vierten Video bereits überlegt, Stichwort Quanten Orakel, man
26:14Kann also eine Schaltung wie die gezeigte bauen, und auf der Leitung von y i wird dann der Wert fi von xy berechnet
26:21Jetzt kann man alles wieder als ein Gatter betrachten und hat damit im Prinzip für jede Berechnung, die man mit klassischen Göttern durchführen kann, einen entsprechenden Quellenbaustein
26:27Ich wiederhole jedoch, dass die Umsetzung in der Praxis nicht gerade ein Kinderspiel ist, und es nicht nur um die prinzipielle Realisierbarkeit geht, sondern auch um die Effizienz
26:39Man macht das ja alles nur, weil man signifikant schneller aktualisieren möchte als mit klassischen Verfahren
26:45Vorsprung, den ein Quantencomputer potenziell bietet, will man nicht dadurch verspielen, dass man die Berechnung der zu untersuchenden Funktionen im Schneckentempo durchführt, aber die Details würden uns, wie gesagt, so weit vom Thema wegführen
26:57Wir halten fest, dass es bekannte Verfahren gibt, um modulare Exponentiationen effizient zu realisieren, und das Land, die in klassische Schaltungen übersetzen kann, die man dann wiederum ohne Effizienzverlust in Quanten-Gatter konvertieren kann
27:09Stellen wir uns also vor, wir wollten die Teiler von 15 berechnen und wir hätten einen Quanten-Baustein, der sieben hoch 15 berechnet, ein Gatter zur Ermittlung der Periode dieser Funktion, sehen Sie hier
27:20Der Unterschied zum bereits gezeigten Zeitplan ist, dass auf dieser Folie die Anzahl der Qubits explizit angegeben ist
27:25Allerdings sind es eigentlich zu wenige
27:32Ich hatte vorhin erwähnt, dass man mindestens 15 Quadrat Samples haben will, und dafür bräuchten dann oben nicht 508 Qubits
27:3815 mal 15 ist größer als 2 bis 7, aber kleiner als 28
27:44Wir werden uns aber mit fünf Qubits zufrieden geben, denn der Programmablauf soll visualisiert werden, und bereits fünf Cubes stellen uns vor große Herausforderungen
27:50Ich hoffe, Sie sehen die HD-Version des Videos auf einem schönen großen Bildschirm
27:56Sie haben sich vielleicht noch an das Bild mit den Zuständen eines Registers mit sieben Qubits aus dem zweiten Video erinnert
28:02Hier haben wir insgesamt sogar neun Qubits und damit 512 klassische Zustände, die auf eine bestimmte Art angeordnet sind, die uns die Interpretation der grafischen Informationen erleichtern soll
28:09Horizontal aufgetragen, etwas dunkler, sind die 32 möglichen klassischen Zustände der fünf Qubits, die im Schaltplan an den fünf oberen Leitungen liegen
28:16Vertikal sieht man die 16 Zustände der unteren
28:22Vier Qubits, lese Beispiel: Der hervorgehobene Kreis liegt in der Spalte zu Cat 18 und der Zeile zu Cat 5
28:28Damit repräsentiert er das Tensorprodukt Cat 18 mal Cat 5 dieser beiden Zustände
28:34Man könnte das auch als Zustand Cat 93 des gesamten Registers aus neuen Qubits bezeichnen, aber es ist für das Verständnis besser, wenn man sich zwei Register mit fünf beziehungsweise vier Qubits vorstellt
28:41Schauen wir zunächst, wie unser Funktionsbaustein arbeitet
28:49Dafür stellen wir im Eingaberegister den Wert 23 und im Ausgaberegister 0 1
28:57Das ergibt den Zustand, den wir jetzt sehen, nur der Zustand zur Spalte
29:02Cat 23 und zur Zeile Kette 0 hat die Amplitude 1, alle anderen haben die Amplitude 0
29:077 hoch 23 modulo 15 ist 13, darum sieht es nach Durchlaufen der Funktion so aus
29:13Die Register befinden sich im klassischen Zustand Cat 23-mal Cat 13
29:19Mit anderen Worten, das Argument 23 ist noch da, den Funktionswert 13 kann man aber ebenfalls ablesen
29:25Dann könnte Quantencomputer also fast wie Taschenrechner verwenden, wenn die Dinger momentan nicht so teuer und so schwer zu bekommen wären
29:31Der Ausgangspunkt für den Algorithmus von Shaw ist allerdings der, dass beide Register auf Null gesetzt werden, und dann wird die Hadamarer Transformation angewendet
29:42Jetzt haben alle Zustände, bei denen sich das untere Register immer noch im Zustand 0 befindet, dieselbe Wahrscheinlichkeit
29:48Nun wenden wir die Funktionen an, deren Periode wir wissen wollen, und sehen erneut, was Quantencomputer so besonders macht: wegen der Superposition, die durch die Heimattransformation hergestellt wurde, haben wir mit einem einzigen Durchlauf des Funktionsbausteins 32 Funktionswerte auf einmal berechnet, dass zum Beispiel links oben in Spalte cat 3 und Zeile cat 13 eine positive Amplitude zu sehen
29:58Das bedeutet, dass sich bei der Berechnung von sieben hoch drei Modul 15, der Wert 13 ergeben hat
30:09Beachten Sie, dass natürlich in jeder Spalte nur ein Zustand eine nicht verschwindende Amplitude hat
30:20Werden sonst noch etwas auf das sind im Prinzip genau die Daten, mit denen wir vorhin eine Fourier Transformation durchgeführt haben, und das wollen wir natürlich auch machen
30:37Was noch fehlt, ist die Quantenvariante der Fourier Transformation, darum kümmern wir uns jetzt
30:43Eine diskrete Fourier Transformation ist eigentlich nichts weiter als eine Multiplikation mit einer bestimmten Matrix, die man hier sieht
30:49In der Matrix stehen Nach einem bestimmten Muster Potenzen von Omega in, wobei Omega in die komplexe n-te Einheitswurzel ist, die den Betrag 1 hat und deren Phase ein n-tel von 360° ist, und die dazu inverse diskrete Fouriertransformation sieht fast genauso aus
31:03Sie unterscheidet sich nur durch den Faktor 1 durch n und dadurch, dass die Einträge der Matrix jeweils die konjugiert komplexen Werte ihrer Gegenstücke links sind
31:10Invers heißt diese Transformation natürlich deshalb, weil ihre Anwendung auf das Ergebnis der Fouriertransformation den Eingabevektor wiederherstellt
31:20Sie repräsentiert die Umkehrfunktion der zugehörigen
31:30Diskreten Fouriertransformation und entsprechend ist die Matrix rechts die Inverse der Matrix links und umgekehrt, weil die beiden Matrizen offensichtlich symmetrisch sind, und weil Care Werte der Einheitswurzeln durch Konjugieren entstehen, ist die Matrix rechts also fast die aktivierte der linken Matrix, nur der Faktor stört
31:40Das kann man aber dadurch beheben, dass man den Faktor zu gleichen Teilen auf beide Matrizen verteilt, damit ist die Matrix unten nachdem vor Überlegungen um IKEA und das ist die Matrix der Quantenkurier Transformationen, so einfach ist das, Fußnote, Sie wissen
31:53Vielleicht, dass ich für die schnelle Fourier Transformation besonders gut die Matrizen eignen, bei denen eine Zweierpotenz ist
32:05Für die Quanten-Fourier-Transformation ist immer eine 2er-Potenz, das gilt ja zwangsläufig für alle Matrizen, die unitäre Transformationen auf Quantenregistern darstellen
32:11Was jetzt noch fehlt, ist die Frage der Implementation
32:17Im zweiten Video hatte ich erwähnt, dass man aus technischen Gründen typischerweise nur mit Transformationen arbeiten will, an denen nicht mehr als zwei oder drei Qubits beteiligt sind
32:22Wir müssen die Quanten-Fourier-Transformation Also, entsprechend zerlegen
32:27Dazu schauen wir uns zunächst einmal an, was QFT, die Quanten-Fourier-Transformation, für zwei Qubits mit den klassischen Zuständen 8 Catic soll, also für an der Basis Faktoren Cat 0 bis 3 stehen
32:39Wir könnten dann das Ergebnis der Transformation, dass wir hier sehen, direkt der Matrix entnehmen
32:44Sie wissen ja, die Spalten einer Matrix sind die Bilder der Basis Sektoren
32:50Hier habe ich die Summe ihrer einzelnen Summen zerlegt, dann sieht man nämlich, dass man sie als Tensorprodukt zweier Ein-Qubit-Zustände darstellen können
32:55Rechnen Sie nach, und es gibt noch eine Vereinfachung
33:01Die jedem, der schon einmal mit Einheitswurzeln zu tun hatte, klar sein wird, man kann Omega hoch 14 Quadrat durch Omega hoch 2 ersetzen
33:09Das gleiche Muster findet man auch für größere Transformationen
33:17Hier habe ich es exemplarisch nach einer Kurve 8 aufgeschrieben, da erhalten wir einen Tensor Produkt mit drei Faktoren, und wir können erneut einige Potenzen von Einheitswurzeln durch Einheitswurzel kleinerer Ordnung ersetzen
33:25Außerdem, das hätten wir auf der letzten Folge auch machen können, verteilen, wir werden noch den Vorfaktor gleichmäßig auf alle drei Faktoren des Tensor Produktes, diese Zerlegung
33:31Als Tensorprodukt ist der eigentliche Witz dieser Rechnung, denn damit haben wir die Ergebnisse für die einzelnen Qubits separat dargestellt
33:37Der Faktor ganz rechts entspricht der Einerstelle der Binärdarstellung, der Faktor neben der Zweierstelle und so weiter, und mit den einzelnen Faktoren rechnen wir nun weiter
33:49Vielleicht ist Ihnen ja schon aufgefallen, dass die eine gewisse Ähnlichkeit mit dem Ergebnis der Hadamard-Transformation haben
33:54Tatsächlich ist die Hadamard-Transformation für ein Qubit identisch mit QFT 2
33:59Ich habe noch einmal aufgeschrieben, wie Sie auch die beiden Basis
34:03Zustände eines Qubits wirkt
34:07Wenn wir x0 als die Einerstelle eines 3-Qubit-iks interpretieren, dann können wir der letzten Folie entnehmen, dass die Hadamard-Transformation von Cat x0 exakt die Viererstelle von QFT 8 angewandt auf Cat x liefert, Deutschland
34:20Zwar noch der Faktor Omega 2 hoch x4 Cat 1, aber Omega 2 ist einfach -1, und das entspricht den unterschiedlichen Vorzeichen in der Tabelle
34:28Stehen für diese Beobachtung ist allerdings entscheiden, dass der Wert der besagten Führerstelle nur von der Einerstelle von IKS abhängt
34:34Spuren Sie eventuell noch einmal ein Stück zurück
34:38Und zwar, es ändert sich das an XCOM dort niemals
34:42Exponent von Omega 2 vor, und dabei geht es nur darum, ob es gerade um gerade ist
34:47Aus analogen Gründen hängt die Zweigstelle des Ergebnisses nur von den letzten beiden Stellen des Arguments ab, weil für die ganz eiligen Potenzen von Omega 4 nur der Rest Modul U4 ist
35:00Exponenten relevant ist, was passiert, wenn wir die Hadamard Transformation auf die Zweigstelle Cat X1 anwenden? Sehen wir jetzt, in zwei der vier Fälle ist das Ergebnis schon komplett korrekt, in den anderen beiden Fällen ist es noch nicht ganz richtig, es fehlt noch der Faktor Omega 42, konsumenten ich
35:11Habe auch gleich farblich hervorgehoben, woran man erkennen kann, wann dieser Faktor fehlt
35:18Er fehlt genau dann, wenn die Einerstelle nicht null ist, und für die Einerstelle des Ergebnisses ergibt sich ein ganz ähnliches Muster
35:24In zwei Fällen liefert die Hadamard-Transformation von Cat X2 schon das richtige Ergebnis, in den anderen Fällen müssen wir noch den rechten sogenannten mit Omega 4 oder mit Omega 8 oder mit beiden multiplizieren
35:36Auch hier kann man an den niedrigwertigen Stellen ablesen, wann mit welchem Faktor multipliziert werden muss
35:42Sie kennen den Text schon, den ich jetzt sage, das Ging natürlich viel zu schnell und daher sollten Sie das Video anhalten und sicherstellen, dass Sie auch alles verstanden haben und ich mich nicht vertippt habe, aber Sie wissen ja selbst, was gut für Sie ist
35:53Die Al-Ahmar-Transformation ist inzwischen ein alter Bekannter, aber kennen wir eine Transformation, mit der wir die Korrekturmultiplikation der rechten Spalte durchführen können? Das ist der sogenannte Facelift, den wir als Z-Rotation im zweiten Teil kennengelernt haben
36:11Er lässt sich theoretisch für jeden Winkel 4 realisieren und der Matrix sieht man sofort an, dass sie und er ist die Grafik
36:17zeigt, dass sich durch diese Transformation die Wahrscheinlichkeit nicht ändert, sie hat lediglich Auswirkungen auf die relative Phase, die im Beispiel um 30 Grad größer wird
36:22Ist für die Phase der Einheitswurzel Omega zwei hoch K, dann nennt man die entsprechende Phasenänderung typischerweise RK/2
36:34R2 ist also beispielsweise die Drehung um die halbe, 90 Grad, und R3 ist die Drehung um 45 Grad
36:41Diese Phasenänderungen sind genau die, die wir brauchen, allerdings brauchen wir sie ja nicht immer, sondern nur unter bestimmten Bedingungen
36:46Wir hatten im vierten Video gesehen, wie man aus jeder Transformation, eine durch ein anderes Qubit gesteuerte Transformationen machen kann
36:54Das geht natürlich auch mit dem Facelift und liefert den Controller
37:00Facelift liegt auf der Steuerleitung, einer der beiden klassischen Zustände, dann läuft es so, wie es nun am Beispiel von R3 dargestellt ist
37:06Hat die Steuerleitung den Zustand Cat 0, dann passiert nichts
37:12Hat sie den Zustand Cat 1, dann wird in der relativen Phase gedreht, in diesem Fall um 45 Grad, und damit ist klar, wie man QFT 8 mit kleinen Gattern realisiert
37:21Das muss man quasi nur noch von der Tabelle der vorletzten Folie abschreiben
37:29Beachten muss
37:38man dabei lediglich, dass man das in der richtigen Reihenfolge macht, beispielsweise muss die Einerstelle als letzte dran kommen, denn sie wird vorher noch zum Steuern der anderen Phasenänderung benötigt, aber im Prinzip sollte dann klar geworden sein, wie man beliebig große Quanten-Fouriertransformationen aus Hadamard-Transformationen und gesteuerten Phasenänderungen zusammenbauen kann
37:47Eine Kleinigkeit fehlt allerdings noch, sehen Sie, wenn man es so macht, dann liegen die Ausgangssignale in der falschen Reihenfolge an, die höherwertigen Qubits enden, das macht aber nichts, entweder Berücksichtigt man, dass in den Folge-Gittern oder man zu 100 % verwendet, dass Rob Katter die jeweils zwei Teams vertauschen können, um zu sortieren, jedenfalls können wir nun zu dem Punkt zurückkehren, an dem wir vorhin im Shor-Algorithmus stehen geblieben waren
38:14Nach Durchlaufen der periodischen Funktion stehen 32 Funktionswerte im Quantenregister und warten auf die Fourier-Transformation
38:19Wenn man die nun anwendet, ergibt sich dieses Bild, und damit sind wir fertig
38:26Wenn wir jetzt die oberen fünf Qubits messen, dann kann ganz offensichtlich nur einer der vier Zustände Cat 0, Cat 8, 16 oder 24
38:30herauskommen
38:35Es ist genau so, wie wir uns das schon anhand der normalen diskreten Transformationen überlegt hatten
38:39Es ist sogar noch etwas besser, weil man der Grafik gerade noch so ansehen kann, dass alle 16 Zustände, deren Amplituden nicht verschwinden, dieselbe Wahrscheinlichkeit haben
38:45Die störende 0 hat also eine geringere Wahrscheinlichkeit als bei der klassischen Rechnung
38:51Das liegt daran, dass die Eingabewerte bei der Quanten-Fouriertransformation normalisiert sein müssen
38:57Das macht unser Leben in diesem Fall leichter
39:03Für den Fall, dass noch nicht ganz klar ist, was hier passiert, gehe ich Noch mal einen Schritt zurück: Vor der Fouriertransformation und hinter der Anwendung der periodischen Funktionen, stellen Sie sich vor, wir würden jetzt das untere Register messen, das vertikal aufgetragen ist
39:16Das hat auf das Ergebnis, das uns interessiert, keine Auswirkungen, weil diese Qubits für den nachfolgenden Schritt nicht mehr gebraucht werden, aber es macht vielleicht deutlicher, wie der letzte Schritt des Algorithmus funktioniert
39:22Bei so einer Messung können, wie man hier sieht, nur die Werte 1, 4, 7 oder 13 herauskommen
39:29Nehmen wir an, das Ergebnis wäre 4, dann sieht es danach so aus
39:36Wir wissen, Aus dem dritten Video, das bei Messen die Zustände auf den gemessenen Untervektorraum projiziert werden, darum befinden sich nun alle nicht verschwindenden Athleten in der Zeile zu Cat 4, in der es noch einmal viel deutlicher zu sehen, dass die Eingabe für die für ihre Transformation periodisch mit dr 04 ist
39:54Das Ergebnis der Fourier Transformation würde dann so aussehen
39:58Auf die anschließenden Messungen hatte unsere Messung zwischendurch, wie gesagt, keinen Einfluss
40:01Das waren dann aber wirklich der ganze Shor-Algorithmus
40:05Ich will das aber noch einmal für unser Beispiel drei hoch x-modelle 22 vom
40:11fohlen durchlaufen lassen, um zu zeigen, wie es aussieht, wenn nicht alles so schön passt
40:17Diese Funktion würde zwar bei Teilbarkeitsuntersuchungen nicht auftreten können, aber wir können dann hier sehen, wie sich der Algorithmus verhält, wenn die Periode kein Teiler der Ordnung der Fourier-Transformation ist
40:24Zur Erinnerung: Die Periode ist fünf, man sieht es ja auch, und fünf ist kein Teiler von 32
40:31Die Zuschauer mit den großen Bildschirmen sehen jetzt, dass das Ergebnis der Fourier-Transformation etwas unruhiger ist
40:36Alle Kreise, die nicht komplett leer sind, repräsentieren Zustände, deren Wahrscheinlichkeit größer als 0,1 Prozent ist
40:43Man sieht aber auch, dass sich die wesentlichen Wahrscheinlichkeiten auf die Spalten 6, 13, 19 und 26 konzentrieren
40:49Die Wahrscheinlichkeit, eines dieser vier Ergebnisse zu bekommen, liegt bei etwa 60 Prozent, und bei allen vieren würde die Rate-Funktion, die wir kennengelernt haben, ein richtiges Ergebnis liefern
40:55Zum Abschluss noch ein paar realistischere Wahrscheinlichkeiten dafür, dass man mit dem Verfahren die Periode im ersten Versuch findet
41:02Das Wort "realistisch" steht in Anführungszeichen, weil auch diese Zahlen immer noch Lichtjahre von denen entfernt sind, für die Chance
41:09Der Algorithmus ist eigentlich gedacht
41:15Man sieht aber schon, dass die Wahrscheinlichkeit nach und nach besser werden
41:21Wenn man bereits bei einem Durchlauf in mehr als drei Viertel aller Fälle Erfolg hat, dann liegt nach zwei Durchläufen die Wahrscheinlichkeit für Händen des linken des Verfahrens bei etwa 6 %, und nach fünf Durchläufen ist die geringer als ein Promille
41:27Und wenn ein Durchlauf schnell ist, dann sind es auch fünf
41:33Wenn man es wirklich eilig mit dem Code knacken hat, kann man ja auch fünf Quantencomputer parallel laufen lassen über den Zufall suspect
41:39Muss man sich also keine großen Gedanken machen, aber wie ist denn da der Stand der Technik? Im Jahr 2001 wurde der Shor-Algorithmus bei IBM erstmals auf einem echten Quantencomputer erfolgreich durchgeführt
41:50Man hat die Zahl 15 faktorisiert, und ich feuere einfach mal, dass drei mal fünf herauskam
41:57Der bisherige Weltrekord wurde laut Wikipedia 2012 aufgestellt
42:03Man hat, ich zitiere, sich fest die Zahl 21 faktorisiert
42:07Die Theorie ist der Platz ist also weit voraus
42:11Im nächsten Video werde ich ein paar Worte dazu sagen, warum Quantencomputer bisher noch weit von der Marktreife entfernt sind, und was man
42:16Dagegen unternehmen kann, außerdem werden wir auch über die Simulation von Quantencomputern sprechen und fragen, ob Alan Turing durch Quantencomputer widerlegt wurde, und am Ende gibt es Literaturhinweise, damit Sie all die Details nachlesen können, die in den Videos bisher verschwiegen habe.
