Wo Quantencomputer wirklich punkten können

Das Problem des Handlungsreisenden ist ein Klassiker in der Mathematik. Ein Reisender soll auf dem kürzesten Weg N Städte besuchen und wieder zum Ausgangspunkt zurückkehren. Mit steigender Anzahl N explodiert die Anzahl der möglichen Routen. Dieses Problem ist dann mit Näherungsverfahren lösbar. Quantenrechner könnten hier rascher deutlich bessere Lösungen liefern.

Das Problem des Handlungsreisenden ist ein Klassiker in der Mathematik. Ein Reisender soll auf dem kürzesten Weg N Städte besuchen und wieder zum Ausgangspunkt zurückkehren. Mit steigender Anzahl N explodiert die Anzahl der möglichen Routen. Dieses Problem ist dann mit Näherungsverfahren lösbar. Quantenrechner könnten hier rascher deutlich bessere Lösungen liefern. © HZB

Die vorliegende Arbeit (Pfeil) zeigt, dass ein bestimmter Teil der kombinatorischen Probleme mit Quantencomputern sehr viel besser l&ouml;sbar ist, m&ouml;glicherweise sogar exakt.</p>
<p>

Die vorliegende Arbeit (Pfeil) zeigt, dass ein bestimmter Teil der kombinatorischen Probleme mit Quantencomputern sehr viel besser lösbar ist, möglicherweise sogar exakt.

© HZB

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, 2N), sondern steigt nur noch polynomial, also mit Nx, 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.

arö


Das könnte Sie auch interessieren

  • BESSY II: Wie das gepulste Laden die Lebensdauer von Batterien verlängert
    Science Highlight
    08.04.2024
    BESSY II: Wie das gepulste Laden die Lebensdauer von Batterien verlängert
    Ein verbessertes Ladeprotokoll könnte die Lebensdauer von Lithium-Ionen-Batterien deutlich verlängern. Das Laden mit hochfrequentem gepulstem Strom verringert Alterungseffekte. Dies zeigte ein internationales Team unter der Leitung von Philipp Adelhelm (HZB und Humboldt-Universität) in Zusammenarbeit mit der Technischen Universität Berlin und der Aalborg University in Dänemark. Besonders aufschlussreich waren Experimente an der Röntgenquelle BESSY II.
  • Brennstoffzellen: Oxidationsprozesse von Phosphorsäure aufgeklärt
    Science Highlight
    03.04.2024
    Brennstoffzellen: Oxidationsprozesse von Phosphorsäure aufgeklärt
    Die Wechselwirkungen zwischen Phosporsäure und dem Platin-Katalysator in Hochtemperatur-PEM-Brennstoffzellen sind komplexer als bisher angenommen. Röntgen-Experimente an BESSY II in einem mittleren Energiebereich (tender x-rays) haben die vielfältigen Oxidationsprozesse an der Platin-Elektrolyt-Grenzfläche entschlüsselt. Die Ergebnisse zeigen auch, dass die Feuchtigkeit in der Brennstoffzelle diese Prozesse beeinflusst, so dass sich hier Möglichkeiten bieten, um Lebensdauer und Wirkungsgrad von Brennstoffzellen zu erhöhen. 
  • Neutronenexperiment am BER II deckt neue Spin-Phase in Quantenmaterial auf
    Science Highlight
    18.03.2024
    Neutronenexperiment am BER II deckt neue Spin-Phase in Quantenmaterial auf
    In quantenmagnetischen Materialien unter Magnetfeldern können neue Ordnungszustände entstehen. Nun hat ein internationales Team aus Experimenten an der Berliner Neutronenquelle BER II und am dort aufgebauten Hochfeldmagneten neue Einblicke in diese besonderen Materiezustände gewonnen. Der BER II wurde bis Ende 2019 intensiv für die Forschung genutzt und ist seitdem abgeschaltet. Noch immer werden neue Ergebnisse aus Messdaten am BER II publiziert.