Wo Quantencomputer wirklich punkten können

Das Problem des Handlungsreisenden gilt als Paradebeispiel für kombinatorische Optimierungsprobleme. Nun zeigt ein Berliner Team um den theoretischen Physiker Prof. Dr. Jens Eisert der Freien Universität Berlin, dass eine bestimmte Klasse solcher Probleme tatsächlich durch Quantencomputer besser und sehr viel schneller gelöst werden kann als mit konventionellen Methoden.

Quantencomputer rechnen mit so genannten Qbits, die nicht wie bei konventionellen logischen Schaltungen entweder Null oder Eins betragen, sondern in einem präzisen Sinne alle Werte dazwischen annehmen. Diese Qbits werden durch stark heruntergekühlte Atome, Ionen oder supraleitende Schaltkreise realisiert, und es ist physikalisch noch sehr aufwändig, einen Quantencomputer mit vielen Qbits zu bauen. Doch mit mathematischen Methoden lässt sich schon jetzt erforschen, was fehlertolerante Quantencomputer künftig leisten könnten. „Darüber gibt es viele Mythen, und zuweilen auch zu einem Grade heiße Luft und Hype. Aber wir haben uns der Frage einmal mit mathematischen Methoden rigoros gestellt und solide Ergebnisse zum Thema geliefert. Vor allem haben wir geklärt, in welchem Sinne es überhaupt Vorteile geben kann“, sagt Prof. Dr. Jens Eisert, der eine gemeinsame Forschungsgruppe an der Freien Universität Berlin und am Helmholtz-Zentrum Berlin leitet.

Als Paradebeispiel dient das bekannte Problem des Handlungsreisenden: Ein Reisender soll eine Anzahl von Städten besuchen und im Anschluss wieder in die Heimatstadt zurückkehren. Wie sieht die kürzeste Route aus? Dieses Problem ist zwar leicht verständlich, aber wird mit steigender Anzahl von Städten immer komplexer, die Rechenzeit explodiert. Das Problem des Handlungsreisenden steht für eine Gruppe von Optimierungsproblemen, die enorme wirtschaftliche Bedeutung haben, ob es um Schienennetze, Logistik oder um die Optimierung von Ressourcen geht. Mit Näherungsverfahren lassen sich gute approximative Lösungen finden.

Das Team um Jens Eisert und seinen Kollegen Jean-Pierre Seifert arbeitete nun rein analytisch, um zu evaluieren, wie ein Quantencomputer mit Qbits diese Klasse von Problemen lösen könnte. Ein klassisches Gedankenexperiment mit Stift und Papier und einer Menge Fachwissen. „Wir nehmen einfach an, unabhängig von der physikalischen Realisierung, dass es ausreichend Qbits gibt und betrachten die Möglichkeiten, damit Rechenoperationen durchzuführen“, erklärt Vincent Ulitzsch, Doktorand an der Technischen Universität Berlin. Dabei erkannten sie Ähnlichkeiten zu einem bekannten Problem der Kryptographie, also der Verschlüsselung von Daten. „Wir stellten dann fest, dass wir eine Unterklasse dieser Optimierungsprobleme mit dem Shor-Algorithmus behandeln können,“ sagt Ulitzsch. Damit „explodiert“ die Rechenzeit nicht mehr mit der Anzahl der Städte (exponentiell, 2^N), sondern steigt nur noch polynomial, also mit N^x, wobei x eine Konstante ist. Die so errechnete Lösung ist außerdem qualitativ deutlich besser als die Näherungslösung mit dem konventionellen Algorithmus.

„Wir haben gezeigt, dass Quantencomputer für bestimmte Instanzen des Problems prinzipiell einen Vorteil gegenüber klassischen Computern aufweisen, wenn es um eine bestimmte, aber sehr wichtige und praktisch relevante Klasse kombinatorischer Optimierungsprobleme geht“, sagt Eisert.