Lösung des ‘Traveling Salesman Problems’ durch Quantencomputing

Ein klassisches algorithmisches Problem auf dem Gebiet der Informatik, bekannt als das Traveling Salesman Problem (TSP), ist ein prominentes Beispiel für ein kombinatorisches Optimierungsproblem.

Was genau ist TSP? Dieses mathematische Klassiker beinhaltet die Suche nach der kürzesten möglichen Route, um N-Städte genau einmal zu besuchen, bevor man zur Ausgangsstadt zurückkehrt. Allerdings erhöht sich mit der Anzahl der Städte auch die Anzahl der möglichen Routen und die Rechenzeit, um die optimale Lösung zu finden. Obwohl dieses Problem mit Approximationsmethoden gelöst werden kann, könnten Quantencomputer wesentlich bessere Lösungen liefern und das auch noch viel schneller. 

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

Quantencomputing nutzt Hardware und Algorithmen, die die Quantenmechanik ausnutzen, um komplexe Probleme zu lösen, die für herkömmliche Computer, einschließlich Supercomputer, unerreichbar sind. Trotz ihrer Leistungsfähigkeit sind Supercomputer, also massive klassische Computer mit Tausenden von CPU- und GPU-Kernen, durch ihre Abhängigkeit von der Transistortechnologie des 20. Jahrhunderts bei der Lösung von Problemen mit hohem Komplexitätsgrad eingeschränkt. 

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

Darüber hinaus benötigen Quantencomputer im Gegensatz zu herkömmlichen Computern, die Lüfter für die Kühlung verwenden, dass ihre Quantenprozessoren bei extrem niedrigen Temperaturen gehalten werden, um ihre Quantenzustände beizubehalten. Dies wird durch supraleitende Supraflüssigkeiten erreicht. 

Supraleiter sind Materialien, die einen kritischen quantenmechanischen Effekt aufweisen, der es Elektronen ermöglicht, ohne Widerstand durch sie zu fließen. Wenn Elektronen durch sie fließen, paaren sie sich, um eine Ladung über Barrieren zu tragen. Wenn zwei Supraleiter auf beiden Seiten eines Isolators platziert werden, entsteht eine Josephson-Verbindung, die zur Leitung von supraleitenden Qubits verwendet wird.  

Ein Qubit ist nützlich bei der wichtigen Aufgabe, seine Quanteninformation in einen Zustand der Überlagerung zu bringen, einer Kombination der möglichen Konfigurationen des Qubits. Gruppen von Qubits in Überlagerung sind in der Lage, komplexe, multidimensionale Rechenräume zu erstellen, in denen komplexe Probleme dargestellt werden können.

Hier kann durch die Verschränkung von zwei Qubits eine Änderung des einen direkt auf das andere wirken, und wenn diese verschränkten Qubits in einen Zustand der Überlagerung gebracht werden, erhalten wir viele Wahrscheinlichkeiten. Die Rechnung auf einem Quantencomputer funktioniert, indem eine Überlagerung aller möglichen Rechenzustände vorbereitet wird, und durch Interferenz werden Lösungen gefunden.

Natürlich ist der Bau eines Quantencomputers mit vielen Qubits ein sehr komplexes Verfahren, obwohl mehrere Methoden erforscht werden, um zu sehen, was solche Computer leisten können. 

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

“Es gibt viele Mythen darüber, und manchmal ein gewisses Maß an heißen Luft und Hype. Wir haben das Problem jedoch rigoros angegangen, indem wir mathematische Methoden verwendet und solide Ergebnisse zum Thema geliefert haben. Vor allem haben wir geklärt, in welchem Sinne es überhaupt Vorteile geben kann.” 

Das kritische Traveling Salesman Problem

Ein Optimierungsproblem, TSP ist von großer wirtschaftlicher Bedeutung in der Logistik- und Supply-Chain-Industrie. Es fällt in die breitere Kategorie der kombinatorischen Optimierungsprobleme, zu denen auch die Jobscheduling, Ressourcenzuweisung, Portfolio-Optimierung und sogar die Proteinfaltung gehören, die alle für verschiedene Sektoren von entscheidender Bedeutung sind.

Angesichts der sozialen und wirtschaftlichen Bedeutung dieser Probleme wurden sie Gegenstand intensiver Forschung. Als solche hat die Suche nach Antworten auf Probleme wie der effizientesten Supply-Chain und der günstigsten Lieferstrecke einen positiven Einfluss auf unser tägliches Leben.

