Quantencomputing verständlich erklärt — Episode 10

Welche Probleme ein Quantencomputer tatsächlich schneller lösen kannQuantencomputing verständlich erklärt — Episode 10In Episode 9 haben wir gesehen, warum ein großer Quantencomputer weit mehr benötigt als nur viele Qubits.

Die Qubits müssen zuverlässig gesteuert, gekoppelt und gemessen werden. Fehler müssen erkannt und korrigiert werden, damit aus vielen physischen Qubits zuverlässige logische Qubits entstehen.

Nehmen wir nun an, wir hätten einen ausreichend großen und fehlerkorrigierten Quantencomputer.

Dann stellt sich die entscheidende Frage:

Was würden wir damit eigentlich schneller berechnen?

Denn auch ein perfekter Quantencomputer wäre keine allgemein schnellere CPU.

Nicht die Hardware entscheidet alleinBei einem klassischen Computer können wir ein vorhandenes Programm häufig auf einen schnelleren Prozessor übertragen und erhalten zumindest einen gewissen Geschwindigkeitsgewinn.

Bei einem Quantencomputer funktioniert das nicht so.

Ein klassisches Programm:

Eingabe
↓
klassische Instruktionen
↓
Ergebniswird nicht dadurch zu einem schnellen Quantenprogramm, dass wir seine Instruktionen durch Quantengatter ersetzen.

Wir benötigen einen Quantenalgorithmus, der die besonderen Eigenschaften der QPU gezielt nutzt.

Dazu gehören insbesondere:

Superposition
Phase
Interferenz
VerschränkungDer entscheidende Vorteil entsteht also nicht einfach durch schnellere Hardware.

Er entsteht durch einen anderen Rechenweg.

Was bedeutet überhaupt „schneller“?Bei Algorithmen interessiert uns nicht nur, wie viele Sekunden eine einzelne Berechnung benötigt.

Wir betrachten vor allem, wie der Aufwand wächst, wenn das Problem größer wird.

Ein einfaches Beispiel kennen wir bereits aus Grovers Algorithmus.

Bei N Möglichkeiten benötigt eine klassische Suche ohne weitere Struktur in der Größenordnung von:

NPrüfungen.

Grovers Algorithmus benötigt ungefähr:

√NPrüfungen.

Bei:

N = 1.000.000bedeutet das vereinfacht:

klassisch: etwa 1.000.000
quantum: etwa 1.000Der Quantencomputer führt dabei nicht einfach dieselben eine Million Prüfungen schneller aus.

Der Algorithmus benötigt weniger Schritte.

Das ist ein wesentlich stärkerer Vorteil als lediglich ein Prozessor mit höherer Taktfrequenz.

Grover: schneller suchenGrovers Algorithmus ist deshalb ein gutes erstes Beispiel.

Wir besitzen viele mögliche Kandidaten und eine Regel, mit der wir prüfen können, ob ein Kandidat die gewünschte Eigenschaft besitzt.

Klassisch:

Kandidat prüfen
↓
nächsten Kandidaten prüfen
↓
nächsten Kandidaten prüfen
↓
...Grover nutzt dagegen Quantenzustände und Interferenz.

Vereinfacht:

Superposition erzeugen
↓
Prüfbedingung anwenden
↓
Phasen verändern
↓
Interferenz
↓
passende Ergebnisse werden wahrscheinlicher
↓
messenDer Vorteil beträgt ungefähr:

N → √NDas ist ein quadratischer Vorteil.

Er ist erheblich, aber nicht für jedes Problem revolutionär.

Shor: ein wesentlich größerer UnterschiedEin berühmteres Beispiel ist Shors Algorithmus.

Er kann bestimmte mathematische Probleme wesentlich effizienter lösen als die heute bekannten klassischen Verfahren.

Dazu gehört die Zerlegung einer großen Zahl in ihre Primfaktoren.

Nehmen wir eine kleine Zahl:

15Ihre Primfaktoren sind:

3 × 5Bei kleinen Zahlen ist das trivial.

