Wie der Quanten-Computer funktioniert

Geheimdienste fürchten sie, Forscher hoffen, mit ihnen bislang unlösbare Probleme berechenbar zu machen: Quanten-Computer gelten als beinahe magische Maschinen

Der folgende Beitrag ist vor 2021 erschienen. Unsere Redaktion hat seither ein neues Leitbild und redaktionelle Standards. Weitere Informationen finden Sie hier.

Mein Hahn ist tot. Mon coq est mort. Das sind zwei sehr unterschiedliche Sätze, auch wenn sie jeweils aus vier Wörtern bestehen. Auf grundlegender Ebene haben sie aber eine Gemeinsamkeit: Sie enthalten die gleiche Information, die von der sprachlichen Verkörperung unabhängig ist. Es gibt sehr viele, unendliche viele Möglichkeiten, die gleiche Information darzustellen, so wie Energie in den verschiedensten Formen auftreten kann. Trotzdem, das weiß jeder Übersetzer, muss bei der Umwandlung aus einer Form in die andere der Kern, die Information, immer konstant bleiben: Mein Hahn ist tot.

Es gibt eine weitere Ähnlichkeit zwischen Energie und Information: Auch die Information besitzt eine Einheit. Weil der Begriff erst viel später aufkam, war sofort klar, dass sie quantisiert sein muss, also in nicht mehr teilbaren Brocken auftritt. Diese Informationsquanten sind die Bits. Ein Bit kann genau zwei Zustände einnehmen. Gern wird das Bild von 0 und 1 gebraucht - aber ebenso könnte man die zwei Zustände durch Ein und Aus, Heiß und Kalt, Kurz und Lang, Loch und kein Loch realisieren. Wie beim toten Hahn kommt es nicht auf die Form der Darstellung, sondern auf die Information selbst an.

Bei der Konstruktion klassischer Computer hat man sich immer schlauere Methoden gesucht, 0 und 1 umzusetzen. Auf der ganzen Welt, schätzte das Marktforschungsunternehmen IDC, gab es 2011 insgesamt etwa 1800 Exabytes an digital vorliegenden Informationen. Das ist ungefähr so viel Datenmaterial, als besäße jeder Mensch auf der Erde etwa 20.000 Bücher. Pro Jahr wächst dieser riesige Datenvorrat um 60 Prozent. Doch obwohl dem Wachstum keine Grenzen gesetzt scheinen, sind klassische Rechner Beschränkungen unterworfen, die in ihrer Natur liegen.

Betrachten wir nur eine simple Aufgabe: die Primfaktorenzerlegung einer natürlichen Zahl. Schulstoff aus der fünften oder sechsten Klasse also: Es geht darum, eine Zahl als Produkt anderer, nur durch sich selbst und 1 teilbarer Zahlen (sogenannter Primzahlen) darzustellen. 10 ist das Produkt aus den Primzahlen 2 und 5. 21 lässt sich in die Primfaktoren 3 und 7 zerlegen. Es gibt dafür maschinelle Verfahren, Algorithmen, die das Problem mit Computerhilfe lösen. Doch obwohl die allerschnellsten 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.

Wofür ein Supercomputer heute noch 150 Jahre braucht, dafür benötigen sie gerade noch eine Sekunde

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 aufwändig ist. Deshalb musste man die Verfahren auch schon des öfteren anpassen - wer hätte vor 50 Jahren vorherzusagen gewagt, wie schnell heutige Chips rechnen? Quanten-Computer allerdings machen dem kompletten Kryptografie-Gewerbe 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 noch eine Sekunde. Worauf beruht dieser enorme Fortschritt?

