Quantencomputer: Die Fast-alles-Rechner
Klassische Rechner sind Beschränkungen unterworfen, die in ihrer Natur liegen. Betrachten wir eine simple Aufgabe: die Primfaktorenzerlegung einer natürlichen Zahl. Schulstoff aus der fünften oder sechsten Klasse also. Obwohl die schnellsten Supercomputer heute Billiarden Rechenschritte pro Sekunde ausführen können, bräuchten sie für die Primfaktorenzerlegung einer 300-stelligen Zahl noch immer etwa 150 Jahre. Das freut all die, die Daten zu sichern haben, denn viele moderne Verschlüsselungsverfahren schöpfen ihre Sicherheit aus der Tatsache, dass die Primfaktorenzerlegung sehr, sehr aufwendig ist.
Deshalb musste man die Verschlüsselungsalgorithmen auch schon des Öfteren anpassen – wer hätte vor 50 Jahren vorherzusagen gewagt, wie schnell heutige Chips rechnen? Quantencomputer allerdings machen dem kompletten Kryptographiegewerbe einen Strich durch die Rechnung, denn sie versprechen einen radikalen Fortschritt: Wofür ein Supercomputer heute noch 150 Jahre braucht, dafür benötigen sie gerade mal eine Sekunde. Worauf beruht dieser enorme Fortschritt?
Das Quanten-Bit
In der Quantenphysik bekommt die Grundeinheit der Information eine neue Bedeutung: Aus dem Bit wird das Qubit (gesprochen Kjubit). Während ein klassisches Bit sich für einen Zustand entscheiden muss, existiert das Qubit als Superposition aller möglichen Zustände, es ist also 0 und 1 und irgendetwas dazwischen gleichzeitig.
Die Theoretiker symbolisieren das gern durch die Bloch-Kugel. Die klassischen Werte 0 und 1 werden durch Pfeile durch den Nord- und den Südpol dieser Kugel dargestellt. Das Qubit kann aber auch alle anderen Werte annehmen, die auf der Kugeloberfläche liegen.
Auf den ersten Blick könnte man deshalb vermuten, dass sich in einem Qubit unendlich viele Informationen verstecken lassen. Denn die Kugeloberfläche bietet ja Platz für alle möglichen Kombinationen von Werten. Ganz so leicht macht es uns die Quantentheorie aber dann doch nicht, denn bei jeder Messung wird aus der Überlagerung von Zuständen schließlich doch wieder ein ganz konkreter Zustand, ein klassisches Bit.
Mit welcher Wahrscheinlichkeit 0 oder 1 auftreten, das wird durch die vorherige, uns außerhalb der Messung verborgen bleibende Zustandsmischung definiert.
Verschränkung muss sein
Mit einem einzelnen Qubit ist deshalb praktisch noch nicht viel anzufangen. Wir brauchen ein weiteres Phänomen der Quantenphysik, die Verschränkung. Dabei handelt es sich um ein Quanten-Phänomen, bei dem zwei Teilchen so miteinander verknüpft sind, dass eine Änderung am einen auch eine Änderung am anderen bewirkt – egal, wie weit beide voneinander entfernt sind. Gelingt es, zwei Qubits miteinander zu verschränken, ist ihr gemeinsamer Zustand eine Überlagerung aller Einzelzustände.
Wenn wir nun mit dieser Bit-Kombination rechnen, führen wir unsere Rechnung nicht an einem einzelnen Satz von Werten aus, sondern an allen möglichen Wertekombinationen gleichzeitig. Bei zwei Qubits sind das zwar nur vier Kombinationen, doch die Zahl wächst exponentiell mit der Zahl der verschränkten Qubits.
Fragile Systeme
Forscher haben schon vor einiger Zeit gezeigt, dass sich darauf aufbauend ein sehr leistungsfähiger Computer konstruieren lässt, der klassische Rechner in bestimmten Disziplinen um Längen schlägt. Allerdings stellt es die Wissenschaftler vor große Schwierigkeiten, so ein Gerät zu konstruieren. Quanten-Systeme sind sehr fragil.
Damit sie als Computer nutzbar sind, müssen sie sich widersprechenden Anforderungen genügen: Einerseits müssen die einzelnen Qubits gut voneinander und von der Umgebung isoliert sein, um nicht ihre Quanteneigenschaften zu verlieren (das nennt man Dekohärenz). Andererseits müssen die Qubits untereinander verschränkt sein und sich mit Messungen auslesen lassen.
Weltweit forschen Teams derzeit daran, wie sich all diese Anforderungen am besten umsetzen lassen. Jede Technik hat ihre Vor- und Nachteile. Wer in 20, 30 oder auch 50 Jahren das Rennen machen wird, ist noch lange nicht klar. Gemeinsam haben die Verfahren, dass sie sehr niedrige Temperaturen benötigen: nahe dem absoluten Nullpunkt.
Rechnen mit Licht
Es gibt viele Wege, einen Quantencomputer zu konstruieren. Ein geeignetes System muss fünf Kriterien erfüllen, die erstmals der IBM-Forscher David DiVincenzo formuliert hat:
• Man braucht ein Qubit, also ein quantenphysikalisches System mit einer Überlagerung aus zwei gut trennbaren Zuständen.
• Es muss möglich sein, die Qubits in einen definierten Anfangszustand zu versetzen.
• Die Qubits müssen sich auslesen lassen.
• Es müssen Rechenoperationen an den Qubits möglich sein.
• Die Dekohärenz-Zeit muss länger sein als die Zeit, die man für einen Rechenschritt inklusive Vorbereitung und Auslesen braucht.
Es bietet sich an, mit dem System zu starten, das in der Quantenphysik zuerst die Aufmerksamkeit der Forscher bekam: mit dem Licht. Das sogenannte optische Quanten-Computing hat den Vorteil, dass verschränkte Lichtteilchen (Photonen) schnell und billig herzustellen sind. Kein anderes System lässt sich so sauber verschränken wie die Photonen. Was jedoch nicht so simpel ist: die Lichtteilchen miteinander wechselwirken zu lassen. Ein weiterer kleiner Nachteil: Photonen entfliehen den Forschern mit Lichtgeschwindigkeit.
Dieser Fluchtinstinkt hat aber für die praktische Anwendung auch einen gewissen Charme, denn so lassen sich Informationsverarbeitung und -übertragung gut verbinden. Optischer Datentransfer über Glasfaserkabel ist heute längst Standard. Bei anderen Verfahren müsste man hingegen einen Wandler dazwischenschalten, der naturgemäß verlustbehaftet ist.
Atome in Fallen
Natürlich kann man einen Quantencomputer auch Stück für Stück aus seinen Grundbausteinen zusammensetzen, etwa aus Atomen oder Ionen. Diese Herangehensweise, die Ionenfalle, wählen etwa die Physiker der für ihre Quantenphysik-Abteilung bekannten Innsbrucker Universität. Nutzt man nur wenige Atome, fällt es deutlich leichter, diese zu kontrollieren. Trotzdem müssen die Atome extrem tiefgekühlt sein, damit ihre Eigenbewegung keine Rolle mehr spielt.
Außerdem stören schon kleinste Vibrationen – die Innsbrucker Forscher haben sich deshalb beim Neubau ihres Institutsgebäudes einen riesigen, gummigelagerten Betonklotz im Keller installieren lassen, der einen darauf fixierten Experimentiertisch von sämtlichen Vibrationen isoliert.
Wie funktioniert eine Ionenfalle? Zunächst gilt es, einige wenige Ionen zu isolieren. Da sie eine elektrische Ladung besitzen, kann man sie mit Hilfe elektrischer Felder festhalten. Sie sitzen dann wie auf einer Perlenschnur aufgereiht im Vakuum der Apparatur. Bevor man ins Quantenregime kommt, muss man ihnen aber auch noch den größten Teil ihrer Bewegungsenergie abnehmen.
Dazu benutzen die Forscher verschiedene Verfahren, die in unterschiedlichen Temperaturbereichen funktionieren. Im untersten Bereich hilft dann nur noch die sogenannte Dopplerkühlung, bei der den Teilchen mit genau abgemessenen Stößen durch Photonen ein Teil ihres Impulses entzogen wird. Erst beim winzigsten Teil eines Kelvin sitzen die Ionen so ruhig in der Falle, dass man sie in eine gemeinsame Anregung versetzen kann – auch dabei kommt wieder ein Laser zum Einsatz. Dessen Frequenz muss zu den Eigenschaften der Ionen passen. Auf diese Weise ist es den Innsbrucker Forschern gelungen, immerhin 14 Ionen miteinander zu verschränken – das ist derzeit noch Weltrekord. Kein anderes Verfahren kommt dem derzeit nahe. Auch was die Güte und Vielfalt der auf Ionenfallen möglichen Quanten-Operationen betrifft, liegen derartige Systeme weit vorn.
Stromkreise und Quantenpunkte
Für eine praktische Umsetzung könnte es sich allerdings als ungünstig erweisen, dass man eine größere Apparatur braucht, um Ionen im Vakuum schweben zu lassen. Die Ionenfallen sind gewissermaßen die Elektronenröhren der Quantencomputer: Alle Hoffnung ruht darauf, diese irgendwann durch eine Art von Transistoren, also festkörperbasierte Systeme, zu ersetzen. Unter anderen befassen sich Forscher des Chipherstellers IBM intensiv mit dieser Technik.
Ein Festkörper-Quantencomputer lässt sich zum Beispiel mit Hilfe der Supraleitung umsetzen. Bei sehr tiefen Temperaturen verlieren Stoffe ihren elektrischen Widerstand: Strom kann also verlustlos fließen. Als Qubit dient den Forschern nun ein supraleitender Stromkreis, den Strom in der einen Richtung (Bit = 1) oder in der entgegengesetzten Richtung (Bit = 0) durchfließen kann. Im Quantenregime überlagern sich die Stromflüsse in beide Richtungen, der Strom fließt also links- und rechtsherum gleichzeitig.
Ein Festkörper-Quantencomputer dieser Art besteht also nicht aus einzelnen Teilchen, sondern gleich aus Milliarden von Elektronen. Damit stellt er ein sehr komplexes System dar, das leider zu schneller Dekohärenz neigt. Immerhin haben die Festkörper-Quantencomputer einen wichtigen Vorteil: Die einzelnen Qubits sind mitsamt der sie umgebenden "Apparatur" sehr klein und lassen sich auf einem Chip integrieren.
Adiabatische Quantencomputer
Für viele Forscher stellt dieses Konzept gar keinen echten Quantencomputer dar, denn die Verschränkung mehrerer Qubits spielt hier gar keine Rolle. Es beruht darauf, dass ein System im Grundzustand (also mit der absoluten Mindestenergie) seine Quanten-Eigenschaften nicht verändert, solange die Wechselwirkung mit der Umwelt klein genug ist, dass sie unter der Schwelle für den nächsthöheren Zustand bleibt – das nennt man eine adiabatische Zustandsänderung.
Die Idee ist, einen bestimmten Zustand zu präparieren und diesen dann mit kleinsten Anstößen so weit zu verändern, dass ein anderer, gesuchter Grundzustand erreicht wird, der der Lösung des Problems entspricht und gemessen werden kann. Adiabatische Quantencomputer sind dadurch weit weniger flexibel als "echte". Ob sie klassischen Computern prinzipiell überlegen sind (und bei welcher Art von Problemen), ist derzeit noch Diskussionsgegenstand unter den Forschern.
Öffentliche Aufmerksamkeit bekamen sie durch die US-Firma D-Wave Systems. Deren "D-Wave 2" rechnet angeblich bereits mit 512 Qubits, während die internationale Forschergemeinde nur schwer über 10 Qubits hinaus kommt. Die Technik der Firma basiert auf supraleitenden Schaltkreisen, die zu einem "Chip" vereinigt werden. Allerdings sind wohl nicht alle Qubits auch miteinander verschränkt. Im Juni konnte ein internationales Forscherteam im Fachmagazin Science denn auch zeigen, dass D-Wave 2 bei für Quantencomputer optimierten Aufgaben nicht schneller rechnet als ein klassischer Computer.
Topologische Quantencomputer
Das Konzept des topologischen Quantencomputers stammt ursprünglich aus der Mathematik – und es ist auch noch nicht komplett in der Physik angekommen. Es beruht auf sogenannten 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 sogenannte Braids (Flechten).
Quanten-Braids sind stabiler als zum Beispiel eingefangene Ionen. Damit kodierte Quanten-Informationen wären für Fehler also weniger anfällig. Allerdings fehlt den Forschern noch ein physikalisches Trägersystem für das mathematische Modell. Infrage kommen lediglich Quasiteilchen, Anregungszustände also, wenn diese zweidimensionaler Natur sind (also sich etwa auf Oberflächen beziehen).
Zu den vielversprechenden Kandidaten gehört der Quanten-Spin-Hall-Effekt, der die Existenz eines sogenannten topologischen Isolators bewirkt. Das ist ein Stoff, der eigentlich nicht leitet, an dessen Oberfläche aber trotzdem Ströme fließen, und zwar Spin-Ströme. Ein anderer interessanter Kandidat ist der fraktionale Quanten-Hall-Effekt, der die Wirkung eines starken Magnetfelds auf eine flache Wolke von Elektronen beschreibt. Dabei verhält sich das System, als bestünde es aus Quasiteilchen mit einem Drittel der Elektronenladung.
Ein dritter Kandidat wären speziell komponierte Supraleiter, an deren Grenzflächen sich ebenfalls zweidimensionale Quasiteilchen nachweisen lassen. Tatsächlich ist derzeit allerdings noch nicht einmal nachgewiesen, ob sich mit den so erzeugten Anyonen auch Quanten-Berechnungen ausführen lassen.
Die Grenzen des Quantencomputers
Der Quantencomputer galt lange als Wundermittel. Tatsächlich ist er enorm leistungsfähig – wenn er sich mit den passenden Problemen befasst. Dazu gehört die Primzahlfaktorisierung, hilfreich kann er aber auch bei Suchalgorithmen sein. Mathematisch lässt sich zeigen, dass der Quantencomputer bei all jenen 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 Quantencomputer also genauso effizient wie ein 128 Bit langer Schlüssel gegen einen klassischen Computer.
Welche Probleme ein Quantencomputer prinzipiell lösen kann, lässt sich mit Hilfe der Mathematik diskutieren. Wir müssen dazu nach der Komplexität eines Problems fragen – ein Forschungsgebiet der theoretischen Informatik. 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.
Was der Quantencomputer kann – und was nicht
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). 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 Vertreter-Problem gehört, 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, wäre das allerdings auch eine Revolution in der Mathematik.
Computer auf Zeitreise
Quantencomputer können einige, 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 vielleicht doch einen effizienten, in Polynomialzeit einzusetzenden Algorithmus für NP-Probleme geben könnte, dass also P nicht gleich NP ist.
Eine weitere Problemklasse nennt sich PSPACE. Dazu gehören zum Beispiel vollständige Lösungen der Spiele Schach und Go. Sie enthält Probleme, zu deren Lösung man eine polynomial wachsende Speichermenge und exponentiell wachsende Rechenzeit benötigt. Aufgaben aus dem PSPACE sind klassischen Computern nicht zugänglich. Bei Quantencomputern ist man sich da nicht sicher. Bisher ist aber kein dazu fähiger Algorithmus bekannt.
Könnte es einen Computertyp geben, der dem Quantencomputer überlegen ist? Dazu bräuchte man neue physikalische Prinzipien, von denen heute noch nichts bekannt ist. Forscher schlagen zum Beispiel vor, den Computer auf eine Zeitreise zu schicken. Das Prinzip: Man schickt den Computer einfach so lange und so oft in die Vergangenheit, bis das Problem zum heutigen Zeitpunkt gelöst ist. Dazu bräuchte man die Existenz sogenannter geschlossener zeitartiger Kurven (closed timelike curves, CTCs), die sich als mögliche Lösung der Allgemeinen Relativitätstheorie ergeben. Damit arbeitende Computer könnten sogar Probleme der Klasse PSPACE effizient lösen. Physiker vermuten allerdings, dass CTCs von einer künftigen Vereinigung von Quanten- und Relativitätstheorie wieder ausgeschlossen werden.
Das E-Book "Die faszinierende Welt der Quanten" des Autors ist bei Beam-eBooks(öffnet im neuen Fenster) (DRM-frei, ePub, PDF, Mobi), bei Amazon(öffnet im neuen Fenster) (Mobi) und Apple(öffnet im neuen Fenster) (iPad-Version mit Videos und Fotos) erhältlich.