Quantencomputer und wie sie funktionieren

Um zu verstehen, wie Quantenkryptoanalyse funktioniert, muss man zuerst verstehen, wie Quantencomputer funktionieren.

Aber rufen wir uns vorher noch einmal ins Gedächtnis, wie heutige Computer funktionieren, damit wir später beide besser miteinander vergleichen können.

Wie ein gewöhnlicher Computer funktioniert

Wie ein gewöhnlicher Computer, zum Beispiel ein PC, funktioniert, dürfte jeder wissen: Er arbeitet mit Nullen und Einsen, den sogenanntes Bits. Jedes Bit speichert dabei einen Zustand, der 0 oder 1 sein kann. Der hinter einem Bit stehende, physische Transistor ist eingeschaltet (0) oder ausgeschaltet (1).

Viele Transistoren zusammen bilden den Speicher des Computers, hier können Daten abgelegt werden. Man fasst acht Bits zu einem Byte und 1024 (2 ¹⁰) Bytes zu einem Kilobyte zusammen. 1024 KiB sind dann ein Megabyte und so weiter. Die Daten können beliebig zwischen Speicherbereichen verschoben und kopiert werden. Das Kopieren ist bei Quantencomputern zum Beispiel aufgrund des No-Cloning-Theorems nicht möglich, was einen der wesentlichen Unterschiede zwischen gewöhnlichen und Quantencomputern ausmacht, doch dazu später mehr.

Daten alleine sind noch nicht sehr nützlich. Mal will sie miteinander verknüpfen, mit ihnen rechnen. Das geschieht auf logischer Ebene mit Befehlen, die angeben, wie die Daten zu manipulieren sind. Eine Vielzahl dieser Befehle nennt man Programm. Ein Programm beschreibt also, was mit den Daten angestellt wird. Zum Beispiel könnte eine Programmsequenz folgendes beschreiben: Wenn das Passwort richtig ist, geht es weiter; ansonsten wird abgebrochen.

Ein Programm wird dazu das Passwort eingeben lassen und in einen Speicherbereich E kopieren. Dann wird es das Passwort Bit für Bit mit dem woanders im Speicher (Bereich P) bereits hinterlegten Passwort vergleichen, und zwar Bit für Bit. Dies tut das Programm in einer Schleife. Sobald ein Bit aus E mit einem Bit aus P nicht übereinstimmt, bricht die Schleife ab und es wird an eine andere Stelle im Programm gesprungen, die eine Fehlermeldung anzeigt. Wird die Schleife allerdings komplett ohne Fehler durchlaufen, wird an die Stelle im Programm gesprungen, in der es weitergeht.

Bei klassischen Computern werden also immer Nullen mit Einsen verglichen. Das kann ein Computer sehr schnell, milliardenfach in der Sekunde. Auch wenn es wie eine Mammut-Aufgabe anmutet, alle Bits zweier Speicherbereiche zu vergleichen, erledigt der Computer das insgesamt gesehen in Sekundenbruchteilen.

Außerdem kann der Computer Nullen und Einsen mit einer logischen Operation verknüpfen. Das ist wichtig, um Bedingungen, Schleifen usw. realisieren zu können und zum Beispiel zu erlauben, zwei Passwörter (eingegeben und hinterlegt) zu vergleichen und je nach Ergebnis zu verzweigen.

Bei herkömmlichen Computer geht es dabei immer nur um die zwei Zustände Eins und Null, Strom an oder Strom aus. Sobald im Speicher als auch bei den Verknüpfungen von Bits. Diese Verknüpfung von Bits werden hardwareseitig durch sogenannte Gatter abgebildet und bilden die logischen Operation NICHT, ODER, UND, sowie ENTWEDER ODER ab. Das reicht aus, um in einer Programmiersprache alle Befehle abzubilden, die nötig sind.

Die Gatter auf Hardware-Ebene gibt es schon seit Mitte der 1960er Jahre als integrierte Schaltungen (ICs) mit der Bezeichnung 74xx (TTL-Chips). Jeder der 74xx-Chips bildet eine logische Operation ab: der 7404 das NICHT, der 7408 das UND, der 7432 das ODER und der 7486 das ENTWEDER ODER. Siehe hierzu auch mein Artikel Digitale Logik und Logikgatter einfach erklärt.