Bei sehr großen Zahlen wird die Faktorisierung jedoch schwierig.

Genau darauf beruht unter anderem die Sicherheit bestimmter heute verwendeter kryptografischer Verfahren.

Shor probiert nicht einfach schneller Faktoren ausMan könnte zunächst vermuten, ein Quantencomputer teste einfach:

2?
3?
5?
7?
11?
13?
...besonders schnell.

Das ist nicht die Idee von Shors Algorithmus.

Shor verwandelt das Faktorisierungsproblem in ein anderes mathematisches Problem.

Dabei wird nach einer Periode in einer mathematischen Funktion gesucht.

Vereinfacht:

Faktorisierungsproblem
↓
Periodenproblem
↓
Quantenalgorithmus
↓
Interferenz macht die Periodenstruktur messbar
↓
aus der Periode lassen sich Faktoren bestimmenWieder entsteht der Vorteil also nicht durch:

mehr Berechnungen pro Sekundesondern durch:

anderen RechenwegDie Struktur des Problems ist entscheidendGrover und Shor funktionieren sehr unterschiedlich.

Trotzdem haben sie etwas gemeinsam:

Wir entwerfen einen Quantenalgorithmus, der eine bestimmte mathematische Struktur des Problems gezielt ausnutzt.

Dazu wird das Problem so formuliert, dass diese Struktur durch Quantenzustände, Phasen und Quantengatter verarbeitet werden kann.

Anschließend werden die Amplituden so verändert, dass Interferenz die für uns relevante Information verstärkt oder sichtbar macht.

Vereinfacht:

Problem analysieren
↓
geeignete mathematische Struktur erkennen
↓
Quantenalgorithmus dafür entwerfen
↓
Quantenzustand gezielt verändern
↓
Interferenz nutzen
↓
nützliche Information messbar machenDer Quantencomputer entdeckt diesen Rechenweg also nicht selbst.

Der eigentliche intellektuelle Schritt besteht darin, überhaupt einen Quantenalgorithmus zu finden, der die Struktur eines Problems so nutzt, dass daraus ein Vorteil gegenüber klassischen Verfahren entsteht.

Genau deshalb gibt es nicht für jedes klassische Problem automatisch einen schnelleren Quantenalgorithmus.

Quantencomputer können Quantensysteme besonders natürlich beschreibenEine weitere wichtige Anwendung ist die Simulation von Quantensystemen.

Hier besitzt der Quantencomputer einen besonderen Vorteil.

In Episode 8B haben wir gesehen:

Bei n Qubits wird der gemeinsame Quantenzustand durch:

2^nAmplituden beschrieben.

Für einen klassischen Computer kann die vollständige Speicherung und Berechnung eines solchen Zustands sehr schnell extrem aufwendig werden.

Bei:

10 Qubitssind es:

1.024 AmplitudenBei:

30 Qubitsmehr als:

1 Milliarde AmplitudenEin klassischer Computer muss diese Zahlen tatsächlich in seinem Speicher verwalten, wenn er den vollständigen Quantenzustand direkt simulieren möchte.

Eine QPU besitzt dagegen selbst einen Quantenzustand.

Sie speichert diese Amplituden, wie wir gesehen haben, nicht als Milliarden Zahlen.

Der gemeinsame Zustand ihrer Qubits besitzt diese Quanteneigenschaften physisch.

Natur mit Quantenmechanik simulierenViele Vorgänge in der Natur sind selbst quantenmechanisch.

Beispielsweise das Verhalten von:

Atomen
Molekülen
Elektronen
MaterialienEin klassischer Computer muss deren Quantenverhalten mathematisch simulieren.

Das kann mit wachsender Größe sehr aufwendig werden.

Ein Quantencomputer arbeitet dagegen selbst nach quantenmechanischen Regeln.

Die Hoffnung ist deshalb, bestimmte Quantensysteme wesentlich natürlicher auf einer QPU abzubilden.

Anwendungen könnten beispielsweise die Untersuchung von:

• Molekülen
• chemischen Reaktionen
• Materialien
• elektronischen Zuständen umfassen.