Allerdings macht die Optimierung der Lieferstrecken für mehrere Ziele unter Berücksichtigung verschiedener Einschränkungen wie Verkehrsstaus, steigende Betriebskosten, plötzliche Routenänderungen, kurzfristige Geschäftstermine und Kundenanfragen das TSP noch herausfordernder. Trotz dieser Herausforderungen ist die Lösung des TSP für die effiziente Lieferung von Waren von entscheidender Bedeutung, um ein tragfähiges Geschäftsmodell zu gewährleisten. 

Es gibt viele Vorteile bei der Lösung dieses Problems, einschließlich der Reduzierung der zurückgelegten Strecke und der Reisezeit sowie der Einsparung von Treibstoffverbrauch. Die Minimierung der zurückgelegten Strecke kann dazu beitragen, den CO2-Fußabdruck erheblich zu reduzieren, was zu besserer Luftqualität, verlangsamtem Klimawandel und wirtschaftlichem Wachstum führt. Darüber hinaus kann die Lösung des TSP dazu beitragen, die pünktliche Lieferung von Waren und die rechtzeitige Einhaltung von Terminen mit Kunden zu gewährleisten, was die Kundenerfahrung und die Feldservice-Unternehmen verbessert.

Wie wir gesehen haben, hilft die Lösung des Problems nicht nur Unternehmen, sondern diese Vorteile kommen auch den Kunden zugute, was die Erfahrung für alle Beteiligten bereichert.

Es gibt mehrere Methoden, um das TSP-Problem zu lösen. Eine solche Methode ist der “Brute-Force”-Ansatz, der alle möglichen Permutationen berechnet, um die kürzeste Route zu finden. Bei der Methode der verzweigten und beschränkten Suche wird das Problem in mehrere Reihen von Teilproblemen unterteilt, wobei die Lösung jeder Phase die Lösung in den folgenden Phasen beeinflusst.

Bei der dynamischen Programmierung liegt der Schwerpunkt auf der Vermeidung redundanter Berechnungen. Der nächste Nachbar ist dagegen ein Approximationsalgorithmus, bei dem man mit dem Startort beginnt und dann am nächsten Halt anhält. Sobald alle Städte abgedeckt sind, kehrt man zum Startpunkt zurück. Obwohl diese Methode praktisch und relativ schnell ist, liefert sie nicht immer die effizienteste Route.

Mit dem Fortschritt der Technologie kann die Routenplanung und -optimierung noch effektiver durchgeführt werden. Künstliche Intelligenz (KI) kann insbesondere auch dazu beitragen, das Problem zu lösen, indem sie eine enorme Menge an Daten schnell analysiert, um vielen modernen Unternehmen bei operativen und strategischen Entscheidungen zu helfen.

Quantencomputer werden auch untersucht, um das Problem zu lösen; schließlich bieten sie erhebliche Rechengeschwindigkeitssteigerungen gegenüber herkömmlichen Computern. Es wurde bereits lange vermutet, dass diese Computer möglicherweise dazu beitragen können, Approximationen zu diesen Problemen zu verbessern. 

Verwendung von Quantencomputing-Techniken zur Lösung des TSP

Während das Quantencomputing enormes Interesse auf sich zieht und vielversprechende Ergebnisse für bestimmte Probleme liefert, bleibt der Umfang dieses Quantenvorteils weitgehend unerforscht. 

Daher lieferte die Studie den vollständigen konstruktiven Beweis, dass Quantencomputer tatsächlich herkömmliche Computer bei der Suche nach Approximationen für kombinatorische Optimierungsprobleme übertreffen können.

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

“Wir nehmen einfach an, unabhängig von der physikalischen Realisierung, dass es genügend Qubits gibt und betrachten die Möglichkeiten, Rechenoperationen mit ihnen durchzuführen”, was einer Ähnlichkeit mit einem häufigen Problem in der Kryptographie entspricht, nämlich der Verschlüsselung von Daten, erklärte Vincent Ulitzsch, ein Promotionsstudent an der Technischen Universität Berlin. 

Dann verwendete das Team den Shor-Algorithmus, einen Quantenalgorithmus, um die Primfaktoren einer Ganzzahl zu finden und eine Teilklasse dieser Optimierungsprobleme zu lösen. Mit diesem Ansatz explodiert die Rechenzeit nicht mehr, wenn die Anzahl der Städte zunimmt. Sie erhöht sich nur polynomial, d. h. mit Nx, wobei x eine Konstante ist. Auf diese Weise ist die erhaltene Lösung auch qualitativ viel besser als die, die aus der Approximationslösung mit dem herkömmlichen Algorithmus abgeleitet wird.

