Die faszinierende Welt der Quanten

dürfte aber auch bei einem Erfolg der Technik nicht entstehen. Für die praktische Anwendung sind die gegenwärtigen D-Wave-Modelle noch nicht leistungsfähig genug. Die Firma bietet auf ihrer Homepage aber immerhin schon Programmierkurse für Quantenrechner an.

    Bild 30: Der 128-Qubit-Chip der Firma D-Wave Systems arbeitet als adiabatischer Quanten-Computer
Topologische Quanten-Computer
    Das Konzept des topologischen Quanten-Computers stammt ursprünglich aus der Mathematik – und es ist auch noch nicht komplett in der Physik angekommen. Es beruht auf so genannten Anyonen (nicht zu verwechseln mit den Anionen der Chemie) - das sind Quasi-Teilchen (also Zustände mit Teilchen-Eigenschaften) im zweidimensionalen Raum. In der dreidimensionalen Raumzeit (zwei Ortsdimensionen und eine Zeitdimension) bilden diese so genannte Braids (Flechten).
    Quanten-Braids sind stabiler als zum Beispiel eingefangene Ionen. Damit kodierte Quanten-Information wäre für Fehler weniger anfällig. Die Forscher, die sich mit dieser Materie befassen, haben bisher jedoch nur grundlegende Ideen, wie sich das Konzept in die Wirklichkeit umsetzen lassen könnte.
Die Grenzen des Quanten-Computers
    Der Quanten-Computer galt lange als Wundermittel. Tatsächlich ist er enorm leistungsfähig – wenn er sich mit den passenden Problemen befasst. Dazu gehört, wie erwähnt, die Primzahlfaktorisierung. Hilfreich können die Phänomene der Quantenphysik auch bei Suchalgorithmen sein: Deshalb interessiert sich der Suchmaschinenkonzern Google intensiv für diese Technologie. Mathematisch lässt sich zeigen, dass der Quanten-Computer bei all den Problemen schneller als ein klassischer Rechner ist, die sich durch Ausprobieren lösen lassen, wobei es keinerlei Hinweise darauf gibt, mit welcher Wahrscheinlichkeit eine bestimmte Lösung auftritt. Das perfekte Beispiel dafür ist das Erraten eines Passworts.
    Es gibt aber auch Verschlüsselungsverfahren, gegen die man einen Quantencomputer nicht besonders erfolgreich einsetzen kann. So wurde etwa bereits nachgewiesen, dass er beim oft verwendeten AES-Protokoll lediglich die Schlüssellänge halbiert. Ein aus 256 Bit bestehender Schlüssel ist gegen einen Angriff mit einem Quanten-Computer also genauso effizient wie ein 128 Bit langer Schlüssel gegen einen klassischen Computer.
    Welche Probleme ein Quanten-Computer prinzipiell lösen kann, lässt sich mit Hilfe der Mathematik diskutieren. Wir müssen dazu nach der Komplexität eines Problems fragen. Dabei geht es im Grunde darum, wie lange ein Rechner sowohl für die Lösung als auch für das Nachprüfen eines Lösungsvorschlags braucht.
    Die einfachsten Aufgaben gehören dabei zu den P-Problemen. Das P steht für Polynomialzeit . Die nötige Rechenzeit wächst hier proportional zu einer festen Potenz der Problemgröße. Die Frage, ob eine Zahl eine Primzahl ist, gehört ebenso zu dieser Klasse wie der Check, ob auf einer Straßenkarte jede von x Städten von jeder anderen aus zu erreichen ist. Aufgaben dieser Komplexität sind von klassischen Computern effizient lösbar.
    Formuliert man letztere Aufgabe aber etwas um, erreicht man schon die nächsthöhere Komplexitätsstufe: Gesucht sei eine Route, mit der ein Vertreter alle x Städte auf kürzestem Weg abklappern kann, ohne einen Ort zweimal zu besuchen. Die zur Lösung dieses Problems nötige Rechenzeit wächst exponentiell mit der Zahl x der Städte – die Problemklasse nennt sich „NP“ (nichtdeterministisch polynomial). Exponentielles Wachstum hatten wir schon am Beispiel des Schachspiels diskutiert. Etwas einfacher ist bei NP-Problemen die Prüfung, ob ein Lösungsvorschlag tatsächlich korrekt ist: Dazu ist nur Polynomialzeit nötig, also genügt ein klassischer Computer.
    Das oben genannte Vertreter-Problem gehört übrigens ebenso wie die beliebten Sudoku-Rätsel zu einer speziellen Abteilung der NP-Probleme: Es ist „NP-vollständig“. Solche Probleme haben die interessante Eigenschaft, dass jeder effiziente Algorithmus für eine dieser Aufgaben auch auf alle anderen übertragbar wäre. Schade nur, dass bisher kein einziger solcher Rechenweg bekannt ist... Gäbe es ihn, hätte das allerdings auch eine Revolution in der Mathematik zur Folge.
    Quantencomputer können einige (zum Beispiel die Primfaktoren -Zerlegung), aber nicht alle NP-Probleme lösen. Vermutlich jedenfalls: Bisher konnte trotz eines Preisgelds von einer Million Dollar noch niemand streng mathematisch widerlegen, dass es nicht