In der Quantenphysik bekommt die Grundeinheit der Information eine neue Bedeutung: Aus dem Bit wird das Qubit. Während ein klassisches Bit sich jedoch für einen Zustand entscheiden muss, existiert das Qubit als Superposition aller möglichen Zustände, es ist also 0 und 1 und irgend etwas dazwischen gleichzeitig. Die Theoretiker symbolisieren das gern durch die so genannte 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 einer Messung wird aus einer Überlagerung von Zuständen schließlich doch wieder ein ganz konkreter Zustand, ein klassisches Bit, entweder 0 oder 1. Mit welcher Wahrscheinlichkeit man 0 oder 1 misst, das wird allerdings durch die vorherige, uns außerhalb der Messung verborgen bleibende Zustandsmischung definiert.

Die Verschränkung

Mit einem einzelnen Qubit ist deshalb praktisch noch nicht viel anzufangen. Wir brauchen ein weiteres Phänomen der Quantenphysik, die Verschränkung. 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 Werte-Kombinationen gleichzeitig. Bei zwei Qubits sind das zwar nur vier Kombinationen, doch die Zahl wächst exponentiell mit der Zahl der verschränkten Qubits.

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 stellte es die Wissenschaftler vor große Schwierigkeiten, so ein Gerät zu konstruieren. Quanten-Systeme sind zum einen sehr fragil. Damit sie als Quanten-Computer nutzbar sind, müssen sie zudem sich widersprechenden Anforderungen genügen: Einerseits müssen die einzelnen Qubits gut voneinander und von der Umgebung isoliert sein, um nicht der Dekohärenz anheim zu fallen, also ihre Quanteneigenschaften zu verlieren. Andererseits müssen die Qubits untereinander verschränkt sein und sich mit Messungen auslesen lassen - ein Computer, dessen Ergebnisse man nicht deuten kann, hilft nicht wirklich weiter.

DiVincenzo-Kriterien

Weltweit forschen Teams derzeit daran, wie sich all diese Anforderungen am besten umsetzen lassen. Jede der im folgenden geschilderten Techniken hat dabei ihre Vor- und Nachteile. Wer in 20 oder 30 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. Allein dafür mussten sich die Forscher bereits jede Menge neuer Technologien ausdenken.

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 (deshalb nennt man sie auch DiVincenzo-Kriterien):

  1. man braucht ein Qubit,
  2. es muss möglich sein, die Qubits in einen definierten Anfangszustand zu versetzen,
  3. die Qubits müssen sich auslesen lassen,
  4. es müssen Rechenoperationen an den Qubits möglich sein und
  5. die Zeit, in der die Qubits ihre Quanten-Eigenschaften verlieren, 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 optische Quanten-Computing hat den Vorteil, dass verschränkte 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 versuchen dauernd, den Forschern mit Lichtgeschwindigkeit zu entfliehen. Als Lichtteilchen haben sie ja auch keine andere Wahl.

Verkleinerungen

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.

Derzeit sind die Wissenschaftler dabei, die entsprechenden Strukturen zu verkleinern: Während man im Labor noch große Arbeitstische mit Laserquellen, Strahlenteilern, Spiegeln und so weiter vorfindet, ist es unter anderem an der Universität Bristol schon gelungen, zwei Qubits auf der Fläche eines "Chips" (immer noch 70 mal 3 Millimeter groß) unterzubringen. Wiener Forscher hoffen, mit der so genannten "kohärenten Photonen-Umwandlung" ein ganz neues Werkzeug schaffen zu können, das die Konstruktion optischer Quantenrechner deutlich erleichtern würde. Dass das Verfahren funktioniert, konnten die Forscher schon zeigen - es ist allerdings noch nicht komplett umgesetzt. Falls das gelingt, würden alle nötigen Schritte des Quantenrechnens vereinfacht: Es wäre leichter als bisher, die Qubits zu erzeugen, daran Algorithmen auszuführen und die Ergebnisse auszulesen.

Quantensimulatoren

