Lösen des ‘Handlungsreisenden-Problems’ mittels Quantencomputing

Ein klassisches algorithmisches Problem im Bereich der Informatik, bekannt als das Traveling Salesman Problem (TSP), ist ein herausragendes Beispiel für ein kombinatorisches Optimierungsproblem.

Was genau ist das TSP? Dieses mathematische Klassiker beinhaltet das Finden der kürzesten möglichen Route, um N Städte genau einmal zu besuchen, bevor man zur Ausgangsstadt zurückkehrt. Allerdings steigt mit der Anzahl der Städte auch die Zahl der möglichen Routen und die Rechenzeit, um die optimale Lösung zu finden. Während dieses Problem mit Approximationsmethoden gelöst werden kann, könnten Quantencomputer deutlich bessere und wesentlich schnellere Lösungen liefern. 

Genau das hat das Team des theoretischen Physikers Prof. Dr. Jens Eisert demonstriert: Solche Probleme können mit Quantencomputern besser und schneller gelöst werden.

Quantencomputing nutzt Hardware und Algorithmen, die die Quantenmechanik ausnutzen, um komplexe Probleme zu lösen, die für konventionelle Systeme, einschließlich Supercomputer, unerreichbar sind. Trotz ihrer Leistungsfähigkeit sind Supercomputer – massive klassische Rechner mit Tausenden von CPU‑ und GPU‑Kernen – bei der Lösung hochkomplexer Probleme durch ihre Abhängigkeit von der Transistortechnologie des 20. Jahrhunderts begrenzt. 

Hier kommt die Quantenphysik ins Spiel. Im Gegensatz zu klassischen Computern, die Informationen in binären Bits (0 und 1) codieren, verwenden Quantencomputer Quantenbits oder Qubits, um mehrdimensionale Quantenalgorithmen auszuführen. 

Zudem benötigen Quantencomputer im Gegensatz zu herkömmlichen Computern, die Lüfter zur Kühlung einsetzen, ihre Quantenprozessoren bei extrem niedrigen Temperaturen, um ihre Quantenzustände zu erhalten. Dies wird durch stark gekühlte Supraleiter erreicht. 

Supraleiter sind Materialien, die einen kritischen quantenmechanischen Effekt zeigen, der es Elektronen ermöglicht, ohne Widerstand hindurchzuwandern. Beim Durchgang paaren sich die Elektronen, um eine Ladung über Barrieren zu transportieren. Werden zwei Supraleiter auf gegenüberliegenden Seiten eines Isolators platziert, entsteht eine Josephson‑Klemme, die zur Steuerung supraleitender Qubits verwendet wird.  

Ein Qubit ist für die wichtige Aufgabe nützlich, seine Quanteninformation in einen Zustand der Superposition zu bringen, also eine Kombination der möglichen Qubit‑Konfigurationen. Gruppen von Qubits in Superposition können komplexe, mehrdimensionale Rechenräume erzeugen, in denen komplexe Probleme dargestellt werden können.

Durch die Verschränkung zweier Qubits können Änderungen an einem Qubit das andere direkt beeinflussen, und wenn diese verschränkten Qubits in einen Superpositionszustand gebracht werden, entstehen zahlreiche Wahrscheinlichkeiten. Die Berechnung auf einem Quantencomputer erfolgt, indem eine Superposition aller möglichen Rechenzustände vorbereitet wird und durch Interferenz Lösungen gefunden werden.

Natürlich ist der Bau eines Quantencomputers mit vielen Qubits ein sehr komplexer Vorgang, wobei jedoch verschiedene Methoden untersucht werden, was solche Rechner leisten können. 

Laut Eisert, der eine gemeinsame Forschungsgruppe am Helmholtz‑Zentrum Berlin (HZB), einem Forschungszentrum für Energiematerialien, und an der öffentlichen Forschungsuniversität Freie Universität Berlin leitet:

