Quantencomputer: Alleskönner mit Grenzen
Die Quanten kommen: Alles Wissenswerte über Quantenthemen erfahren Sie auch auf der Konferenz von Golem.de am 23. Juni in Berlin!
Weitere Artikel vorlesen lassen:
Der Vorteil, das große Versprechen eines Quantencomputers lässt sich auf ein einzelnes Phänomen herunterbrechen: die Superposition, also die Tatsache, dass im Quantenregime bis zur Messung stets eine Überlagerung vieler Zustände, Möglichkeiten, vorliegt, die von der Wellenfunktion des Systems beschrieben wird. Wenn man das Bit der klassischen IT, das stets entweder aus oder an, entweder 0 oder 1 ist, in die Quantenwelt überträgt, erhält man ein viel flexibleres Bit, das alle möglichen Zustände gleichzeitig annehmen kann. Jede Operation, die man darauf anwendet, wird dadurch an allen Zuständen parallel ausgeführt. Das Bit des Quantencomputers heißt zur besseren Unterscheidung auch Qubit. Anschaulich bedeutet das, dass der Rechner nicht wie ein klassischer Computer bloß 1 + 1 = 2 ausrechnet, sondern x + y = z, und zwar für alle möglichen Werte von x und y.
In der Praxis ergibt sich dann zwar immer noch das Problem, das gewünschte Ergebnis geschickt auszulesen, aber das ist lösbar - und eine Frage, um die sich die Entwickler von Quantenalgorithmen kümmern. Der Dimension, um die sich die Leistungsfähigkeit dank des Quantenphänomens Superposition verbessert, tut das keinen Abbruch.
Trotzdem werden heute noch immer neue Supercomputer gebaut, steigt die Leistungsfähigkeit selbst von Desktoprechnern von Jahr zu Jahr. Warum steht nicht längst unter jedem Schreibtisch ein Quantencomputer? Wieso konstruieren IBM & Co. nach wie vor immer schnellere Superrechner, statt Milliarden in die Entwicklung des Quantencomputers zu investieren? Dafür gibt es eine ganze Reihe von Ursachen, die sich in zwei Punkten zusammenfassen lassen: Sie sind schwer zu skalieren, und sie sind schwer zu programmieren. Hinzu kommt, dass sich selbst die Experten noch lange nicht einig sind, wie leistungsfähig ihre verschiedenen Ausprägungen tatsächlich sind.
Problem 1: von einem zu vielen Bits
Seit Peter Shor 1994 zeigte, dass sich mit Quantencomputern in polynomialer Zeit Primzahlen faktorisieren lassen (eine wesentliche Grundlage der meisten aktuellen kryptographischen Algorithmen besteht darin, dass genau das nicht möglich ist), erfreut sich das Konzept allergrößten Interesses. Schnell konnte man es auch praktisch umsetzen: zunächst mit ein, zwei, drei Bits, 2005, also vor nun zwölf Jahren, kam man bei sechs bis acht Bits an und prognostizierte, dass damit nun der Durchbruch erreicht sei. Heute können "klassische" Quantencomputer im besten Fall auf eine zweistellige Zahl von Bits zugreifen.
Das hat vor allem physikalische Gründe. Quantenzustände sind sehr fragil. Passt man nicht auf, fallen sie der Dekohärenz anheim, geben also die Superposition zugunsten eines klassischen Entweder-Oder auf. Am besten kann man sie schützen, indem man das System sehr stark kühlt und von der Außenwelt isoliert. Aber das ist aufwendig. Quantenrechner, die mit Ionenfallen oder Photonen arbeiten, dürften deshalb kaum eine industrielle Zukunft haben (in der Gegenwart sind sie allerdings spannend, weil sie sich besonders gut untersuchen und manipulieren lassen). Am vielversprechendsten dürften auf supraleitenden Schaltkreisen basierende Quantencomputer sein. Sie benötigen zwar ebenfalls tiefe Temperaturen, bieten jedoch die Aussicht, sich in Siliziumtechnik integrieren und deutlich verkleinern zu lassen.
Neben der Dekohärenz gibt es ein zweites Problem, das die Forscher beschäftigt.
So ein Quantencomputer ist anders
Im Quantenregime sind Messungen immer rein statistischer Natur. Man benötigt deshalb ausgefeilte Fehlerkorrektur-Mechanismen, die meist direkt an die genutzte Architektur anzupassen sind. Die Effizienz eines "ausgereiften" Quantencomputers würden sie kaum beeinflussen, aber so weit ist die Forschung eben noch nicht.
Problem 2: Quantencomputer programmieren
Den richtigen Umgang mit dem Quantencomputer zu erlernen, ist ein zeitraubender Prozess. Stellen Sie sich vor, Ihr Kollege Ingenieur hat einen Abakus entwickelt. Es gibt spannende Theorien darüber, was man damit alles ausrechnen kann. Addieren und Subtrahieren sind klar, einfach ein paar Kugeln hin und her schieben, fertig. Aber wie sieht es mit der Multiplikation aus? Sie wissen, wie man schriftlich multipliziert, doch auf dem Abakus funktioniert das ganz anders. Sie müssen also erst einen Algorithmus dafür finden.
Nun hat die Mathematik für eindeutige Zustände schon seit Jahrhunderten jede Menge Algorithmen parat - doch das seltsame Verhalten im Quantenreich ist auch ihr neu. Quantencomputer sind zumindest heute keine Universalmaschinen, denen man jedes beliebige Problem vorlegen kann. Vermutlich werden sie das aus sich heraus auch nie werden. Vielleicht wird man in Zukunft an einem herkömmlichen Supercomputer arbeiten, der nur passende Operationen eigenverantwortlich an ein Quantenmodul auslagert. Doch so weit ist die Forschung noch nicht - heute geht es vor allem darum, geeignete Algorithmen zu finden und an die aktuellen Quantencomputer-Konzepte anzupassen. Dadurch relativiert sich ein wenig das Problem, dass noch keine Quantencomputer mit sehr vielen Bits zur Verfügung stehen.
Abkürzung adiabatischer Quantencomputer?
Dass bisher von "weniger als 20 Qubits" die Rede war, scheint von einem Unternehmen widerlegt zu werden, das seine Quantencomputer auch schon an Google verkauft hat und in seinem neuen Modell auf bis zu 2.000 Qubits verweist. Doch Qubit ist nicht gleich Qubit, denn die Firma D-Wave geht mit ihrem Konzept einen etwas anderen Weg: Sie verzichtet auf die Verschränkung der einzelnen Qubits untereinander. Jedes Bit ist also vollständig unabhängig voneinander - es gibt auch abgewandelte Konzepte, bei denen immer wenige Qubits miteinander verschränkt sind, aber nicht mit dem Rest. Das vermindert die Gefahr von Dekohärenz. Forscher nennen das Grundprinzip einen adiabatischen Quantencomputer.
Es beruht darauf, dass ein System im Grundzustand (also mit der absoluten Mindestenergie) seine Quanteneigenschaften 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 herkömmlichen Computern prinzipiell überlegen sind - und bei welcher Art von Problemen -, ist derzeit noch Diskussionsgegenstand unter den Forschern. Tatsächlich scheint ein solcher Quantenrechner bestimmte Probleme (insbesondere bei der Optimierung) enorm schnell lösen zu können - wobei die meiste Zeit für die Konfiguration des Rechners auf das spezielle Problem benötigt wird.
Die ökonomischen Grenzen
Lange glaubte man, dass Quantencomputer quasi unumgänglich wären - und aus technischer Sicht stimmt das sogar. Denn die Strukturen in der klassischen Halbleitertechnik schrumpfen immer weiter und sind längst in Bereichen angekommen, wo Quanteneffekte eine große Rolle spielen. Obwohl schon lange das Ende der Miniaturisierung ausgerufen wurde, ist man seit Jahr und Tag überraschend erfolgreich darin, die Technik immer noch einen Schritt weiter zu treiben.
Was kann ein Quantencomputer? Was nicht?
Bei allen Schwierigkeiten handelt es sich um eine Technologie, die man beherrscht, in die Abermilliarden an Investitionen geflossen sind. Bis ein Quantencomputer wirklich mal auch in der Praxis leistungsfähiger als ein gleich teurer (!) klassischer Rechner ist, dürften noch einige Jahre vergehen. Deshalb leisten sich derzeit vor allem die Forschungsabteilungen großer IT-Unternehmen Quantencomputer, um daran mögliche Zukunftskonzepte zu studieren.
Die prinzipiellen Grenzen
Der Quantencomputer ist ganz sicher kein Wundermittel, das ist den Forschern heute klar. Es gibt Probleme, bei denen er theoretisch jeden klassischen Computer schlägt, etwa bei der Primzahlfaktorisierung oder Suchalgorithmen. Mathematisch lässt sich zeigen, dass der Quantencomputer schneller ist als ein klassischer Rechner bei all den Problemen, 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 AES-Protokoll lediglich die Schlüssellänge effektiv 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 eines Teilgebiets der Mathematik diskutieren, der Komplexitätstheorie. Die Frage ist: Wie lange braucht der Rechner für die Lösung - einerseits - und für das Nachprüfen der Lösung - andererseits.
P-Probleme kann auch ein normaler Computer lösen
Die einfachsten Aufgaben gehören dabei zu den P-Problemen ("Polynomialzeit"). Die 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 schon von klassischen Computern effizient lösbar, Quantencomputer werden hier nicht benötigt.
Formuliert man die Aufgabe um, erreicht man die nächsthöhere Komplexitätsstufe "nichtdeterministisch polynomial" oder "NP": Gesucht sei eine Route, mit der ein Vertreter alle 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 der Städte. Einfacher ist bei NP-Problemen die Prüfung, ob ein Lösungsvorschlag korrekt ist: Dazu ist nur Polynomialzeit nötig. Quantencomputer können einige, aber nicht alle NP-Probleme lösen. Welche genau? Das ist noch offen, genau wie die Frage, ob es nicht doch einen in Polynomialzeit funktionierenden Algorithmus für NP-Probleme gibt. Falls Sie die Antwort beweisen können, egal wie sie lautet, bringt Ihnen das eine Million Dollar Preisgeld ein. Falls Sie den Algorithmus finden, machen Sie sich all die Hersteller zum Feind, die auf Quantencomputer setzen, denn die würden dann nicht mehr gebraucht.
Denn bei Problemen noch höherer Komplexität versagen wahrscheinlich auch sie, wobei "versagen" nicht das richtige Wort ist - sie kennen dann nur keine Abkürzung zum Ziel. Dazu gehören zum Beispiel vollständige Lösungen der Spiele Schach und Go, die man in die Klasse PSPACE einordnet: Probleme, für deren Lösung man zum einen eine polynomial wachsende Speichermenge und zum anderen exponentiell wachsende Rechenzeit braucht. Bei Aufgaben dieser Stufe stoßen klassische Computer schnell an Grenzen. Wie es sich bei Quantencomputern verhält, ist unbekannt - jedenfalls hat noch niemand einen Quantenalgorithmus dafür gefunden.
Die Quanten kommen: spannende Expertenvorträge und Paneldiskussionen rund um Quantencomputer, Quantennetzwerke, Quanten - und Postquantenverschlüsselung auf der ersten eigenen Golem.de-Konferenz am 23. Juni 2017 in Berlin. Jetzt Ticket sichern!