Quantencomputer können komplexe Probleme lösen, die herömmliche Computer an Grenzen stoßen lässt. Die Technologie birgt viele Potenziale für die Industrie und bedeutet nicht nur einen Vorstoß in der Wissenschaft, sondern auch eine große Chance für innovative Geschäftsmodelle und vielversprechende Anwendungszenarien.
»Der Quantencomputer rechnet parallel und ist um ein Vielfaches schneller. Mit ihm lassen sich zum Beispiel Natursimulationen erstellen oder komplizierte Logistikketten optimieren oder Milliarden von Zahlungsströmen in Echtzeit steuern, während komplexe regulatorische Vorgaben berücksichtigt werden.« Dieses Zitat aus einem Artikel von Focus Online haben wir bereits im ersten Blogbeitrag dieser Serie kennengelernt, und zwar als Beschreibung des sogenannten Quantenparallelismus. Wir haben auch behauptet, dass dieser Effekt einer der Grundpfeiler für die Mächtigkeit des Quantencomputers ist. Wir haben aber nicht erklärt, was der Quantenparallelismus eigentlich genau ist, noch haben wir die Behauptung über die Mächtigkeit erklärt. Jetzt, wo wir die Grundlagen des Quantencomputing aus dem ersten Blogartikel kennen, werden wir dies schleunigst nachholen.
In diesem zweiten Artikel wollen wir also den Quantenparallelismus erklären – und zwar nicht mathematisch rigoros, sondern wir wollen uns ihn an dem einfachen, aber instruktiven Beispiel eines Sudokus verständlich machen. Mit dem gewonnen Verständnis werden wir uns anschließend die großen Potenziale des Quantencomputers und des Quantenparallelismus verdeutlichen.
Eine kurze Wiederholung
Im ersten Blogartikel dieser Serie haben wir das Qubit als grundlegende Informationseinheit des Quantencomputers kennengelernt. Wir haben gesehen, dass es sich im Unterschied zu einem klassischen Bit in einer Überlagerung der Basiszustände |0⟩ und |1⟩ befinden kann, in welchem es sozusagen gleichzeitig in beiden dieser Zustände ist. Dies konnten wir mathematisch präzise mit dem Prinzip der Superposition erfassen. In diesem zweiten Blogartikel werden wir unsere Qubits in einen ganz bestimmen Superpositionszustand versetzen, in welcher die Zustände |0⟩ und |1⟩ gleichmäßig vertreten sind. Diesen Zustand haben wir im ersten Blogartikel als ∣+⟩ = 1/√2∣0⟩ + 1/√2∣1⟩ kennengelernt.
Wir werden also genau diesen Zustand verwenden, um alle möglichen Kombinationen eines Sudoku-Boards in einem einzigen Quantenzustand darzustellen. Als Konsequenz können wir in einer einzigen Rechnung jede Kombination auf ihre Zulässigkeit prüfen und müssen nicht, wie auf dem klassischen Computer, jede nacheinander bearbeiten. Aber fangen wir von vorne an, d.h. schauen wir uns erstmal das Problem an und wie der klassische Computer damit umgeht.
Wie löst ein klassischer Computer ein Sudoku?
Wir betrachten ein 2 x 2 Sudoku mit vier Einträgen 𝑞0, 𝑞1, 𝑞2 und 𝑞3, welche alle nur Werte 0 oder 1 annehmen dürfen:
Daraus ergeben sich 24 = 16 mögliche Kombinationen, die wir hier kurz auflisten:
Gemäß den Sudoku-Regeln ist eine Kombination nur gültig, falls in jeder Zeile und in jeder Spalte verschiedene Zahlen stehen. Möchten wir diese Gültigkeit für alle möglichen Kombinationen auf dem klassischen Computer prüfen, bleibt uns nichts anderes übrig als nacheinander jede der Kombinationen zu überprüfen, also 16 Rechnungen auszuführen:
Und wie löst es ein Quantencomputer?
Nun schauen wir die gleiche Aufgabe auf dem Quantencomputer an. Jede mögliche Kombination können wir hier mit vier Qubits |𝑞0⟩, |𝑞1⟩, |𝑞2⟩ und |𝑞3⟩ in einem gemeinsamen Zustand |𝑞⟩ darstellen:
Soweit ist dies nicht anders als auf dem klassischen Computer. Auch dort reichen vier Bits aus, um jede mögliche Kombination darstellen zu können. Auf dem Quantencomputer steht uns jetzt allerdings die oben erwähnte gleichmäßige Superposition |+⟩ aus |0⟩ und |1⟩ zur Verfügung. Beispielweise können wir das erste Qubit |𝑞0⟩ in diese versetzen, wodurch wir zwei Sudoku-Boards gleichzeitig darstellen können:
Die gleichmäßige Superposition |+⟩ bietet sich hier an, da dabei |0⟩ und |1⟩ gleich vertreten sind und wir a priori keinen Grund haben, eine dieser Zustände zu bevorzugen.
Selbstverständlich können wir auch alle vier Qubits in Zustand |+⟩ versetzen, wodurch der resultierende Zustand |𝑞⟩ alle möglichen Kombinationen des Sudokus gleichzeitig darstellt:
Tatsächlich können wir durch die Superposition nicht nur alle Sudoku-Kombinationen gleichzeitig darstellen — wir können auch auf allen Zuständen gleichzeitig rechnen. Beispielsweise können wir simultan alle Sudoku-Kombinationen mit nur einer einzigen Rechnung überprüfen:
Damit haben wir den klassischen Computer deutlich geschlagen.
Ausblick
Jetzt müssen wir noch bedenken, dass wir hier nur ein Minimalbeispiel betrachtet haben. Wir hatten vier Qubits und konnten 24 = 16 Rechnungen parallel ausführen. Wenn wir nun die Anzahl der Qubits vergrößern, wächst diese Anzahl nicht linear, sondern exponentiell. Genauer: Mit jedem weiteren Qubit bekommen wir eine Verdopplung an darstellbaren Zuständen, welche wir mit dem Quantenparallelismus gleichzeitig verarbeiten können. Beispielsweise bei fünf Qubis 25 = 32, bei sechs Qubits 26 = 64 usw. Das klingt erstmal nicht nach viel, deswegen hier zur Veranschaulichung des exponentiellen Wachstums: mit 50 Qubits können 250 (mehr als 1.000.000.000.000.000 (eine Billiarde)) Zustände dargestellt werden und mit 300 Qubits mehr als es Atome im Universum gibt!
Wir sehen, der Quantencomputer hat ein immenses Potenzial. Allerdings wollen wir nicht verschweigen, dass es nicht einfach ist, dieses zu heben. Ein Grund ist, dass wir diese unglaublich große Zahl an Zuständen nur in der Quantenwelt in Form der Superposition haben. Auch das Ergebnis unserer durch den Quantenparallelismus beschleunigten Rechnung ist wieder eine Superposition. Wenn wir nun nach der Rechnung das Ergebnis auslesen wollen, müssen wir den Zustand der Qubits messen. Im ersten Blogartikel haben wir gesehen, dass eine solche Messung nicht die gesamte Superposition liefern kann, sondern immer lediglich einen der Zustände, aus denen sich die Superposition zusammensetzt, als Ergebnis liefert. Wir haben auch gesehen, dass der Ausgang der Messung zufällig ist, wir aber angeben können mit welcher Wahrscheinlichkeit welcher Zustand als Ergebnis der Messung auftritt. Beim Quantencomputer muss also nach der eigentlichen Rechnung noch eine weitere Verarbeitung erfolgen, welche sicherstellt, dass in der anschließenden Messung erwünschte Ergebnisse auftreten. Wie eine solche sogenannte Amplitudenverstärkung funktioniert, welche Quantenalgorithmen aus dem beschriebenen Quantenparallelismus entwickelt werden können und auch welche anderen Algorithmen und potenzielle Anwendungen für Quantencomputer es gibt, kann bald in unserer Studie »Quantencomputing: Der Weg in die industrielle Praxis« gelesen werden.
Leselinks:
- Schulungsprogramm »Quantencomputing«
- Focus Online: Tiefgekühlter IBM-Superrechner
- Studie »Quantencomputing: Der Weg in die industrielle Praxis« – bald auf unserer Webseite zu finden
Kategorien: Quantencomputing
Tags: Quantencomputer, Quantencomputing (QC), Quantenparallelismus