Was beschleunigen Quantenalgorithmen?
Ein Quantenalgorithmus nutzt Interferenz, um die richtige Antwort wahrscheinlich zu machen, und er beschleunigt nur bestimmte Probleme. Wenn Sie wissen, was er beschleunigt und was nicht, ordnen Sie Meldungen über Quantencomputer nüchtern ein.
In dieser Lektion rechnen Sie einen Suchschritt selbst und sehen dann, warum ein Simulator keinen Vorteil zeigen kann.
Am Ende dieser Lektion
Notiz
Ich kann sagen, was Quantenalgorithmen beschleunigen und was nicht.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Amplitudenverstärkung | ein Verfahren, das die Amplitude der gesuchten Antwort wachsen lässt |
| Markieren | das Vorzeichen der gesuchten Antwort umkehren |
| Spiegeln | jede Amplitude am Mittelwert spiegeln |
| Rauschen | kleine Störungen, die ein echtes Qubit verfälschen |
| Fehlerkorrektur | Verfahren, die mit vielen Qubits ein fehlerfreies Qubit nachbilden |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine Suche mit vier Elementen
Vier Elemente tragen die Nummern 00, 01, 10 und 11. Das Element 11 ist gesucht. Zu Beginn haben alle dieselbe Amplitude 0,5, also die Chance 0,25.
Dann markieren Sie das gesuchte Element, indem Sie sein Vorzeichen umkehren. Danach spiegeln Sie jede Amplitude am Mittelwert: neue Amplitude gleich zweimal Mittelwert minus alte Amplitude.
Beispiel: ein Verstärkungsschritt bei vier Elementen
| Schritt | 00 | 01 | 10 | 11 | Chance für 11 |
|---|---|---|---|---|---|
| Start | 0,5 | 0,5 | 0,5 | 0,5 | 0,25 |
| Markiert | 0,5 | 0,5 | 0,5 | -0,5 | 0,25 |
| Mittelwert | 0,25 | 0,25 | 0,25 | 0,25 | |
| Gespiegelt | 0 | 0 | 0 | 1 | 1 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Der Verstärkungsschritt im Lab
docker exec jupyter python3 steps/amplify.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Suche braucht etwa die Wurzel der Schritte
Eine ungeordnete Liste mit N Elementen durchsucht ein gewöhnlicher Rechner im Mittel mit etwa N durch 2 Blicken. Die Amplitudenverstärkung kommt mit etwa der Wurzel aus N Schritten aus.
Das ist ein großer Gewinn, aber kein Wunder: Er gilt für die Suche, nicht für jedes Problem.
Beispiel: Blicke gegen Schritte
| Elemente N | Gewöhnlich im Mittel | Verstärkungsschritte, Größenordnung |
|---|---|---|
| 4 | etwa 2 | 1 |
| 100 | etwa 50 | etwa 10 |
| 10 000 | etwa 5 000 | etwa 100 |
| 1 000 000 | etwa 500 000 | etwa 1 000 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele glauben, ein Quantencomputer probiere alle Antworten gleichzeitig aus und sei für alles schneller. Das stimmt nicht. Eine Messung liefert nur eine Antwort. Ein Gewinn entsteht nur bei Problemen, für die jemand die Interferenz geschickt entworfen hat.
Die Wurzel aus zwei großen Zahlen
docker exec jupyter python3 -c "print(10000 ** 0.5, 1000000 ** 0.5)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Faktorisieren: ein bekanntes Beispiel in Worten
Eine große Zahl in ihre Primfaktoren zu zerlegen, ist für gewöhnliche Rechner sehr aufwendig. Ein Quantenalgorithmus, der Shor-Algorithmus, kann das nach heutigem Wissen viel schneller.
Deshalb arbeiten Forschende an Verschlüsselung, die dagegen sicher ist. Die Rechnung ist aber nur im Prinzip bekannt. Eine Maschine, die große Zahlen so zerlegt, gibt es heute nicht.
Echte Qubits sind empfindlich
Ein echtes Qubit wird durch kleine Störungen verfälscht. Das nennt man Rauschen. Je mehr Gatter ein Programm hat, desto mehr Fehler sammeln sich an.
Mit Fehlerkorrektur lässt sich ein gutes Qubit aus vielen schlechten bauen, aber das kostet viele zusätzliche Qubits. Darum sind lange Rechnungen heute selten.
Warum der Simulator keine Beschleunigung zeigt
Der Simulator rechnet jede Amplitude einzeln aus. Für n Qubits sind das 2 hoch n Zahlen zu je 16 Byte. Jedes Qubit mehr verdoppelt Speicher und Zeit.
Er kann die Regeln darum genau zeigen, aber nie, dass ein Quantencomputer schneller ist. Dafür bräuchte man echte Hardware.
Speicher für 30 Qubits in Byte
docker exec jupyter python3 -c "print(2 ** 30 * 16)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Beispiel: Speicher des Simulators
| Qubits | Amplituden | Speicher bei 16 Byte je Amplitude |
|---|---|---|
| 10 | 1 024 | etwa 16 Kilobyte |
| 20 | 1 048 576 | etwa 16 Megabyte |
| 30 | 1 073 741 824 | etwa 17 Gigabyte |
| 40 | etwa 1,1 Billionen | etwa 17,6 Terabyte |
| 50 | etwa 1,1 Billiarden | etwa 18 Petabyte |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.