“Es gibt viele Mythen darüber und manchmal eine gewisse Menge an Aufhebens und Hype. Wir haben das Thema jedoch rigoros mit mathematischen Methoden angegangen und solide Ergebnisse erzielt. Vor allem haben wir geklärt, in welchem Sinne überhaupt Vorteile bestehen können.” 

Das kritische Handlungsreisenden-Problem

Als Optimierungsproblem hat das TSP große wirtschaftliche Bedeutung in der Logistik- und Lieferkettenbranche. Es gehört zur breiteren Kategorie der kombinatorischen Optimierungsprobleme, zu denen auch Job‑Scheduling, Ressourcenallokation, Portfolio‑Optimierung und sogar Proteinfaltung gehören, die alle für verschiedene Sektoren entscheidend sind.

Angesichts der sozialen und wirtschaftlichen Bedeutung dieser Probleme wurden sie intensiv erforscht. Daher hat die Lösung von Aufgaben wie der effizientesten Lieferkette und der günstigsten Lieferroute positive Auswirkungen auf unser tägliches Leben.

Allerdings wird die Optimierung von Lieferwegen für mehrere Ziele unter Berücksichtigung verschiedener Einschränkungen wie Verkehrsstaus, steigender Betriebskosten, plötzlicher Routenänderungen, Last‑Minute‑Geschäftstermine und Kundenwünsche das TSP noch schwieriger zu lösen. Trotz dieser Herausforderungen ist die Lösung des TSP entscheidend für die effiziente Zustellung von Waren, was ein tragfähiges Geschäftsmodell sicherstellt.

Es gibt zahlreiche Vorteile, das Problem zu lösen, darunter die Reduzierung von zurückgelegter Strecke und Fahrzeit sowie Kraftstoffeinsparungen. Die Minimierung der zurückgelegten Distanz kann den CO₂‑Fußabdruck erheblich senken, was zu besserer Luftqualität, verlangsamtem Klimawandel und Wirtschaftswachstum führt. Darüber hinaus kann die Lösung des TSP die pünktliche Lieferung von Waren und rechtzeitige Kundentermine unterstützen, was die Kundenerfahrung und den Außendienst verbessert.

Wie wir gesehen haben, hilft die Lösung des Problems nicht nur Unternehmen, sondern diese Vorteile wirken sich auch auf die Kunden aus und bereichern das Erlebnis aller Beteiligten.

Mehrere Methoden können zur Lösung des TSP eingesetzt werden. Eine davon ist der ‘Brute‑Force’-Ansatz, der alle möglichen Permutationen berechnet, um die kürzeste Route zu finden. Beim Branch‑and‑Bound‑Verfahren wird das Problem in mehrere Teilprobleme zerlegt, wobei die Lösung jeder Stufe die Lösung der nachfolgenden Stufen beeinflusst.

Im dynamischen Programmieren liegt der Fokus darauf, redundante Berechnungen zu vermeiden. Der Nearest‑Neighbor‑Algorithmus ist ein Approximationsverfahren, bei dem man vom Startort ausgehend stets die nächstgelegene Stadt wählt. Sobald alle Städte besucht wurden, kehrt man zum Ausgangspunkt zurück. Obwohl praktisch und relativ schnell, liefert diese Methode nicht immer die effizienteste Route.

Mit fortschreitender Technologie kann die Routenplanung und -optimierung deutlich effektiver durchgeführt werden. Künstliche Intelligenz (KI) kann insbesondere helfen, das Problem zu lösen, indem sie große Datenmengen schnell analysiert und modernen Unternehmen bei operativen und strategischen Entscheidungen unterstützt.

Quantencomputer werden ebenfalls untersucht, um das Problem zu lösen; schließlich bieten sie erhebliche Rechenbeschleunigungen gegenüber klassischen Computern. Es wurde lange vermutet, dass diese Rechner die Approximationen solcher Probleme tatsächlich verbessern können.