Durch die Verwendung kryptographischer Konzepte und der Theorie des maschinellen Lernens liefert die Studie den “vollständigen konstruktiven Beweis, dass Quantencomputer einen superpolynomialen Vorteil gegenüber klassischen Computern bei der Approximation kombinatorischer Optimierungsprobleme aufweisen”. 

Die Studie stellte weiter fest, dass das Forschungsteam wesentliche Fortschritte bei der wichtigen Frage erzielt hat, was Quantencomputer möglicherweise für die Approximation der Lösung kombinatorischer Optimierungsprobleme bieten können, die erhebliche soziale und wirtschaftliche Auswirkungen haben.

Die Studie wurde 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 finanziert. Das Bundesministerium für Bildung und Forschung Deutschlands gewährte ebenfalls finanzielle Unterstützung.

Erforschung des Potenzials von Quantencomputing 

Während dies eine großartige Leistung war, war dies nicht das erste Mal, dass Quantencomputing zur Lösung des Traveling Salesman Problems eingesetzt wurde. Es gab viele Fälle von Enthusiasten und Forschern, die sich mit der Lösung des Problems durch Quantencomputing beschäftigt haben. 

Im Dezember 2022 schlug ein Artikel einen Quantenalgorithmus für das TSP auf der Grundlage der Grover-Adaptive-Suche (GAS) vor. Im Rahmen des GAS-Rahmens gibt es mindestens zwei grundlegende Schwierigkeiten – Lösungen können nicht machbar sein, und die Anzahl der Qubits der aktuellen Quantencomputer ist sehr begrenzt und kann die Mindestanforderungen nicht erfüllen, was die Anwendung von Quantenalgorithmen für kombinatorische Optimierungsprobleme einschränkt. 

Daher hat der Artikel den Hamiltonian-Zyklus-Erkennungs-Oracle (HCD) poliert, der unmögliche Lösungen während der Algorithmusausführung automatisch entfernen kann. Sie haben auch eine “Anker-Register”-Strategie entwickelt, um den Qubit-Verbrauch zu sparen, wobei die Umkehrbarkeitserfordernis des Quantencomputings vollständig berücksichtigt und die Schwierigkeit überwunden wird, dass die verwendeten Qubits nicht einfach überschrieben oder freigegeben werden können. Dies ermöglichte es der Studie, nur 31 Qubits zu benötigen, und die Lösung hatte eine Erfolgsrate von 86,71%.

Im Jahr 2019 schrieb der selbsternannte Physik-Kenner Joseph Cammidge über die Verwendung eines Annealing-Quantenprozessors, der es ihm ermöglichte, das Traveling Salesman Problem für sieben Städte zu lösen und das theoretische Potenzial hat, für neun Städte zu lösen, sobald technische Einschränkungen beseitigt sind. 

Eine neue Rechenmethode, Quantenannealing, hat das Potenzial gezeigt, Optimierungsprobleme schneller als klassische Techniken zu lösen. Die Theorie besagt, dass die Qubits einen optimalen Zustand mit niedriger Energie erreichen, wenn sie supergeschaltet werden. 

Allerdings fand eine Studie im Jahr 2021, die von Supply Chain Digital & Data Science, Johnson & Johnson finanziert wurde, dass der Quantenannealer nur ein Problem der Größe 8 oder weniger Knoten bewältigen kann und seine Leistung sowohl in Bezug auf Zeit als auch auf Genauigkeit im Vergleich zum klassischen Solver unterlegen ist.

Die Verwendung von Quantencomputing zur Lösung des TSP-Problems ist bereits seit langem im Gange. Vor über zwei Jahrzehnten, im Jahr 2001, begann eine Studie, nach einem Quantenalgorithmus zur Lösung des Problems zu suchen.

In der Arbeit untersuchte Buckley Hopper von der University of Alabama den Quantencomputer-Algorithmus von Grover und Shor. Er stellte fest, dass Grovers Algorithmus nur eine quadratische Verbesserung bietet, was bedeutet, dass er kein klassisch unlösbares Problem auf einem Quantencomputer lösbar machen kann. Was Shors Algorithmus betrifft, so beobachtete Hopper, dass er, obwohl er ein vermutlich unlösbares Primfaktorproblem in ein lösbares Problem auf dem Quantencomputer umwandeln kann, nur für ein sehr spezifisches Problem geeignet ist. 

Insgesamt fand Hopper “kein zufriedenstellendes Ergebnis für einen Algorithmus zur Berechnung von Approximationen für das Traveling Salesman Problem”.

