Quantencomputing### Mehrere Qubits und der Mythos vom parallelen Rechnen
In Episode 2 haben wir den Zustand eines einzelnen Qubits mit zwei Amplituden beschrieben:
Amplitude für das mögliche Messergebnis 0
Amplitude für das mögliche Messergebnis 1Ein Quantengatter verändert diese Amplituden nach einer festen Regel. Bei der Messung bestimmen sie, mit welcher Wahrscheinlichkeit wir 0 beziehungsweise 1 erhalten.
Aber ein Computer arbeitet nicht nur mit einem einzelnen Bit. Deshalb erweitern wir unser Modell nun auf mehrere Bits und Qubits.
Drei Bits speichern eine Binärzahl
Ein einzelnes Bit kann den Wert 0 oder 1 besitzen. Drei Bits können gemeinsam acht verschiedene Bitfolgen darstellen:
000
001
010
011
100
101
110
111Warum entsprechen diese Bitfolgen den Zahlen 0 bis 7?
In unserem gewohnten Dezimalsystem besitzt jede Stelle einen Stellenwert:
Einer, Zehner, Hunderter, Tausender …Bei der Dezimalzahl 352 bedeutet das:
3 × 100
- 5 × 10
- 2 × 1 = 352Das Binärsystem funktioniert genauso. Es verwendet jedoch nur die Ziffern 0 und 1. Die Stellenwerte verdoppeln sich deshalb von rechts nach links:
… 16, 8, 4, 2, 1Bei drei Bits haben die Stellen von links nach rechts die Werte 4, 2 und 1:
Bit110Stellenwert421Beitrag420
Damit gilt:
110 = 4 + 2 + 0 = 6Die acht möglichen Bitfolgen entsprechen diesen Zahlen:
BitfolgeDezimalzahl00000011010201131004101511061117
Drei klassische Bits befinden sich zu einem bestimmten Zeitpunkt in genau einem dieser acht Zustände. Stehen sie auf 110, speichern sie die Zahl 6.
Drei Qubits können ebenfalls die Zahl 6 darstellen
Auch drei Qubits können auf 1, 1 und 0 gesetzt werden. In der Quanteninformatik schreiben wir diesen Zustand so:
|110⟩Das bedeutet zunächst ebenfalls die Binärzahl 6.
Messen wir die drei Qubits sofort, erhalten wir sicher:
110Das Messergebnis entspricht wieder der Dezimalzahl 6.
Bis hierhin besteht kein wesentlicher Unterschied zu drei klassischen Bits:
drei Bits: 110 → auslesen → 6
drei Qubits: 110 → messen → 6Der Unterschied beginnt erst, wenn Quantengatter den gemeinsamen Zustand der Qubits verändern.
Eine Amplitude für jedes mögliche Messergebnis
In Episode 2 haben wir jedem möglichen Messergebnis eine Amplitude zugeordnet.
Bei einem Qubit gibt es zwei mögliche Messergebnisse:
0
1Deshalb wird sein Zustand mit zwei Amplituden beschrieben: einer Amplitude für 0 und einer Amplitude für 1.
Bei zwei Qubits besteht das Messergebnis aus zwei Stellen. Für die erste Stelle gibt es die Möglichkeiten 0 und 1. Dasselbe gilt für die zweite Stelle. Daraus entstehen vier mögliche vollständige Messergebnisse:
00
01
10
11Zu jedem dieser vier Messergebnisse gehört eine Amplitude.
Bei drei Qubits kommt eine dritte Stelle hinzu. An jede der vier bisherigen Bitfolgen kann entweder 0 oder 1 angehängt werden:
00 → 000 oder 001
01 → 010 oder 011
10 → 100 oder 101
11 → 110 oder 111Damit gibt es acht mögliche vollständige Messergebnisse:
000 001 010 011 100 101 110 111Zu jedem dieser acht Messergebnisse gehört wiederum eine Amplitude:
Amplitude für 000
Amplitude für 001
Amplitude für 010
Amplitude für 011
Amplitude für 100
Amplitude für 101
Amplitude für 110
Amplitude für 111Die Amplituden sind weiterhin die Koordinaten des Zustands. Eine Koordinate gehört nun aber nicht zu einem einzelnen Qubit, sondern zu einem möglichen vollständigen Messergebnis aller drei Qubits.
Ein Koordinatensystem mit acht Achsen können wir nicht mehr zeichnen. Mathematisch funktioniert es trotzdem nach demselben Prinzip: Die acht Amplituden beschreiben gemeinsam einen einzigen Zustand.
Zu jedem möglichen vollständigen Messergebnis gehört genau eine Amplitude. Drei Qubits haben acht mögliche Messergebnisse. Ihr gemeinsamer Zustand wird deshalb mit acht Amplituden beschrieben.### Der eindeutige Zustand 110
Sind die drei Qubits auf 110 gesetzt, besitzt nur dieses mögliche Messergebnis eine Amplitude von 1. Alle anderen Amplituden sind 0:
Mögliches MessergebnisAmplitudeWahrscheinlichkeit00000 %00100 %01000 %01100 %10000 %10100 %1101100 %11100 %
Die Messung kann daher nur 110 ergeben.
Auch dieser Zustand lässt sich als Liste seiner Koordinaten schreiben:
(0, 0, 0, 0, 0, 0, 1, 0)Die siebte Position gehört zur Bitfolge 110. Dort steht eine 1; an allen anderen Positionen steht 0.
Quantengatter verändern die acht Amplituden
Nun beginnen wir stattdessen mit drei Qubits im Zustand 000 und wenden auf jedes Qubit ein H-Gatter an:
|000⟩
↓
H auf das erste Qubit
H auf das zweite Qubit
H auf das dritte Qubit
↓
SuperpositionDie drei H-Gatter verändern den gemeinsamen Zustand so, dass anschließend alle acht möglichen Messergebnisse dieselbe Wahrscheinlichkeit besitzen:
Mögliches MessergebnisUngefähre Wahrscheinlichkeit00012,5 %00112,5 %01012,5 %01112,5 %10012,5 %10112,5 %11012,5 %11112,5 %
Alle acht Wahrscheinlichkeiten zusammen ergeben 100 Prozent:
8 × 12,5 % = 100 %Die zugehörigen Amplituden betragen jeweils ungefähr 0,354, denn:
0,354² ≈ 0,125 = 12,5 %Der gemeinsame Zustand besitzt nun also acht gleich große Amplituden.
Was liefert die Messung?
Bei einer einzelnen Messung erhalten wir nicht alle acht Bitfolgen. Wir erhalten genau eine davon:
000 oder 001 oder 010 oder 011
oder 100 oder 101 oder 110 oder 111Beispielsweise könnte die Messung ergeben:
101Das entspricht der Dezimalzahl 5.
Wiederholen wir den vollständigen Ablauf sehr oft, erscheinen alle acht Ergebnisse ungefähr gleich häufig. Eine einzelne Ausführung liefert jedoch immer nur eine Bitfolge und damit nur eine Zahl.
Unser bisheriges Programm wäre daher lediglich eine umständliche Methode, eine zufällige Zahl zwischen 0 und 7 zu erzeugen. Einen Rechenvorteil haben wir damit noch nicht erreicht.
Woher kommt die Behauptung vom parallelen Rechnen?
Bei n klassischen Bits gibt es 2ⁿ mögliche Bitfolgen. Die Bits besitzen zu einem bestimmten Zeitpunkt aber nur eine davon.
Bei n Qubits wird der gemeinsame Zustand mit 2ⁿ Amplituden beschrieben:
AnzahlMögliche Messergebnisse beziehungsweise Amplituden1 Qubit22 Qubits43 Qubits84 Qubits1610 Qubits1.024n Qubits2ⁿ
Quantengatter können diese Amplituden während einer Berechnung verändern. Daraus entsteht die verbreitete Aussage:
*Ein Quantencomputer berechnet alle Möglichkeiten gleichzeitig.*Diese Formulierung ist verführerisch, aber irreführend.
Die 2ⁿ Amplituden sind keine 2ⁿ getrennten Speicherplätze, aus denen wir anschließend alle Ergebnisse auslesen können. Sie sind die Koordinaten eines einzigen gemeinsamen Quantenzustands.
Bei der Messung erhalten wir weiterhin nur eine der möglichen Bitfolgen. Die übrigen Amplituden können wir nicht der Reihe nach auslesen. Bereits die erste Messung beendet die vorherige Superposition.
Viele Amplituden bedeuten nicht viele gleichzeitig auslesbare Ergebnisse.### Wo kann dann ein Vorteil entstehen?
Ein nützliches Quantenprogramm misst die gleichmäßige Superposition nicht sofort. Es wendet weitere Quantengatter an.
Diese Gatter verändern die Amplituden nach den Regeln des Algorithmus:
Eingabewert vorbereiten
↓
Superposition erzeugen
↓
weitere Gatter verändern die Amplituden
↓
Amplituden verstärken sich oder heben sich auf
↓
erst am Ende messenDurch Interferenz kann das Programm die Wahrscheinlichkeitsverteilung vor der Messung verändern. Bestimmte Ergebnisse werden dadurch wahrscheinlicher, andere unwahrscheinlicher oder sogar unmöglich.
Das geschieht nicht, weil der Quantencomputer die richtige Antwort kennt oder weil man ihm ein gewünschtes Ergebnis vorgibt. Die Folge der Gatter muss vorher so entwickelt werden, dass ihre festen Rechenregeln diese Veränderung bewirken.
Genau darin liegt die eigentliche Schwierigkeit eines Quantenalgorithmus:
*Es genügt nicht, viele mögliche Ergebnisse in einer Superposition zu besitzen. Das Programm muss ihre Amplituden so verarbeiten, dass die gesuchte Information bei der Messung sichtbar wird.*Nur für bestimmte Probleme kennt man Algorithmen, bei denen dies einen Vorteil gegenüber klassischen Verfahren verspricht.
Was wir jetzt wissen
- Drei klassische Bits können eine Binärzahl zwischen 0 und 7 speichern.
- Die Bitfolge 110 entspricht der Dezimalzahl 6.
- Drei Qubits können ebenfalls eindeutig auf 110 gesetzt werden.
- Der gemeinsame Zustand von drei Qubits wird mit acht Amplituden beschrieben.
- Jede Amplitude gehört zu einem möglichen Messergebnis von 000 bis 111.
- Quantengatter verändern diese acht Amplituden nach festen Regeln.
- Eine Messung liefert trotzdem nur eine einzige Bitfolge.
- 2ⁿ Amplituden sind keine 2ⁿ getrennt auslesbaren Rechenergebnisse.
- Ein möglicher Quantenvorteil entsteht erst durch einen passenden Algorithmus, der die Amplituden vor der Messung gezielt transformiert. ### Mit einem Missverständnis aufräumen
Missverständnis:* Drei Qubits berechnen acht Ergebnisse gleichzeitig, aus denen anschließend das richtige ausgelesen wird.Tatsächlich besitzt ihr gemeinsamer Zustand acht Amplituden — eine für jedes mögliche Messergebnis. Eine Messung liefert aber nur eine einzige Bitfolge, nicht alle acht Ergebnisse.*In Episode 4 verfolgen wir ein kleines Quantenprogramm Schritt für Schritt. Dann sehen wir konkret, wie Gatter die Amplituden mehrerer möglicher Ergebnisse verändern und welche Information dadurch bei der Messung sichtbar wird.
Top comments (0)