Eher eine Hilfsrolle spielen Photonen bei dem Weg, den unter anderem Forscher des Garchinger Max-Planck-Instituts für Quantenoptik beschreiten: Sie fangen eine größere Anzahl von Atomen in einem Gitter ein, das aus Laserstrahlen gebildet wird. Dieses Gitter erzeugt für die neutralen Atome eine Struktur, die einer Eierverpackung gleicht. In jedem der "Eierlöcher" findet statt eines Hühnereis ein Atom Platz. Allerdings können die Forscher die Eigenschaften des Gitters verändern. Sie können die Stege schmaler oder niedriger machen und beobachten, wie sich die Atome nun verhalten. Bricht man aus einer Eierverpackung die Pappstege heraus, kullern die Eier plötzlich durcheinander - Atome verhalten sich nach den Gesetzen der Quantenphysik und nutzen zum Beispiel die niedrigeren Hürden für den Tunneleffekt.

Das lässt sich zwar nicht zum Rechnen einsetzen, führt aber trotzdem zur Lösung wissenschaftlicher Probleme. Die Gitterstrukturen ähneln nämlich erstaunlich denen, die etwa Elektronen in Festkörpern vorfinden, nur dass sie sich hier im Labor weit besser manipulieren lassen. Das Ergebnis könnten neuartige Materialien sein, denen man anders nicht auf die Spur gekommen wäre.

Was die Forscher damit gebaut haben, ist ein Quantensimulator: Ein System, das das Verhalten eines anderen Quanten-Systems simuliert und damit Rückschlüsse erlaubt. Quantensimulatoren sind derzeit für die Physiker ein sehr heißes Eisen, weil sie mit vergleichsweise geringem Aufwand (der Aufbau eines solchen Experiments dauert trotzdem zwei, drei Jahre) bereits bestimmte Funktionen von Quanten-Computern übernehmen, die sicher noch zwanzig Jahre auf sich warten lassen werden. Derzeit arbeiten die Forscher daran, ihre Kontrollmöglichkeiten über einzelne Atome zu verbessern. Sollten sie dabei erhebliche Fortschritte erzielen, hätten sie plötzlich einen Quanten-Computer mit sehr vielen Qubits vor sich.

Die Ionenfallen

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 unter anderem Physiker der für ihre Quantenphysik-Abteilung bekannten Innsbrucker Universität. Nutzt man nur wenige Atome, fällt es deutlich leichter, diese zu kontrollieren. Zwischen "leichter" und "leicht" besteht leider noch eine große Diskrepanz. Wenn man mit derart kleinen Objekten zu tun hat, fällt jede Störung ins Gewicht. Die Atome müssen extrem tief gekü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 in der Praxis? 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 so genannte 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. Auf diese Weise ist 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.

Für eine praktische Umsetzung könnte 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 Quanten-Computer: Alle Hoffnung ruht darauf, diese irgendwann durch eine Art von Transistoren, also festkörperbasierte Systeme, ersetzen zu können. Es ist kein Zufall, dass sich ausgerechnet Forscher des Chipherstellers IBM intensiv mit dieser Technik befassen: Hier kennt man sich besonders gut mit den zur Fertigung kleinster Strukturen nötigen Techniken aus. Außerdem sucht IBM bereits jetzt nach einer Ablösung für den klassischen Transistor, der bereits bei Strukturgrößen von nur 22 Nanometern angekommen ist.

Ein Festkörper-Quantencomputer

Ein Festkörper-Quantencomputer lässt sich zum Beispiel mit Hilfe der Supraleitung umsetzen. 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. Eine IBM-Gruppe um den Deutschen Matthias Steffen hat mit dieser Methode Anfang 2012 seht gute Erfolge erzielt. Ihr Quanten-Computer besteht aus drei Qubits, die aus zwei supraleitenden Elektroden aus Niob und einem Isolator aus Aluminiumoxid konstruiert sind und auf einer Siliziumunterlage sitzen.