Einige Jahre später stellte das Institute of Electrical and Electronics Engineers (IEEE) einen neuen Algorithmus für die Lösung des Problems vor, der sowohl von genetischen Algorithmen als auch von Quantencomputing inspiriert wurde. Die IEEE fand heraus, dass die Ergebnisse der Anwendung des vorgeschlagenen Algorithmus auf einige Instanzen des Traveling Salesman Problems erheblich besser sind als diejenigen, die durch Standard-Genetische Algorithmen bereitgestellt werden.

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

Unternehmen, die mit Quantencomputing arbeiten 

Lassen Sie uns nun einen Blick auf einige Namen werfen, die an der Forschung und Entwicklung von Quantencomputing arbeiten:

#1. IBM

International Business Machines Corporation ist in einer breiten Palette von Branchen tätig, darunter KI, Cloud-Dienste, IT, Kundenfinanzierung und kommerzielle Finanzierung. Der Technologiekonzern ist auch im Bereich des Quantencomputings tätig, und zwar über seine IBM Quantum Platform, die öffentlichen und premium Zugang zu ihren cloudbasierten Quantencomputing-Diensten bietet. Dazu gehören eine Reihe von IBM-Prototyp-Quantenprozessoren, Tutorials zum Quantencomputing und ein interaktives Lehrbuch.

Vor kurzem gaben IBM-Wissenschaftler bekannt, dass sie einen weiteren Schritt gemacht haben, um ein Hindernis zu überwinden, das das spielverändernde Potenzial von Quantencomputern entsperrt. Dazu führten sie einen neuen Quantenfehlerkorrekturcode ein, der ihrer Meinung nach etwa zehnmal effizienter ist als frühere Methoden. 

Ende des letzten Jahres stellte das Unternehmen auch den Quantencomputer namens Condor vor, der 1.121 supraleitende Qubits in einem hexagonalen Muster aufweist. IBM stellte auch das IBM Quantum System Two vor, sein erstes modulares Quantencomputer- und quantenorientiertes Supercomputing-Design, das skalierbar ist und daher mit Chips aufgerüstet werden kann, die in den nächsten fünf Jahren veröffentlicht werden.

Mit einem Marktwert von 175 Milliarden US-Dollar werden IBMs Aktien bei 190,86 US-Dollar gehandelt, was einem Anstieg von 16,66% seit Jahresbeginn entspricht. IBM hat einen Umsatz (TTM) von 61,86 Mrd. US-Dollar erzielt und einen Gewinn pro Aktie (TTM) von 8,03 US-Dollar, einem KGV (TTM) von 23,76 und einer Eigenkapitalrendite (TTM) von 33,36%. Das Unternehmen zahlt eine Dividendenrendite von 3,48%.

#2. D-Wave Systems

Dieses Quantencomputing-Unternehmen entwickelt und liefert entsprechende Systeme, Software und Dienstleistungen. Zu seinen Produkten gehören The Leap und The Advantage, und es bietet Quantenanwendungen für die Terminplanung, Logistik, Arzneimittelentdeckung, Herstellungsprozesse und mehr. 

Vor kurzem gab D-Wave bekannt, dass Quantenmaschinen Probleme mit realen Anwendungsfällen jetzt schneller lösen können als jeder herkömmliche Computer. Anfang dieses Jahres kündigte das Unternehmen einen Quantencomputer mit 1.200 Qubits, 10.000 Kopplern und einer 20-mal schnelleren Lösungszeit für schwierige Optimierungsprobleme an.

Die Aktien des Unternehmens werden derzeit bei 1,86 US-Dollar gehandelt, was einem Anstieg von 138,6% seit Jahresbeginn entspricht, bei einem Marktwert von 267 Millionen US-Dollar. Es wurden 8,247 Millionen US-Dollar an Verkäufen (TTM) gemeldet, ein Verlust pro Aktie (TTM) von -0,66 US-Dollar und ein KGV (TTM) von -3,19, und es wurde ein Umsatzwachstum von über 20% für das 4. Quartal und das Gesamtjahr 2023 angekündigt, während die Bestellungen um 34% bzw. 89% stiegen. 

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

Fazit

Der Markt für Quantencomputing wird voraussichtlich 6,5 Milliarden US-Dollar im Jahr 2028 erreichen, und sein Potenzial, das Traveling Salesman Problem (TSP) zu lösen, hat Auswirkungen auf verschiedene Branchen wie Fertigung, Logistik, Supply-Chain-Management, E-Commerce, Verkehr und Forschung. Schließlich kann dies zu erheblichen Vorteilen führen, insbesondere zur Steigerung der Produktivität, zur Kosteneinsparung und zur Förderung von Innovationen in verschiedenen Sektoren.

Klicken Sie hier, um die Liste der fünf besten Quantencomputing-Unternehmen zu sehen.