Die Überlegenheit von Quantencomputern – aus der Informatikperspektive
Übersicht
Auf einen Blick
Schlüsselbegriffe: Rechenkomplexität, Big-O-Notation, RSA-Algorithmus
Alter: 16 – 19 Jahre
Erforderliche Kenntnisse/Fähigkeiten: Grundlegendes Verständnis der strukturierten Programmierung, Grundkenntnisse der Programmiersprache Python
Zeitrahmen: 30–45 Minuten
Autor: Cristian Datzko (CH)
In dieser Unterrichtsstunde entdecken die Schüler*innen:
- die Unterschiede zwischen einem klassischen und einem Quantencomputer;
- die Big-O-Notation für Wachstumsraten (linear, polynomial, exponentiell, faktoriell);
- was Quantenüberlegenheit bedeutet.
Material
- Papier und Bleistift
- Computer/Tablets und Internetzugang
1. Rechenkomplexität und die Big-O-Notation
Aufgabe 1
Finde die Primfaktoren der Zahl 373628601156041617, ohne einen Computer zu verwenden. Warum ist das so schwierig? Vergleiche diese Aufgabe mit der Multiplikation zweier Zahlen.
Ein Primfaktor der Zahl 373628601156041617 kann theoretisch jede natürliche Zahl von 2 bis sein.
Um eine Zahl in ihre Primfaktoren zu zerlegen, müssen also mindestens alle Primzahlen von 2 bis daraufhin überprüft werden, ob sie Primfaktoren von 373628601156041617 sind.
Dabei ist eine Zahl, die halb so viele Ziffern hat wie die ursprüngliche Zahl 373628601156041617 (9 anstatt 18).
Ein offensichtlicher Ansatz wäre, digitale Tools wie WolframAlpha zu verwenden, die die Zahl zu 191206237 · 1954060741 faktorisieren. Dies verdeckt jedoch die Tatsache, wie aufwendig es für einen Computer ist, Zahlen wie 373628601156041617 zu faktorisieren. Ein Programm hierfür ist unter „Erklärung“ vorgestellt. Es zeigt klar auf, dass es länger braucht, je größer die zu faktorisierende Zahl ist; präzise formuliert benötigt es exponentiell mehr Zeit.
Die Zahlen 191206237 und 1954060741 sind bewusst gewählt: Der 23. Juni 1912 ist der Geburtstag von Alan Turing und der 7. Juni 1954 ist der Jahrestag seines Todes.
Aufgabe 2
Recherchiere Informationen über den RSA‑Algorithmus, der 1977 von Ronald L. Rivest (*1947), Adi Shamir (*1952) und Leonard Adleman (*1945) erfunden wurde und noch heute in der Kryptografie verwendet wird. Wie werden öffentliche und private Schlüssel erstellt?
Der RSA‑Algorithmus basiert auf einem öffentlichen und einem privaten Schlüssel. Der öffentliche Schlüssel wird veröffentlicht und zum Verschlüsseln verwendet, während der private Schlüssel geheim bleibt und zum Entschlüsseln dient. Die folgenden mathematischen Operatoren werden hierfür verwendet:
- Multiplikation a · b
- Potenzieren bx
- Modulo‑Rechnen a % b (ist gleich dem Rest der ganzzahligen Division von a : b)
Drei Aspekte werden vom RSA‑Algorithmus geregelt:
- Um einen Satz öffentlicher und privater Schlüssel zu erzeugen, führt der Empfänger folgende Schritte aus:
- Der Empfänger wählt zwei große Primzahlen p und q und berechnet das Produkt n = p · q.
- Der Empfänger wählt zwei Zahlen d und e, so dass d · e % (p – 1) · (q – 1) = 1 ergibt. Ergänzend müssen d und e teilerfremd (d. h. die beiden Zahlen haben außer 1 keinen weiteren gemeinsamen Teiler) zu p – 1 und q – 1 sein.
- Der Empfänger veröffentlicht (n, e) als seinen öffentlichen Schlüssel und behält (n, d) als seinen privaten Schlüssel. p und q werden vernichtet.
- Um eine Nachricht zu verschlüsseln, berechnet der Absender aus der Nachricht m den Geheimtext c = me % n.
- Um die Nachricht zu entschlüsseln, berechnet der Empfänger aus dem Geheimtext c den ursprünglichen Klartext m’ = cd % n.
Aufgabe 3
Vergleiche das Wachstum der Funktionen , , , und , indem du die Funktionswerte für , , , , , und berechnest.
Hinweis: Du brauchst eventuell spezielle Hilfswerkzeuge wie Python oder WolframAlpha, um einige dieser Funktionswerte zu berechnen.
Die folgende Tabelle zeigt die berechneten Werte:
| x | f₁(x) = x | f₂(x) = x² | f₃(x) = x¹⁰ | f₄(x) = 2ˣ | f₅(x) = x! |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 2 | 1 |
| 10 | 10 | 100 | 1 · 1010 | 1024 | 3 628 800 |
| 100 | 100 | 10 000 | 1 · 1020 | 1,268 · 1030 | 9,333 · 10157 |
| 1 000 | 1 000 | 1 000 000 | 1 · 1030 | 1,072 · 10301 | 4,024 · 102567 |
| 10 000 | 10 000 | 100 000 000 | 1 · 1040 | 1,995 · 103010 | 2,846 · 1035659 |
| 100 000 | 100 000 | 1 · 1010 | 1 · 1050 | 9,990 · 1030102 | 2,824 · 10456573 |
| 1 000 000 | 1 000 000 | 1 · 1012 | 1 · 1060 | 9,901 · 10301029 | 8,264 · 1055555708 |
Für die größten Werte wurde WolframAlpha verwendet.
Die Tabelle zeigt klar auf, dass f₄(x) = 2ˣ (exponentielles Wachstum) signifikant schneller als die anderen Funktionen (linear, quadratisch oder polynomial) wächst, und dass f₅(x) = x! (faktorielles Wachstum) noch schneller wächst.
Erklärung
Einige dieser Rechnungen dauern länger als erwartet. Ein einfacher Ansatz zur Faktorisierung einer sehr großen ganzen Zahl wäre, alle möglichen Primfaktoren (beginnend mit 2) zu testen, bis ein erster Faktor gefunden wird.
Man muss lediglich bis testen, weil entweder eine Primzahl ist oder als faktorisiert werden kann, wobei entweder oder kleiner ist als .
Dieser Vorgang muss dann fortgesetzt werden, bis alle Faktoren gefunden sind oder bis sich herausstellt, dass die ganze Zahl eine Primzahl ist.
Das folgende Python‑Programm zeigt diesen Prozess in vereinfachter Form (der Einfachheit halber werden alle ganzen Zahlen ab 2 getestet, anstatt nur die Primzahlen):
import mathdef is_divisible_by(dividend, divisor): """ Gibt an, ob der Zähler durch den Nenner teilbar ist, indem überprüft wird, ob der Rest der ganzzahligen Division 0 ist.""" return dividend % divisor == 0 # Der Modulo-Operator „%“ ermittelt den Rest einer ganzzahligen Division.integer = 373628601156041617 # Die Zahl, die faktorisiert werden sollfactors = [] # Eine Liste von Faktoren, beginnend mit einer leeren Listex = integer # Lege eine Kopie von „integer“ an, da sich diese Variable mit der Zeit ändert.factor = 2 # Überprüfe jede ganze Zahl, beginnend mit 2.while factor <= math.sqrt(x): # Solange die überprüfte Zahl (der Faktor) kleiner oder gleich der Wurzel von x ist if is_divisible_by(x, factor): factors.append(factor) # Hänge den überprüften Faktor ans Ende der Liste an. x = x // factor # Jetzt müssen nur noch Zahlen bis x geteilt durch den Faktor überprüft werden, da der Faktor selbst bereits ein Faktor der Faktorisierung ist. „//“ ist eine ganzzahlige Division, daher ist das Ergebnis immer eine ganze Zahl. # Der Faktor muss nicht geändert werden, da er nicht kleiner als vorher sein kann, sondern wieder der gleiche Faktor sein könnte. else: factor = factor + 1 # Erhöhe den Faktor um 1factors.append(x) # Wenn keine Faktoren kleiner oder gleich Wurzel von x gefunden werden, muss die verbleibende ganze Zahl eine Primzahl sein und somit der endgültige Faktor.print("Die Primfaktoren von", integer, "sind", factors)
Beispiel: Um die Zahl 100 zu faktorisieren, würde jede Iteration der Schleife die folgenden Werte ergeben:
| x | Faktor | Alle Faktoren |
|---|---|---|
| 100 | 2 | [] |
| 50 | 2 | [2] |
| 25 | 2 | [2, 2] |
| 25 | 3 | [2, 2] |
| 25 | 4 | [2, 2] |
| 25 | 5 | [2, 2] |
| 5 | 5 | [2, 2, 5] |
| [2, 2, 5, 5] |
Dies nimmt viel Zeit in Anspruch. Die kürzeste Rechenzeit wird erreicht, wenn eine Potenz von 2 ist, da dann in jeder Schleifeniteration durch 2 geteilt wird. Wenn die Anzahl der Binärziffern (Bits) ist, die die ganze Zahl darstellen, führt dies zu einer Rechenzeit von .
Der schlimmste Fall tritt ein, wenn bereits eine Primzahl ist: Dies würde zu einer Rechenzeit von führen. Mit anderen Worten: Die Rechenzeit ist exponentiell in Bezug zur Größe einer Zahl.
Zur Veranschaulichung dieser abstrakten Notation: Wenn eine einzelne Iteration der Schleife 1 Mikrosekunde dauert, würde die Rechenzeit für die Faktorisierung von 373628601156041617 – 59 Binärziffern sind erforderlich, um diese Zahl darzustellen – zwischen 59 Mikrosekunden und etwa 13 Minuten liegen:
Wie bestimmt man z. B. die Anzahl der Binärziffern (Bits) von 25?
25 = 2 × 2 × 2 × 2 + 2 × 2 × 2 + 1 = + + 1.
In der Basis 2 entspricht das 11001 (d. h. 5 Ziffern). Die Anzahl der Binärziffern, die zur Darstellung der Zahl 25 benötigt werden, beträgt also 5.
Die Big-O-Notation
Die Big‑O‑Notation wird in der Informatik verwendet, um die ungefähre Rechenzeit zu bestimmen, die ein Algorithmus zur Durchführung einer bestimmten Berechnung braucht, z. B. die Berechnung des Wertes der Funktion in Abhängigkeit von der Eingabegröße . Alle konstanten Faktoren werden vernachlässigt, ebenso wie konstante und/oder langsamer wachsende Terme der Funktion. Es wird nur der am schnellsten wachsende Term berücksichtigt. Dies ergibt ein grobes „allgemeines Bild“ des Verhaltens einer Funktion.
Zum Beispiel wächst die Parabel für langsamer als die Gerade .
Für „überholt“ die Parabel die Gerade. Dies gilt sogar, wenn ein beliebig kleiner, aber positiver Faktor vor gesetzt wird oder wenn eine beliebige Zahl hinzugefügt wird, sodass .
Es gibt immer ein , ab dem die Parabel die Gerade „überholt“. Daher ist für große Werte von nur der dominante Teil der Funktion relevant, in diesem Fall geschrieben als .
Geraden wachsen „linear“ – in der Big‑O‑Notation als bezeichnet –, während Parabeln „quadratisch“ anwachsen – .
Polynome haben eine „polynomiale“ Wachstumsrate. Für ein Polynom ergibt sich die Wachstumsrate . Dabei wird nur beibehalten, während und alle langsamer wachsenden Terme vernachlässigt werden.
Eine noch größere Wachstumsrate ist die „exponentielle“ Wachstumsrate .
Die Fakultät einer natürlichen Zahl ist das Produkt der ersten natürlichen Zahlen, also
.
Überblick über gängige Wachstumsklassen
| Name | Linear | Quadratisch | Polynomial | Exponentiell | Faktoriell |
| Wachstumsklasse | O(x) | O(x2) | O(xn) | O(2x) | O(x!) |
2. Der RSA‑Algorithmus
Der RSA‑Algorithmus für die Public‑Key‑Kryptografie verwendet sehr große Zahlen (in der Regel etwa 4096 Bits; dies entspricht etwa 1234 Dezimalziffern), die das Produkt zweier großer Primfaktoren sind. Die Rechenzeit für die Faktorisierung einer so großen Zahl liegt daher ungefähr bei der oberen Rechenzeitgrenze, d. h. (wobei die Anzahl der Bits ist). Verfeinerte Algorithmen können die Leistung des Algorithmus verbessern, aber die Rechenzeit bleibt in diesem Bereich und liegt in der Regel bei etwa , wobei eine kleine Zahl ist, die dennoch größer als 1 ist.
Um derart große Zahlen zu faktorisieren, wie sie für den RSA‑Algorithmus verwendet werden, würde ein klassischer Computer Hunderttausende von Jahren benötigen. Aus diesem Grund ist der RSA‑Algorithmus, der nach wie vor weit verbreitet ist, so sicher. Bis heute ist kein klassischer Algorithmus bekannt, der eine Zahl schneller faktorisieren kann als der RSA‑Algorithmus. Ein vom Mathematiker Peter Shor entwickelter Quantenalgorithmus, der „Shor‑Algorithmus“ (siehe Das Unknackbare knacken: Der Shor-Algorithmus), benötigt jedoch nur eine polynomiale Laufzeit . Dies stellt eine erhebliche Beschleunigung dar und würde die RSA‑Verschlüsselung angreifbar machen. Glücklicherweise würde ein Quantencomputer mit etwa 20 Millionen[2] sogenannten „noisy“ (also nicht idealen) Qubits etwa acht Stunden brauchen, um einen RSA‑Schlüssel mit 2048 Bits zu knacken. Dies übersteigt noch immer die Fähigkeiten heutiger Quantencomputer.
Das Knacken eines RSA‑Schlüssels ist ein gutes Beispiel, um Quantenüberlegenheit zu demonstrieren: In der „klassischen“ Informatik sind bisher nur Algorithmen bekannt, die RSA‑Schlüssel mit einer Rechenzeit knacken können, die schneller als polynomial mit der Größe der Eingabezahl anwächst. Mit Quantencomputern könnte diese Rechenzeit dagegen erheblich verkürzt werden.
3. Aufgaben
Aufgabe 1
Ein klassisches Problem, dessen Lösung eine sehr lange Rechenzeit erfordert, ist das „Problem des Handelsreisenden“ (englisch: Travelling Salesman Problem). Stell dir vor, ein Handelsvertreter muss mit seinem Lastwagen in die 20 größten Städte deines Landes fahren, um Waren auszuliefern. Er kann dies in einer beliebigen Reihenfolge tun, aber je weniger Zeit er für die Rundreise braucht, umso besser für ihn, da er ein festes Gehalt erhält und nach der Auslieferung der Waren nach Hause fahren kann.
Ermittle die ungefähre Zeit für die Berechnung der besten Route in Big‑O‑Notation.
Hinweis: Beginne mit einer Stadt und füge dann nach und nach weitere Städte hinzu, um einen Ausdruck für alle möglichen Routen zu finden. Sei nicht überrascht, wenn er 77 094 Jahre braucht, um die beste Route zu finden, wenn die Berechnung für eine einzelne Route 1 µs dauert.
Für eine Stadt ist das Problem trivial: Es braucht genau einen Besuch. Für eine zweite Stadt gibt es doppelt so viele Möglichkeiten, denn es könnte jeweils die erste oder die zweite Stadt zuerst besucht werden. Für eine dritte Stadt gibt es bereits dreimal so viele Möglichkeiten wie für zwei Städte, denn die neue Stadt könnte vor, zwischen oder nach den bereits geplanten Besuchen besucht werden, so dass es 2 · 3 = 6 Reihenfolgen gibt, in der die Städte besucht werden können.
Ganz allgemein gilt: Wenn bereits n Städte besucht wurden, gibt es für eine weitere Stadt n + 1 Mal so viele Möglichkeiten wie bei n Städten. Diese Art von Wachstum ist ein faktorielles Wachstum, so dass für n Städte insgesamt n! mögliche Routen existieren.
Für 20 Städte gibt es also 20! ≈ 2,433 · 1018 mögliche Routen. Wenn das Berechnen einer Route 1 µs dauert, bräuchte man für das Berechnen der möglichen Routen bei 20 Städten:
(2,433 · 1018) / (1 000 000 · 60 · 60 · 24 · 365,25) ≈ 77 094 Jahre.
Aufgabe 2
Du machst mit deiner Klasse eine Wanderung und sollst einen Rucksack mit Proviant mitbringen. Du willst so viel Proviant wie möglich mitnehmen, aber das Fassungsvermögen deines Rucksacks beträgt maximal 13,5 kg.
Die Lebensmittel (die nicht geteilt werden dürfen) haben folgende Massen: 0,025 kg, 0,9 kg, 1,6 kg, 1,7 kg, 2,25 kg, 2,85 kg, 3,15 kg, 3,45 kg, 4,9 kg und 6,05 kg.
Wie viel Proviant kannst du maximal mitnehmen?
Um das Optimum zu finden, müssen alle möglichen Packkombinationen einzelner Wegzehrungsgegenstände ausprobiert werden. Es gibt zwar einige Optimierungsmöglichkeiten, zum Beispiel anzuhalten, wenn eine Lösung gefunden ist, die die Kapazität des Rucksacks vollständig ausnutzt.
Weil es 10 Gegenstände mit verschiedenen Massen gibt, gibt es insgesamt 210 mögliche Kombinationen dieser Gegenstände (für jeden Gegenstand, ob er eingepackt wird oder nicht). Deshalb ist die Laufzeit in O(2x).
Um die optimale Lösung zu finden, überprüft das folgende Programm jede mögliche Kombination, indem es einfach über die Zahlen 0 bis 210 − 1 iteriert, die den verschiedenen Packkombinationen entsprechen. Für jedes Bit, das 1 ist, wird der entsprechende Gegenstand „eingepackt“. Wenn die Masse innerhalb der Kapazität des Rucksacks, aber größer ist als die Masse der bisher größten Packkombination, wird dies als (bisher) beste Packkombination gespeichert. Am Ende wird das globale Optimum (oder eines von denen, wenn mehrere gleichwertige existieren) ausgegeben.
def bit(number, position): """Gibt True zurueck, wenn number ein Bit 1 an der Position position hat, sonst False""" temp = number for i in range(position): # Teilen, bis das letzte Bit das ist, an dem wir interessiert sind temp = temp // 2 if temp % 2 == 0: # Ist durch 2 teilbar return False else: return Truedef weight(knapsack): """Berechnet die Masse des Rucksackinhalts durch Aufsummieren der individuellen Massen""" weight = 0 for i in range(len(knapsack)): weight = weight + knapsack[i] return weightitems = [0.025, 0.9, 1.6, 1.7, 2.25, 2.85, 3.15, 3.45, 4.9, 6.05]maximum_weight = 13.5optimum = []for bitcombination in range(2 ** len(items)): # Alle moeglichen Kombinationen zum "Einpacken" der jeweiligen Gegenstaende/Massen in Form einer Zahl, deren Bits den Massen entsprechen knapsack = [] for bitposition in range(len(items)): if bit(bitcombination, bitposition): # Wenn das Bit fuer den Gegenstand 1 ist, muss der Gegenstand "eingepackt" werden knapsack.append(items[bitposition]) if weight(knapsack) <= maximum_weight: # Wenn dies in den Rucksack passt if weight(optimum) < weight(knapsack): # Ein Rucksack mit einem besseren Packgewicht wurde gefunden optimum = knapsackprint("Ein optimal gefuellter Rucksack wiegt", weight(optimum), "und beinhaltet die Gegenstaende mit folgenden Massen:", optimum)
Aufgabe 3
(alternativ zu Aufgabe 2)
Das Damen‑Problem ist ein berühmtes Schachproblem: Auf einem 8×8‑Schachbrett werden acht Königinnen (die sich vertikal, horizontal und diagonal bewegen können) so platziert, dass sie sich nicht innerhalb eines Zuges von einer zur anderen bewegen können. Finde eine Lösung für dieses Problem.
Wenn du herausgefunden hast, wie sich das Problem theoretisch lösen lässt, schreibe ein Computerprogramm, das alle möglichen Lösungen ausgibt.
Erstelle anschließend ein Computerprogramm, das alle möglichen Lösungen für ein n×n‑großes Schachbrett ausgibt, und analysiere die Rechenzeit in Abhängigkeit von der Größe des Schachbretts.
Das Damenproblem, auch bekannt als Acht-Damen-Problem, ist ein bekanntes Beispielproblem für verschiedene Programmiertechniken in der Informatik. Es wurde erstmals 1848 vom Schachkomponisten Max Bezzel veröffentlicht, und seitdem haben sich viele Mathematiker mit diesem Problem sowie mit seiner verallgemeinerten Form, dem n-Damen-Problem, beschäftigt.
Unter Wikipedia: Damenproblem[3] ist das Problem erläutert. Dort findet sich auch eine Python-Lösung für das Problem.
WolframAlpha
https://www.wolframalpha.com/
(letzter Zugriff 13.03.2026)Craig Gidney: How to factor 2048 bit RSA integers with less than a million noisy qubits (2025).
(letzter Zugriff 13.03.2026)Wikipedia: Damenproblem
https://de.wikipedia.org/wiki/Damenproblem
(letzter Zugriff 13.03.2026)
Diese Seite teilen