1. Grundlagen des Quantenregisters und das Suchproblem [0]

thumbnail

  1. Zustand eines Quantenregisters [0]

    1. Der Zustand eines Quantenregisters mit Qubits ist ein Vektor von Gewichten. [0]
    2. Dieser Vektor hat exponentiell viele Komponenten, nämlich . [1]
    3. Die Gewichte () sind komplexe Zahlen. [2]
    4. Der Vektor hat die Länge 1 und liegt auf der Einheitskugel. [2]
    5. Die Quantenphysik erlaubt jede umkehrbare Operation auf dieser Einheitskugel. [2]
    6. Manche dieser Operationen sind effizient in Quantenhardware realisierbar. [3]
    7. Quantenrechner rechnen im Verborgenen; die Zustände sind nicht direkt sichtbar. [5]
    8. Bei einer Messung sieht man einen klassischen Zustand . [6]
    9. Die Wahrscheinlichkeit, Zustand zu sehen, ist . [6]
    10. Diese Quadrate summieren sich zu eins, was eine Wahrscheinlichkeitsverteilung ergibt. [6]

  2. Das Suchproblem in einer großen Menge [7]

    1. Die Eingabe ist ein klassisches Schaltnetz (bestehend aus UND, ODER, NICHT). [8]
    2. hat Eingaben ( bis ) und liefert 0 oder 1. [8]
    3. Die Funktion hat genau eine Eingabe (X Stern), bei der ist. [8]
    4. Ziel ist es, dieses zu finden. [8]
    5. Klassische Lösung: Man probiert alle Eingaben durch. [9]
    6. Im schlechtesten Fall muss man alle Elemente anschauen. [11]
    7. Im Mittel muss man die Hälfte der Elemente anschauen. [13]
    8. Klassisch ist keine bessere Lösung möglich. [13]
    9. Der Aufwand wächst klassisch linear in (der Größe der Datenbank). [14]
    10. Quantenrechner können dies mit einer Laufzeit proportional zu . [14]
    11. Dies ist ein beweisbarer, riesiger Unterschied, besonders bei großem . [15]

2. Grovers Algorithmus: Funktionsweise und Iterationen [17]

thumbnail

2.1. Die zwei Kernoperationen des Algorithmus [17]

  1. Überblick über Grovers Algorithmus [17]

    1. Der Algorithmus wurde von Grover Mitte der 80er Jahre erfunden. [17]
    2. Er benötigt nur Zeit (Wurzel aus Groß N). [17]
    3. Der Algorithmus ist einfach und nutzt zwei Operationen. [18]

  2. Erste Operation: Phasen-Inversion bei $X^*$ [19]

    1. Die Zustände reichen von 0 bis . [19]
    2. Irgendwo in der Mitte liegt der gesuchte Zustand . [19]
    3. Die Operation dreht das Vorzeichen des Gewichts von . [19]
    4. Alle anderen Gewichte bleiben unverändert. [19]
    5. Die Länge des Vektors bleibt unverändert, da nur das Vorzeichen wechselt. [19]
    6. Physiker nennen dies Phasen-Inversion bei . [20]

  3. Zweite Operation: Spiegelung am Mittelwert [22]

    1. Zuerst wird der Mittelwert aller Gewichte bestimmt. [23]
    2. Jedes Gewicht wird am Mittelwert gespiegelt. [24]
    3. Wenn ein Gewicht über dem Mittelwert liegt, geht es darunter. [24]
    4. Wenn ein Gewicht genau der Mittelwert ist, bleibt es unverändert. [25]
    5. Mathematisch wird das neue Gewicht zu . [27]
    6. Dies entspricht . [28]
    7. Der Grover-Algorithmus verwendet nur reelle Gewichte; Imaginärteile sind null. [29]