Auch hier gilt jedoch:

Nicht jede Simulation wird automatisch schneller.

Es muss ein geeigneter Quantenalgorithmus existieren, und wir müssen am Ende die benötigte Information aus dem Quantenzustand messen können.

Die Messung bleibt eine GrenzeHier stoßen wir wieder auf einen Punkt aus den ersten Episoden.

Ein Quantenzustand kann sehr viele Amplituden besitzen.

Bei 30 Qubits:

mehr als eine MilliardeAber wir können diese Milliarde Amplituden nicht einfach alle auslesen.

Eine Messung liefert nur ein klassisches Ergebnis.

Zum Beispiel:

011010...Der Quantenalgorithmus muss deshalb so konstruiert sein, dass die gesuchte Information in den Messwahrscheinlichkeiten sichtbar wird.

Das ist entscheidend.

Ein Quantencomputer wäre wenig hilfreich, wenn wir zunächst eine riesige Rechnung im Quantenzustand durchführen, die benötigte Information anschließend aber nicht effizient daraus gewinnen können.

Warum große Datenmengen ein Problem sein könnenDasselbe gilt für die Eingabe.

Angenommen, wir besitzen eine klassische Datenbank mit einer Milliarde Datensätzen.

Diese Daten befinden sich zunächst nicht automatisch in der QPU.

Sie liegen beispielsweise:

im RAM
auf einer SSD
auf einem ServerWenn ein Quantenalgorithmus diese Daten benötigt, müssen sie in geeigneter Form für die Quantenberechnung bereitgestellt werden.

Auch das kostet Zeit.

Deshalb reicht die Aussage:

Der Quantenalgorithmus benötigt nur √N Schritte.allein noch nicht aus.

Wir müssen die gesamte Berechnung betrachten:

Daten vorbereiten
↓
Quantenzustand erzeugen
↓
Quantenalgorithmus ausführen
↓
messen
↓
Ergebnis klassisch verarbeitenNur wenn die gesamte Kette einen Vorteil bringt, ist der Quantencomputer tatsächlich schneller.

Und was ist mit Optimierungsproblemen?Quantencomputern wird häufig ein großer Vorteil bei Optimierungsproblemen zugeschrieben.

Ein Optimierungsproblem sucht aus vielen Möglichkeiten eine möglichst gute Lösung.

Zum Beispiel:

Welche Route ist am kürzesten?oder:

Wie verteilen wir Ressourcen möglichst effizient?Solche Probleme können klassisch sehr schwierig sein.

Daraus folgt aber nicht automatisch:

schwierige Optimierung

Quantencomputer ist schnellerFür manche Optimierungsprobleme und bestimmte Problemstrukturen werden Quantenalgorithmen erforscht.

Es gibt aber keinen allgemeinen Quantentrick, der jedes schwierige Optimierungsproblem plötzlich einfach macht.

Auch hier muss für das konkrete Problem ein Algorithmus existieren, der einen tatsächlichen Vorteil bietet.

Dasselbe gilt für künstliche IntelligenzAuch bei Machine Learning und künstlicher Intelligenz taucht häufig die Behauptung auf, Quantencomputer könnten zukünftige KI-Systeme massiv beschleunigen.

Auch das ist keine allgemeine Eigenschaft einer QPU.

Ein heutiges neuronales Netz besteht zu einem großen Teil aus numerischen Berechnungen, die GPUs sehr effizient ausführen können.

Eine QPU ist nicht automatisch eine schnellere GPU.

Für einen Quantenvorteil müsste wiederum ein geeigneter Quantenalgorithmus existieren.

Deshalb gilt auch hier:

großes Rechenproblem
≠
automatisch gutes QuantenproblemWas bleibt klassisch?Sehr viele Aufgaben eines Computers profitieren nicht von einer QPU.

Zum Beispiel:

Text anzeigen
Dateien kopieren
Webseiten darstellen
Netzwerkverbindungen verwalten
Datenbankeinträge speichern
Fenster zeichnen
E-Mails verarbeiten
Betriebssystem ausführenFür solche Aufgaben sind klassische Prozessoren hervorragend geeignet.