Das komplette System funktioniert zwar nur bei einer Temperatur von einem Hundertstel Kelvin, aber die Kühltechnik beherrschen die Forscher inzwischen sehr gut. Auf diese Weise gelang es ihnen nun, die Verschränkung so lange stabil zu halten, dass sich mit den Qubits auch rechnen ließe. Das ist ab zehn bis 100 Millionstel Sekunden der Fall.

Ein Festkörper-Quantencomputer dieser Art besteht nicht aus einzelnen Ionen oder Photonen, sondern gleich aus Milliarden winziger Elektronen, die bei extrem tiefen Temperaturen ohne Widerstand durch den Stromkreis flitzen - im Grunde ein sehr komplexes System, das leider zu schneller Dekohärenz neigt. Insofern ist den Wissenschaftlern hier ein spannender Erfolg gelungen.

Im nächsten Schritt wollen sie nun daran gehen, von zwei oder drei Qubits zu größeren Systemen zu wechseln. Da eine Quanten-Operation bei dieser Technik etwa 0,1 Mikrosekunden dauert, ist mit den Qubits der IBM-Forscher durchaus schon etwas anzufangen. Immerhin haben die Festkörper-Quanten-Computer einen wichtigen Vorteil: Die einzelnen Qubits sind mitsamt der sie umgebenden "Apparatur" sehr klein und lassen sich auf einem Chip integrieren.

Die allerersten Computer, etwa die von Charles Babbage entworfene Difference Engine, bedienten sich zum Rechnen mechanischer Elemente. Kühlt man sie nur weit genug ab, nehmen mechanische Elemente aber auch Quanten-Verhalten an. Das zeigen unter anderem Experimente der Gruppe von Markus Aspelmeyer an der Universität Wien und von Wissenschaftlern des Caltech. Die Forscher gehen damit schon sehr weit in Richtung der realen, makroskopischen Welt, denn ihre winzigen, einen tausendstel Millimeter breiten und mehrere hundertstel Millimeter langen Sprungbretter bestehen aus Milliarden von Atomen.

Um solche Objekte auf ihren Grundzustand zu kühlen, genügen gewöhnliche Verfahren nicht. Die Wissenschaftler nutzen stattdessen Photonen, um die Energie der Bewegungsquanten des mechanischen Systems, der Phononen, nach außen abzuleiten. Damit haben die Forscher nicht nur eine clevere Kühlmethode gefunden, sondern auch einen Mechanismus, mit dem man das mechanische System mit Licht koppeln kann. Die Idee dahinter: womöglich gelingt es ja, auf diese Weise Quanten-Informationen in den kleinen Siliziumbrücken zu speichern und wieder auszulesen. Ein solches System wäre als Speichermedium für einen Quanten-Computer geeignet. Ganz nebenbei hoffen die Forscher aber auch, mit ihren Methoden Vermutungen der Quanten-Gravitation überprüfen zu können (also der immer noch gesuchten Verbindung aus Quantenphysik und Gravitationstheorie): Dazu hat man sich bisher (eher erfolglos) astrophysikalischer Methoden bedient.

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. 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).

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 vielleicht doch einen effizienten, in Polynomialzeit einzusetzenden Algorithmus für NP-Probleme geben könnte, dass also P nicht gleich NP ist. Es ist aber sehr wahrscheinlich, dass der Unterschied besteht - ließe sich das Gegenteil beweisen, wären alle NP-Probleme auch für klassische Computer zugänglich. Vollständige Lösungen der Spiele Schach und GO ordnet man übrigens in die Klasse PSPACE ein: 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 Quanten-Computern ist man sich da nicht sicher. Bisher ist aber kein dazu fähiger Algorithmus bekannt.

Der Text ist ein Ausschnitt aus dem E-Book "Die faszinierende Welt der Quanten", das der Autor als iBook (für Apple iPad) und DRM-freies Kindle-eBook (mit dem Programm Calibre in ePub wandelbar) veröffentlicht hat.