Quantencomputing‑Techniken zur Lösung des TSP einsetzen

Während Quantencomputing enormes Interesse weckt und vielversprechende Ergebnisse für bestimmte Probleme liefert, bleibt das Ausmaß dieses quantenmechanischen Vorteils weitgehend unerforscht. 

Daher lieferte die Studie einen vollständigen konstruktiven Beweis dafür, dass Quantencomputer herkömmliche Rechner bei der Approximation kombinatorischer Optimierungsprobleme tatsächlich übertreffen können.

Die neueste Studie, geleitet von Eisert und seinem Kollegen Jean‑Pierre Seifert, nutzte ausschließlich analytische Methoden, um zu bewerten, wie ein Quantencomputer mit Qubits das TSP-Problem lösen kann. 

“Wir gehen einfach davon aus, unabhängig von der physischen Realisierung, dass genügend Qubits vorhanden sind und betrachten die Möglichkeiten, Rechenoperationen mit ihnen durchzuführen,” was einer ähnlichen Fragestellung in der Kryptographie, nämlich der Verschlüsselung von Daten, entspricht, erklärte Vincent Ulitzsch, Doktorand an der Technischen Universität Berlin. 

Dann nutzte das Team den Shor‑Algorithmus, einen Quantenalgorithmus, um die Primfaktoren einer ganzen Zahl zu finden und eine Unterklasse dieser Optimierungsprobleme zu lösen. Damit steigt die Rechenzeit nicht mehr exponentiell mit der Anzahl der Städte, sondern nur noch polynomial, d. h. mit N^x, wobei x eine Konstante ist. Auf diese Weise ist die erhaltene Lösung qualitativ deutlich besser als die aus der approximativen Lösung des herkömmlichen Algorithmus.

Durch die Anwendung kryptografischer Konzepte und der Theorie des computergestützten Lernens liefert die Studie einen “vollständig konstruktiven Beweis”, dass Quantencomputer einen super‑polynomiellen Vorteil gegenüber klassischen Computern bei der Approximation kombinatorischer Optimierungsprobleme besitzen. 

Die Studie stellte zudem fest, dass das Forschungsteam bedeutende Fortschritte bei der wichtigen Frage gemacht hat, welches Potenzial Quantencomputer bei der Approximation von Lösungen kombinatorischer Optimierungsprobleme bieten könnten, die erhebliche soziale und wirtschaftliche Auswirkungen haben.

Die Studie wurde finanziert von der Einstein Research Unit, dem Berlin Mathematics Research Center (MATH+ Cluster of Excellence), dem BMBF (Hybrid), dem BMWK (EniQmA), dem Munich Quantum Valley und der DFG. Das Bundesministerium für Bildung und Forschung (BMBF) stellte ebenfalls finanzielle Unterstützung bereit.

Das Potenzial des Quantencomputings erforschen 

Obwohl es ein großer Erfolg ist, war dies nicht das erste Mal, dass Quantencomputing zur Lösung des Handlungsreisenden-Problems eingesetzt wurde. Es gab zahlreiche Fälle von Enthusiasten und Forschern, die das Problem mithilfe von Quantencomputing zu lösen versuchten. 

Im Dezember 2022 schlug ein Paper einen Quantenalgorithmus für das TSP vor, basierend auf der Grover Adaptive Search (GAS). Im Rahmen von GAS gibt es mindestens zwei grundlegende Schwierigkeiten – Lösungen können unpraktisch sein, und die Anzahl der Qubits aktueller Quantencomputer ist stark begrenzt und kann die Mindestanforderungen nicht erfüllen, was die Anwendung von Quantenalgorithmen für kombinatorische Optimierungsprobleme einschränkt.