Auch einfache mathematische Operationen benötigen keinen Quantencomputer.

Eine CPU kann beispielsweise:

7 + 5direkt berechnen.

Es wäre sinnlos, daraus erst einen Quantenzustand zu erzeugen, Quantengatter auszuführen und anschließend wieder zu messen.

Der Quantencomputer wird deshalb kein Ersatz für den klassischen ComputerEin zukünftiger Quantencomputer ist eher als zusätzliche spezialisierte Recheneinheit zu verstehen.

Ähnlich wie heute eine GPU bestimmte Berechnungen übernimmt:

CPU
+
GPUkönnte ein System für bestimmte Aufgaben verwenden:

CPU
+
GPU
+
QPUDie CPU führt das normale Programm aus.

Die GPU übernimmt geeignete stark parallele Berechnungen.

Die QPU wird nur für jene Teile eingesetzt, für die ein geeigneter Quantenalgorithmus existiert.

Danach verarbeitet die CPU die Messergebnisse weiter.

Drei unterschiedliche Arten von VorteilWir können die Unterschiede nun grob zusammenfassen.

Klassische CPUflexible allgemeine BerechnungenGPUsehr viele ähnliche Berechnungen parallelQPUbestimmte Problemstrukturen
durch Quantenzustände und Interferenz ausnutzenDie QPU besitzt also nicht einfach:

mehr RechenleistungSie bietet für bestimmte Algorithmen eine andere mathematische Möglichkeit zu rechnen.

Wann lohnt sich eine QPU?Für einen echten Vorteil müssen mehrere Bedingungen gleichzeitig erfüllt sein.

Wir benötigen:

ein geeignetes Problem
+
einen geeigneten Quantenalgorithmus
+
ausreichend gute Qubits
+
ausreichend geringe Fehler
+
vertretbaren Aufwand für Eingabe und MessungErst dann kann ein praktischer Geschwindigkeitsvorteil entstehen.

Eine QPU allein genügt nicht.

Was wir jetzt wissen- Ein Quantencomputer ist keine allgemein schnellere CPU.

• Der Vorteil entsteht durch Quantenalgorithmen, nicht allein durch die Hardware.
• Ein Quantenalgorithmus wird von uns so entworfen, dass er eine geeignete mathematische Struktur des Problems gezielt ausnutzt.
• Der Quantencomputer findet diesen Rechenweg nicht selbst.
• Grovers Algorithmus reduziert eine unstrukturierte Suche von ungefähr N auf √N Prüfungen.
• Shors Algorithmus nutzt eine mathematische Periodenstruktur und kann bestimmte zahlentheoretische Probleme wesentlich effizienter lösen als bekannte klassische Verfahren.
• Quantensysteme können für klassische Computer sehr aufwendig zu simulieren sein.
• Eine QPU kann solche Systeme unter bestimmten Voraussetzungen natürlicher darstellen.
• Die vielen Amplituden eines Quantenzustands können nicht einfach vollständig ausgelesen werden.
• Auch das Bereitstellen klassischer Eingangsdaten kann einen möglichen Vorteil begrenzen.
• Schwierige Optimierungsprobleme werden nicht automatisch durch eine QPU einfach.
• Dasselbe gilt für Machine Learning und künstliche Intelligenz.
• Die meisten alltäglichen Aufgaben eines Computers bleiben klassische Aufgaben.
• Zukünftige Systeme werden QPUs deshalb eher als spezialisierte Ergänzung zu CPUs und GPUs verwenden. Damit können wir eine der bekanntesten Behauptungen über Quantencomputer genauer untersuchen.

Shors Algorithmus kann mathematische Probleme beschleunigen, auf denen ein Teil unserer heutigen Kryptografie beruht.

In Episode 11 schauen wir uns deshalb an, was hinter der Aussage steckt:„Quantencomputer können die Verschlüsselung des Internets knacken.“Welche Verfahren wären tatsächlich betroffen — und welche nicht?