Erwähnenswert sei an dieser Stelle noch das NICHT-UND-Gatter, auf englisch NOT AND, oder kurz NAND, welches 4-fach im 7400 verbaut ist. Das besondere an diesem Gatter ist, dass man durch Einanderreihung mehrerer Gatter dieses Typs jede andere logische Operation abbilden kann. Das hat man perfektioniert und immer kleiner gemacht und heute stecken Milliarden dieser Gatter superklein in einer CPU, die dadurch sehr leistungsfähig geworden ist.

Zusammenfassend kann man sagen: Der klassische Computer arbeitet nur mit Nullen und Einsen und das sehr präzise. Es kommt bei den Berechnungen immer das gleiche Ergebnis heraus und er ist bei der Berechnung sehr zuverlässig. Man muss ihn schon sehr stören (etwa Überhitzung über 100 °C durch Übertaktung oder harte, ionisierende Strahlung), damit er ein falsches Ergebnis ausspuckt.

Wie ein Quanten-Computer funktioniert

Bei einem Quanten-Computer ist das anders: Diese arbeitet mit sogenannten Qubits, Quantenbits, deren Wert nicht nur Null oder Eins sein können, sondern jeder beliebige Wert dazwischen. Ein Quantencomputer rechnet nicht mit exakten Nullen und Einsen, sondern mit Wahrscheinlichkeiten zwischen 0 und 1, was man Superposition nennt. Dies aber nur, solange es ungestört, also im Status der Kohärenz ist. Wenn man das Qubit stört, etwa durch eine Messung, "entscheidet" es sich - je nach innewohnender Wahrscheinlichkeit des Zustands - für einen festen Zustand bzw. Wert von Null oder Eins und wechselt in den Zustand der Dekohärenz.

Festlegen des Qubit-Wertes durch Messung (vereinfachte Darstellung mit Bloch-Kugeln)
0 1 Vor der Messung befindet sich das Qubit in Superposition. Sein Zustand ist unbekannt, sozusagen 0 und 1 gleichzeitig.
0 1 Tendiert das Qubit zum Zeitpunkt der Messung mit 75% Wahrscheinlichkeit zu 0 ...	0 1 ... legt es sich zu 75% auf den absoluten Wert 0 fest. Aber es kann zu 25% auch 1 werden.
0 1 Tendiert das Qubit zum Zeitpunkt der Messung mit 90% Wahrscheinlichkeit Richtung 1 ...	0 1 ... legt es sich zu 90% auf den absoluten Wert 1 fest. Aber es kann zu 10% auch 0 werden.
© 2025 Oliver Kuhlemann, Kryptografie.de

Dieses Kippen der Wahrscheinlichkeit zum Absolutwert (0 oder 1) kann also auch schon mal "daneben gehen" und ein "falsches" Ergebnis anzeigen. Darum muss man die Berechnung viele Male, vielleicht 1000x wiederholen und die Ergebnisse durchforsten, welches mit hinreichender Wahrscheinlichkeit das richtige ist, weil es mit Abstand am häufigsten vorkommt. Außerdem benötigt man eine Fehlerkorrektur, die man mit weiteren Qubits realisieren kann.


Ein Qubit "fühlt" sich leider sehr schnell gestört. Man muss ein Qubit darum daran hindern, mit seiner atomaren Umgebung zu interagieren - das würde augenblicklich die Kohärenz zerstören. Man isoliert ein Qubit zum Beispiel, indem man auf fast Null Kelvin (das sind unter -270 °C) abkühlt. Dazu braucht man spezielles, flüssiges Helium. Das ist nicht billig und die Kühlung ist aufwändig. Oder indem man das Qubit etwa mit mehreren Laserstrahlen gefangen hält. Das ist dann eine Ionenfalle - die relativ viel Platz benötigt und auch sehr aufwändig ist.

Das allein ist schon sehr aufwändig und teuer. Doch mit einem einzelnen Qubit ist noch nichts gewonnen. Damit lässt sich nicht rechnen. Man muss die Qubits auch noch miteinander verknüpfen, ihre Quantenzustände verschränken, damit ein Quantencomputer nützlich sein kann. Was das Gesamtkonstrukt noch anfälliger macht.

Mit mehr Qubits kann man paralleler rechnen. Ein klassischer Computer rechnet sequentiell: immer schön alles eins nach dem anderen. Ein Quantencomputer kann parallel rechnen. Das ist seine große Stärke gegenüber dem klassischen Computer.