Daher verfeinerte das Paper das Hamiltonian Cycle Detection (HCD)-Oracle, das während der Algorithmusausführung automatisch unpraktische Lösungen entfernen kann. Sie entwickelten zudem eine “Anchor‑Register”-Strategie, um den Qubit‑Verbrauch zu sparen, wobei die Umkehrbarkeit des Quantencomputings vollständig berücksichtigt und das Problem überwunden wurde, dass genutzte Qubits nicht einfach überschrieben oder freigegeben werden können. Dadurch konnte die Studie nur 31 Qubits benötigen, und die Lösung erreichte eine Erfolgsquote von 86,71 %.

Im Jahr 2019 schrieb der selbsternannte Physik‑Kenner Joseph Cammidge über die Nutzung eines annealing‑Quantenprozessors, der es ihm ermöglichte, das Handlungsreisenden‑Problem für sieben Städte zu lösen und theoretisch das Potenzial hat, für neun Städte zu funktionieren, sobald technologische Beschränkungen beseitigt sind.

Eine neue Rechenmethode, das Quantum Annealing, hat das Potenzial gezeigt, Optimierungsprobleme schneller zu lösen als klassische Techniken. Ihre Theorie impliziert, dass die Qubits bei starker Kühlung einen optimalen Niedrigenergie‑Zustand erreichen.

Allerdings zeigte eine Studie aus dem Jahr 2021, finanziert von Supply Chain Digital & Data Science, Johnson & Johnson, dass der Quantum‑Annealer nur Problemgrößen von acht oder weniger Knoten bewältigen kann und sowohl in Bezug auf Zeit als auch Genauigkeit gegenüber klassischen Lösungsansätzen unterdurchschnittlich abschneidet.

Der Einsatz von Quantencomputing zur Lösung des TSP-Problems besteht bereits seit einiger Zeit. Vor über zwei Jahrzehnten, im Jahr 2001, begann eine Studie nach einem Quantenalgorithmus zur Lösung des Problems zu suchen.

In dem Paper untersuchte Buckley Hopper von der University of Alabama die Quantencomputer‑Algorithmen von Grover und Shor. Er stellte fest, dass Grovers Algorithmus nur eine Quadratwurzel‑Verbesserung liefert, was impliziert, dass er ein klassisch unlösbares Problem nicht auf einem Quantencomputer lösbar macht. Hinsichtlich Shors Algorithmus bemerkte Hopper, dass er zwar ein vermutlich unlösbares Primfaktor‑Problem in ein lösbares auf der Quantenmaschine verwandeln kann, jedoch nur für einen sehr spezifischen Problemtyp geeignet ist.

Insgesamt “fand Hopper kein zufriedenstellendes Ergebnis für einen Algorithmus zur Berechnung approximativer Lösungen des Handlungsreisenden‑Problems”.

Einige Jahre später präsentierte das Institute of Electrical and Electronics Engineers (IEEE) einen neuen Algorithmus zur Lösung des Problems, inspiriert von genetischen Algorithmen und Quantencomputing. Das IEEE stellte fest, dass die Ergebnisse der Anwendung des vorgeschlagenen Algorithmus auf einigen Instanzen des Traveling Salesman Problem deutlich besser sind als die von Standard‑Genetischen Algorithmen.

Klicken Sie hier, um mehr über den aktuellen Stand des Quantencomputings zu erfahren.

Unternehmen, die mit Quantencomputing arbeiten 

Werfen wir nun einen Blick auf einige Namen, die an Forschung und Entwicklung im Bereich Quantencomputing arbeiten:

#1. IBM

Die International Business Machines Corporation ist in einer Vielzahl von Bereichen tätig, darunter KI, Cloud‑Dienste, IT, Kundenfinanzierung und Unternehmensfinanzierung. Der Technologieriese ist zudem im Quantencomputing aktiv über seine IBM Quantum Platform, die öffentlichen und Premium‑Zugang zu cloudbasierten Quantencomputing‑Diensten bietet. Diese umfassen eine Reihe von IBM‑Prototyp‑Quantenprozessoren, Tutorials zur Quantenberechnung und ein interaktives Lehrbuch.

