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

  • Sauberer Brennstoff zum Kochen für das südliche Afrika hat große Wirkung
    Nachricht
    19.04.2024
    Sauberer Brennstoff zum Kochen für das südliche Afrika hat große Wirkung
    Das Verbrennen von Biomasse beim Kochen belastet Gesundheit und Umwelt. Die deutsch-südafrikanische Initiative GreenQUEST entwickelt einen sauberen Haushaltsbrennstoff. Er soll klimaschädliche CO2-Emissionen reduzieren und den Zugang zu Energie für Haushalte in afrikanischen Ländern südlich der Sahara verbessern.

  • Einfachere Herstellung von anorganischen Perowskit-Solarzellen bringt Vorteile
    Science Highlight
    17.04.2024
    Einfachere Herstellung von anorganischen Perowskit-Solarzellen bringt Vorteile
    Anorganische Perowskit-Solarzellen aus CsPbI3 sind langzeitstabil und erreichen gute Wirkungsgrade. Ein Team um Prof. Antonio Abate hat nun an BESSY II Oberflächen und Grenzflächen von CsPbI3 -Schichten analysiert, die unter unterschiedlichen Bedingungen produziert wurden. Die Ergebnisse belegen, dass das Ausglühen in Umgebungsluft die optoelektronischen Eigenschaften des Halbleiterfilms nicht negativ beeinflusst, sondern sogar zu weniger Defekten führt. Dies könnte die Massenanfertigung von anorganischen Perowskit-Solarzellen weiter vereinfachen.
  • Spintronik: Ein neuer Weg zu wirbelnden Spin-Texturen bei Raumtemperatur
    Science Highlight
    16.04.2024
    Spintronik: Ein neuer Weg zu wirbelnden Spin-Texturen bei Raumtemperatur
    Ein Team am HZB hat an BESSY II eine neue, einfache Methode untersucht, mit der sich stabile radiale magnetische Wirbel in magnetischen Dünnschichten erzeugen lassen.