Je nach Anzahl der Qubits kann er 2 ⁿ Zustände gleichzeitig einnehmen. Stark vereinfacht gesagt könnte ein Quantencomputer mit 8 Qubits demnach 2⁸ = 256 Werte gleichzeitig haben, die gleichzeitig berechnet würden, ein Quantencomputer mit 100 Qubits schon 2¹⁰⁰ = 1.2 Quintillionen Werte, mit denen gleichzeitig gerechnet werden könnte. Statt einer Rechenaufgabe nach der anderen würden mehr als 1 Quintillion Aufgaben gleichzeitig erledigt. Die Leistungsfähigkeit eines Quantencomputers steigt exponentiell mit der Anzahl seine Qubits - wobei man hier vorsichtig sein muss: sagen wir lieber "Arbeits-Qubits". Dazu gleich mehr. Doch zuerst zu dem immensen Vorteil eines Quantencomputers.

Der große Vorteil eines Quantencomputers gegenüber eines Normalen

Um den immensen Vorteil der Rechenweise eines Quantencomputers gegenüber eines klassischen Computers zu verdeutlichen, ein kleines Beispiel: In einem dicken Telefonbuch einer Großstadt stehen 100'000 Telefonnummern. Diese liegen alphabetisch sortiert als Textdatei vor. Das ist so, weil man normalerweise zu einem Namen eine Nummer sucht. Ich möchte jetzt aber eine Rückwärtssuche durchführen: zu einer Telefon-Nummer, die ich habe, den Anschlussinhaber herausfinden. Das Problem ist: ich kann schnell nach einem Namen (wegen der alphabetischen Sortierung) suchen, nicht aber nach einer Nummer.

Mit einem klassischen Computer bleibt mir nichts anderes übrig, als ganz vorne anzufangen und hinter jedem der Namen einzeln zu schauen, ob dort die Nummer steht, die ich suche. Im statistischen Mittel muss ich 50%, also 50'000 Einträge durchsuchen, bis ich die richtige Nummer gefunden habe.

Mit einem Quantencomputer, der in seinen Qubits alle Namen und Nummern gespeichert hat, brauche ich nur ein einziges Mal nach der Nummer zu fragen und erhalte als Antwort den zugehörigen Namen zurück. Es werden quasi alle Nummern gleichzeitig angeschaut und der Name ergibt sich auf fast magische Weise von selbst. Vielleicht deswegen auch der etwas mystisch anmutende Name "Quanten-Orakel" für solche quantentechnisch abgebildeten Funktionen.

Der Vorteil kommt allerdings mit einem Nachteil: Der Quantencomputer ist eine Blackbox, die man während der Arbeit nicht stören darf, da sonst Kohärenz und Ergebnis zerstört werden. Das hat unter anderem auch zur Folge, dass man nur ein Ergebnis am Ende herausbekommen kann, zum Beispiel die eine Telefonnummer. Quantencomputer sind nicht dazu geeignet, mehrere Ergebnisse gleichzeitig zu liefern. Das Sortieren einer Liste wäre mit Quantencomputern ein hoffnungsloses Unterfangen.

Außer macht das Rechnen mit Wahrscheinlichkeiten bzw. mit Superpositionen auch das Ergebnis nur wahrscheinlich, es ist also nicht immer richtig. Mit dem Grover-Algorithmus bekommt man es aber hin, den richtigen Eintrag, nämlich den mit der höchsten Wahrscheinlichkeit, herauszufinden. Dazu muss man das Orakel aber mehrfach hintereinander "rechnen" lassen. Es sind so viele Rechenrunden notwendig, wie das Quadrat der Dateneinträge iat.

Darum ist die Behauptung von oben, das Orakel nur einmal fragen zu müssen, ein wenig euphemistisch bzw. vereinfachend. Aber: Für ein Telefonbuch mit einer Millionen Einträge sind immerhin nur eintausend Runden nötig. Ein enorme Geschwindigkeitsvorteil. Und auch das ist wieder vereinfacht, denn man kann nicht einen Telefonbuch-Eintrag nur mit einem Qubit abbilden, sondern braucht mehrere. Aber es zeigt prinzipiell den enormen Geschwindigkeitsvorteil von Quantencomputern.