Kürzlich erklärten IBM‑Wissenschaftler dass sie einen weiteren Schritt näher daran seien, ein Hindernis zu überwinden, das das spielverändernde Potenzial von Quantencomputern freischaltet. Dafür stellten sie einen neuen Quanten‑Fehlerkorrekturcode vor, der ihrer Aussage nach etwa zehnmal effizienter sei als frühere Methoden. 

Ende letzten Jahres brachte das Unternehmen zudem den Quantencomputer namens Condor auf den Markt, mit 1.121 supraleitenden Qubits, die in einem Wabenmuster angeordnet sind. IBM stellte außerdem das IBM Quantum System Two vor, seinen ersten modularen Quantencomputer und die quantum‑zentrierte Supercomputing‑Architektur, die skalierbar ist und daher in den nächsten fünf Jahren mit neuen Chips aufgerüstet werden kann.

Mit einer Marktkapitalisierung von 175 Milliarden $ notieren IBM‑Aktien bei 190,86 $, ein Anstieg von 16,66 % seit Jahresbeginn (YTD). IBM verzeichnete einen Umsatz (TTM) von 61,86 Milliarden $, ein EPS (TTM) von 8,03, ein KGV (TTM) von 23,76 und eine Eigenkapitalrendite (ROE) (TTM) von 33,36 %. Das Unternehmen zahlt eine Dividendenrendite von 3,48 %.

#2. D-Wave Systems

Dieses Quantencomputing‑Unternehmen entwickelt und liefert zugehörige Systeme, Software und Dienstleistungen. Zu seinen Produkten gehören The Leap und The Advantage, und es bietet Quantenanwendungen für Terminplanung, Logistik, Wirkstoffforschung, Fertigungsprozesse und mehr. 

Anfang dieses Monats erklärte D‑Wave, dass Quantenmaschinen nun Probleme mit realen Anwendungen schneller lösen können als jeder herkömmliche Computer. Zu Beginn dieses Jahres kündigte das Unternehmen einen Quantencomputer mit 1.200 Qubits, 10.000 Kopplern und einer 20‑fach schnelleren Lösungszeit bei harten Optimierungsproblemen an.

Die Aktien des Unternehmens werden derzeit bei 1,86 $ gehandelt, ein Anstieg von 138,6 % seit Jahresbeginn (YTD), bei einer Marktkapitalisierung von 267 Millionen $. Das Unternehmen meldete einen Umsatz (TTM) von 8,247 Millionen $, ein EPS (TTM) von -0,66 und ein KGV (TTM) von -3,19, und kündigte ein Wachstum von über 20 % beim Umsatz sowohl für das vierte Quartal als auch für das Jahresende 2023 an, während die Auftragslage um 34 % bzw. 89 % gestiegen sei.

Interessanterweise erklärte der CEO des Unternehmens, Dr. Alan Baratz, dass das Unternehmen an Schwung gewinne, wobei er die mehrjährige strategische Partnerschaft mit Zapata AI, die Einführung des 1.200‑plus‑Qubit‑Advantage2‑Prototyps, Joint‑Ventures mit NEC Australia und Deloitte Canada sowie die Ernennung der ehemaligen US‑Ministerin für Heimatschutz Kirstjen Nielsen in den Vorstand nannte.

Fazit

Der Markt für Quantencomputing wird voraussichtlich bis 2028 6,5 Milliarden $ erreichen, und sein Potenzial, das Traveling Salesman Problem (TSP) zu lösen, hat Auswirkungen auf zahlreiche Branchen, wie Fertigung, Logistik, Lieferkettenmanagement, E‑Commerce, Transport und Forschung. Schließlich kann es zu erheblichen Vorteilen führen, insbesondere die Produktivität steigern, Kosten senken und Innovationen in verschiedenen Sektoren ankurbeln.

Klicken Sie hier für die Liste der besten fünf Quantencomputing‑Unternehmen.