2.2. Ablauf und Wachstum des Gewichts von [30]

  1. Initialisierung [30]

    1. Alle Gewichte werden gleich gemacht. [30]
    2. Da die Gewichte reell sein müssen, werden sie auf gesetzt. [31]
    3. Dies stellt sicher, dass die Summe der Quadrate 1 ergibt (). [31]

  2. Die Schleife [32]

    1. Der Algorithmus geht in eine Schleife. [32]
    2. Die Schleife besteht immer aus Phasen-Inversion und Spiegelung am Mittelwert. [33]
    3. Die Schleife läuft, bis das Gewicht von über liegt. [33]

  3. Erster Schritt (Startzustand) [34]

    1. Alle Zustände von 0 bis starten mit dem Gewicht . [35]
    2. liegt irgendwo unter diesen Zuständen. [36]
    3. Phasen-Inversion: Das Vorzeichen von wird geändert. [37]
    4. Der nächste Zustand hat . [38]
    5. Alle anderen Gewichte bleiben bei . [39]

  4. Zweiter Schritt (Spiegelung am Mittelwert) [42]

    1. Der Mittelwert liegt leicht unter . [43]
    2. Fast alle Elemente sind , nur eines ist . [43]
    3. Spiegelung: Alle Gewichte werden am Mittelwert gespiegelt. [44]
    4. Die Gewichte, die bei lagen, gehen etwas nach unten. [44]
    5. Das Gewicht von wird nach oben geflippt. [44]
    6. Der Abstand von zum Mittelwert ist im Wesentlichen . [46]
    7. Das neue Gewicht von liegt bei ungefähr . [47]
    8. Die anderen Gewichte liegen nur klitzeklein unter . [49]

  5. Wachstum des Gewichts von $X^*$ [50]

    1. Nächste Phasen-Inversion: Das Gewicht von geht auf . [50]
    2. Nächste Spiegelung: Der Mittelwert bleibt im Wesentlichen . [51]
    3. Das Gewicht von wächst in jeder Iteration um . [52]
    4. Es startet bei und wächst zu nach Schritten. [53]
    5. Man möchte, dass das Gewicht so groß wie wird. [53]
    6. Dies erfordert ungefähr Iterationen. [55]

  6. Messung und Ergebnis [57]

    1. Klassisch würde man das Gewicht von beobachten und aufhören, wenn es über liegt. [57]
    2. Dies ist bei Quantenrechnern nicht möglich, da eine Messung den Zustand zerstört. [58]
    3. Quantenrechner wiederholen die Schleife Mal. [60]
    4. Nach dieser Anzahl von Iterationen ist das Gewicht groß genug. [61]
    5. Messung: Nach der Schleife wird gemessen. [61]
    6. Man erhält mit einer Wahrscheinlichkeit von . [62]
    7. Alle anderen Zustände werden mit einer exponentiell kleinen Wahrscheinlichkeit erhalten. [62]
    8. Wenn die Rechnung zehnmal wiederholt wird, ist man sich sicher, zu erhalten. [63]

3. Technische Realisierung und zukünftige Implikationen [64]

thumbnail

  1. Aktueller Stand der Technik [64]

    1. Quantenrechner mit wenigen Qubits (fünf, sechs) wurden realisiert. [64]
    2. Der Weltrekord beim Faktorisieren ist die Zahl 143 (). [65]
    3. Die Firma D-Wave verkauft angeblich einen Quantencomputer mit 503 Qubits. [67]
    4. Der Preis beträgt 10 Millionen, und Käufer sind Google, Amazon und die CIA. [69]
    5. Ein Artikel in Science diskutiert die D-Wave-Maschine. [70]
    6. Es ist umstritten, ob D-Wave wirklich ein Kernrechner ist. [72]
    7. Ein Test besagt, dass es kein Quantencomputer ist. [74]
    8. Es werden Effekte genutzt, aber nicht der versprochene Geschwindigkeitszuwachs erreicht. [74]
    9. An dem Test waren Käufer der Maschine beteiligt. [75]
    10. Das Urteil über D-Wave ist noch offen; es scheint noch nicht der Durchbruch zu sein. [76]

  2. Zusammenfassung und Ausblick [78]

    1. Heutige Rechner basieren auf klassischer Physik. [79]
    2. Quantenphysik erlaubt eine größere Klasse von Rechnern. [79]
    3. Diese sind potenziell schneller für manche Probleme. [80]
    4. Suchen in ungeordneten Datenbanken: Quantenrechner erreichen Laufzeit. [81]
    5. Klassisch ist kein sublinearer Algorithmus möglich. [81]
    6. Faktorisieren: Klassisch ist kein polynomieller Algorithmus bekannt. [82]
    7. Für Quantenrechner existiert ein Polynomzeit-Algorithmus. [83]
    8. Es ist nicht bewiesen, dass Faktorisieren klassisch nicht in Polynomzeit möglich ist. [84]
    9. Wenn Quantenrechner Realität werden, kann man faktorisieren. [85]
    10. Viele Kryptographie-Verfahren werden unsicher. [85]
    11. Diese Verfahren beruhen auf der Schwere von Faktorisieren oder diskretem Logarithmus. [85]
    12. Quantenrechner bieten neue Möglichkeiten für sichere Datenübertragung. [86]
    13. Digitale Unterschriften müssen neu gelöst werden und sind noch ungelöst. [87]
    14. Die Realisierung von Quantenrechnern steht noch am Anfang. [78]