In der Theorie toll, in der Praxis eher schwierig

Wegen der "Ungenauigkeit", die sich aus dem Verknüpfen von Wahrscheinlichkeiten ergibt, und weil vielleicht doch mal ein Qubit seinen Zustand ungewollt verändert (z. B. durch sogenannte Bitflip- und Phasenflip-Fehler), benötigt man für die "Arbeits-Qubits" weitere "Überwachungs-Qubits" bzw. Fehlerkorrektur-Qubits bzw. Quantengatter, um die Abweichungen durch Wahrscheinlichkeiten in Grenzen zu halten, damit am Ende überhaupt ein sinnvolles Ergebnis herauskommen kann. Und diese Überwachungs- bzw. Fehlerkorrektur-Qubits benötigen ggf. weitere Überwachungs-Qubits, um sicher zu gehen, dass auch diese ihre Arbeit richtig erledigen. Was bedeutet, dass es sehr sehr aufwändig wird, Quantencomputer mit vielen Qubits zu bauen - oder dass das Ergebnis nur mit einer gewissen Wahrscheinlichkeit stimmt. Oder gar kein Ergebnis vorliegt, weil die Kohärenz zerstört wurde. Es wird wohl technisch nur bis zu einer bestimmten Anzahl von nutzbaren, "logischen" Qubits möglich sein.

Eine Idee, dieses Problem zu lösen, ist es, mehrere, kleinere Quantencomputer mit einem Quantennetzwerk zu verbinden, um damit eine große Rechenleistung zu erreichen. Das bringt aber wieder andere Probleme mit sich.

Und es gibt wesentliche Einschränkungen beim Quantencomputer-"Rechnen": Qubits können zwar mit Werten beschrieben werden, indem ihr Quantenzustand festgelegt wird, was einen Aspekt des traditionellen Speicher-Konzepts möglich macht. Der wichtige Mechanismus, Speicherbereiche zu kopieren, ist bei Quantencomputern aber nicht möglich. Man kann nicht einfach ein Zwischenergebnis kopieren und dann an zwei Stellen weiterrechnen. Denn jedes Auslesens des Speichers zerstört die Kohärenz und legt den Qubit-Wert auf 0 oder 1 fest. Es gilt das No-Cloning-Theorem.

Auch WENN-DANN-(IF THEN)-Bedingungen wie bei klassischen Computern sind nicht möglich. Das IF benötigt einen Vergleich von Werten. Werden die Werte aus einem Quantensystem dafür ausgelesen, ist die Kohärenz verloren und damit auch die ganze Rechnung. Das ganze Quantenrechensystem muss in sich abgeschottet sein, damit es funktioniert, eine Black-Box. Es funktioniert nur "ungeöffnet". Jeder zwischenzeitliche Abruf einer Quanten-Information zerstört die Rechnung und das Ergebnis. An Debugging des "Quanten-Programmes" ist nicht zu denken, und das macht eine Fehlersuche während der Laufzeit unmöglich und dadurch wird es sehr schwierig, fehlerfreie, komplexe Programme auf Quantencomputern zu entwickeln.

Was man dagegen beim Quantencomputing kann, sind sogenannte Transformationen. Dabei wird ein einzelnes Qubit transformiert, das heißt sein Vektor (wir erinnern uns an die Bloch-Kugeln von oben) verändert. Damit ändern sich dann auch die Wahrscheinlichkeiten mehr zu 0 oder 1 hin. Es gibt Transformationen, die die Rotation ändern und welche, die die relative Phase ändern. Oder die Hadamard-Transformation, die die Wahrscheinlichkeiten auf 50% setzt, später jeweils 0 und 1 zu messen. Diese Transformationen zerstören dabei die Superposition nicht, sie ändern sie nur. Jede Einzel-Qubit-Transformation benötigt aber natürlich die entsprechende "Quanten-Hardware", die auf das Qubit wirkt.

Um das parallele Rechnen zu ermöglichen, benötigt man, wie bereits erwähnt, mehrere Qubits, die miteinander verschränkt sein müssen. Solch eine Gruppierung mehrerer verschränkter Qubits nennt man dann auch Quantenregister. Es gibt allerdings nur begrenzte Möglichkeiten, Qubits innerhalb eines Registers logisch miteinander zu verknüpfen. Dazu kommen dann sogenannte Quantengatter zum Einsatz. Die Gatter bei klassischen Computern haben meist zwei Eingänge (Frage) und einen Ausgang (Ergebnis), also zum Beispiel A | B = E (Bit A ODER Bit B ergibt Ergebnis E) was bedeutet: E ist 1, wenn A ODER B (oder auch beide) 1 sind.

Bei Quantencomputern muss ein Quantengatter immer gleich viele Eingänge wie Ausgänge haben, damit seine Logikoperation umkehrbar (reversibel) bleibt, eine durch die Quantenmechanik vorgegebene Grundvoraussetzung, damit es funktioniert. Ein 1-Bit-Gatter hat demnach einen Eingang und einen Ausgang, ein 2-Bit-Gatter zwei Eingänge und zwei Ausgänge und ein 3-Bit Gatter drei Eingänge und drei Ausgänge. Für eine OR-Verknüpfung bräuchte es also zwei Eingänge (A und B) und zwei Ausgänge (E1 und E2), wobei die Eingänge miteinander wechselwirken. Das macht ein klassisches OR-Gatter für Quantencomputer unmöglich: Würde eine 1 errechnet, gäbe es keine Information mehr darüber, an welchem der Eingänge ursprünglich eine 0 vorlag.

Quantengatter besitzen darum einen ganz anders gearteten Satz an Verknüpfungsoperatoren, die sich größtenteils von den klassischen, logischen Operatoren unterscheiden. Es gibt aber auch Übereinstimmungen im Ergebnis, etwa bei NOT_quant. und NOT_klass. oder CNOT_quant. und XOR_klass.. Man kann weitere klassische, logische Verknüpfungen durch Aneinanderreihung von Quantengattern erreichen, allerdings nicht OR_klass. oder AND_klass., da diese nicht-linear sind. Mit Quantengattern lassen sich aber nur lineare Operationen abbilden. Eigentlich. Denn auch hier kann man wieder tricksen und ein 3-bittiges CCNOT-Gatter, auch Toffoli-Gatter benutzen, wobei Teile der beteiligten Qubits Ergebnisse erhalten, die einem klassischen NAND-Gatter entsprechen. Und das NAND-Gatter ist bekanntlich universell und kann durch Aneinanderreihung alle anderen klassischen Gatter realisieren. Auch AND und OR. Theoretisch. Die praktische Umsetzung wird damit immer schwieriger, denn die Aneinanderreihung von Quantengattern erhöht die Komplexität des Quantensystems weiter. Das erhöht wiederum auch die Anfälligkeit, dass die Kohärenz zerstört wird und ein unbrauchbares Ergebnis herauskommt.

Qubits, die sich gegenseitig beeinflussen sollen, müssen miteinander verschränkt werden. Das erst macht das parallele Rechnen an sich möglich. Die Methoden wie die einzelnen Quantenbits miteinander verschränkt sind, also die Quantengatter, sorgen für die speziellen Operationen untereinander, das Rechnen. Das heißt aber auch - weil die Verschränkung der Gatter fest ist - dass der gesamte Quantenalgorithmus fest "verdrahtet" ist. So wie man früher diskrete Schaltungen für alte Computer nur mit 74xx-Gattern aufgebaut hat, um eine ganz spezielle Funktion - und nur diese eine - zu bewerkstelligen.

Die Programmierung von Quanten-Computer unterscheidet sich also grundlegend von der heutige linearen Programmierung von Algorithmen für heutige gewöhnliche Computer und es ist fraglich, ob es überhaupt irgendwann in ferner Zukunft universell programmierbare Quantencomputer geben wird, weil der Aufwand durch Miniaturisierung (wie beim klassischen Computer) überschaubar geworden sein wird.

Wahrscheinlicher ist es, dass sie - zumindest in der näheren Zukunft - für spezielle Aufgaben, in denen sie ihre Stärken ausspielen kann, einsetzt werden. Dazu gehören zum Beispiel das Lösen von Optimierungsproblemen, zum Beispiel in der Logistik (Stichwort Problem des Handelsreisenden), in der Materialforschung, Biologie und Chemie als auch das Knacken von asymmetrischen Verschlüsselungsverfahren wie RSA durch Quantenkryptoanalyse.

Quellen, Literaturverweise und weiterführende Links