Lösung des Problems des Handlungsreisenden durch Quantencomputing

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

Was genau ist TSP? Bei diesem Mathematik-Klassiker geht es darum, die kürzestmögliche Route zu finden, um N Städte genau einmal zu besuchen, bevor man zur Ursprungsstadt zurückkehrt. Allerdings steigen mit der Anzahl der Städte auch die möglichen Routen und die Rechenzeit, um die optimale Lösung zu finden. Während dieses Problem mithilfe von Näherungsmethoden gelöst werden kann, könnten Quantencomputer viel bessere Lösungen liefern, und zwar viel schneller. 

Genau das ist es, was der theoretische Physiker meint Das Team von Prof. Dr. Jens Eisert zeigte: dass solche Probleme mit Quantencomputern besser und schneller gelöst werden können.

Quantencomputing nutzt Hardware und Algorithmen, die die Quantenmechanik nutzen, um komplexe Probleme zu lösen, die über die Möglichkeiten herkömmlicher Computer, einschließlich Supercomputer, hinausgehen. Trotz ihrer Leistung sind Supercomputer – riesige klassische Computer mit Tausenden von CPU- und GPU-Kernen – durch ihre Abhängigkeit von der Transistortechnologie des 20. Jahrhunderts bei der Lösung hochkomplexer Probleme eingeschränkt. 

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

Darüber hinaus ist es bei Quantencomputern im Gegensatz zu herkömmlichen Computern, die Lüfter zur Kühlung verwenden, erforderlich, dass ihre Quantenprozessoren bei extrem niedrigen Temperaturen gehalten werden, um ihre Quantenzustände beizubehalten. Dies wird durch unterkühlte Superflüssigkeiten erreicht. 

Supraleiter sind Materialien, die einen kritischen quantenmechanischen Effekt aufweisen, der es Elektronen ermöglicht, sich ohne Widerstand durch sie zu bewegen. Beim Durchgang bilden sich Elektronen zu Paaren, um eine Ladung über Barrieren hinweg zu transportieren. Wenn zwei Supraleiter auf beiden Seiten eines Isolators platziert werden, entsteht ein Josephson-Kontakt, der zur Leitung supraleitender Qubits verwendet wird.  

Ein Qubit ist nützlich für die wichtige Aufgabe, seine Quanteninformationen in einen Superpositionszustand zu versetzen, 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.

Hier können sich durch die Verschränkung zweier Qubits Änderungen an einem direkt auf das andere auswirken, während wir, wenn diese verschränkten Qubits in einen Überlagerungszustand gebracht werden, sehr viele Wahrscheinlichkeiten erhalten. Bei der Berechnung auf einem Quantencomputer wird eine Überlagerung aller möglichen Rechenzustände vorbereitet und durch Interferenz werden Lösungen gefunden.

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

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

„Es gibt viele Mythen darüber und manchmal auch eine gewisse Menge heißer Luft und Hype. Allerdings sind wir mit mathematischen Methoden konsequent an die Problematik herangegangen und haben zu diesem Thema solide Ergebnisse geliefert. Vor allem haben wir geklärt, inwieweit es überhaupt Vorteile geben kann.“ 

Das kritische Problem des Handlungsreisenden

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

Angesichts der sozialen und wirtschaftlichen Bedeutung dieser Probleme waren sie Gegenstand intensiver Forschung. Daher wirkt sich die Suche nach Antworten auf Probleme wie die effizienteste Lieferkette und der günstigste Lieferweg positiv auf unser tägliches Leben aus.

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

Die Lösung dieses Problems bietet viele Vorteile, darunter die Reduzierung der zurückgelegten Distanzen und Stunden sowie die Reduzierung des Kraftstoffverbrauchs. Die Minimierung der zurückgelegten Distanz kann dazu beitragen, den CO2-Fußabdruck deutlich zu reduzieren, was sich in einer besseren Luftqualität, einer Verlangsamung des Klimawandels und einem Wirtschaftswachstum niederschlägt. Darüber hinaus kann die Lösung des TSP bei der pünktlichen Lieferung von Waren und zeitnahen Treffen mit Kunden helfen, was das Kundenerlebnis und die Außendienstgeschäfte verbessert.

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

Zur Lösung des TSP-Problems stehen verschiedene Methoden zur Verfügung. Eine davon ist der „Brute-Force“-Ansatz, bei dem alle möglichen Permutationen berechnet werden, um die kürzeste Route zu finden. Bei der Branch-and-Bound-Methode wird das Problem in mehrere Teilprobleme zerlegt, wobei die Lösung jeder einzelnen Stufe die Lösung der nachfolgenden Stufen beeinflusst.

Bei der dynamischen Programmierung liegt der Fokus auf der Vermeidung redundanter Berechnungen. Der Nearest Neighbor hingegen ist ein Näherungsalgorithmus, bei dem Sie mit dem Startort beginnen und dann beim nächstgelegenen aufhören. Sobald alle Städte abgedeckt sind, geht es zurück zum Ausgangspunkt. Diese Methode ist zwar praktisch und relativ schnell, stellt jedoch möglicherweise nicht immer eine effiziente Route dar.

Mit fortschreitender Technologie können Routenplanung und -optimierung weitaus effektiver durchgeführt werden. Insbesondere künstliche Intelligenz (KI) kann ebenfalls zur Lösung des Problems beitragen, indem sie riesige Datenmengen schnell analysiert und vielen modernen Unternehmen dabei hilft, operative und strategische Entscheidungen zu treffen.

Zur Lösung des Problems werden auch Quantencomputer untersucht; Schließlich bieten sie im Vergleich zu klassischen Computern erhebliche Rechengeschwindigkeiten. Es wird seit langem vermutet, dass diese Computer tatsächlich dazu beitragen könnten, die Lösung dieser Probleme zu verbessern. 

Verwendung von Quantencomputertechniken zur Lösung von TSP

Während Quantencomputer großes Interesse wecken und vielversprechende Ergebnisse für bestimmte Probleme liefern, ist das Ausmaß dieses Quantenvorteils noch weitgehend unerforscht. 

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

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

„Wir gehen einfach, unabhängig von der physikalischen Realisierung, davon aus, dass es genügend Qubits gibt, und schauen uns die Möglichkeiten an, mit ihnen Rechenoperationen durchzuführen“, was eine Ähnlichkeit mit einem häufigen Problem der Kryptographie, nämlich der Verschlüsselung von Daten, erkennen lässt, erklärte Vincent Ulitzsch , ein Ph.D. Student an der Technischen Universität Berlin. 

Anschließend verwendete das Team den Shor-Algorithmus, einen Quantenalgorithmus, um die Primfaktoren einer ganzen Zahl zu bestimmen und eine Unterklasse dieser Optimierungsprobleme zu lösen. Dadurch explodiert die Rechenzeit nicht mehr mit zunehmender Anzahl von Städten. Sie steigt nur noch polynomisch an, also mit Nx, wobei x eine Konstante ist. Auf diese Weise ist die erhaltene Lösung auch qualitativ deutlich besser als die Näherungslösung mit dem herkömmlichen Algorithmus.

Durch den Einsatz kryptografischer Konzepte und der Theorie des rechnergestützten Lernens liefert die Studie „vollständig konstruktive Beweise dafür, dass Quantencomputer bei der Approximation kombinatorischer Optimierungsprobleme einen superpolynomischen Vorteil gegenüber klassischen Computern aufweisen.“ 

Die Studie stellte außerdem fest, dass das Forschungsteam erhebliche Fortschritte bei der wichtigen Frage gemacht hat, welches Potenzial Quantencomputer für die Annäherung an die Lösung kombinatorischer Optimierungsprobleme bieten könnten, die erhebliche soziale und wirtschaftliche Auswirkungen haben.

Die Studie wurde gefördert durch die Einstein Research Unit, das Berliner Forschungszentrum Mathematik (MATH+ Exzellenzcluster), das BMBF (Hybrid), das BMWK (EniQmA), das Munich Quantum Valley und die DFG. Auch das Bundesministerium für Bildung und Forschung leistete finanzielle Unterstützung.

Das Potenzial des Quantencomputings erkunden 

Obwohl dies eine große Leistung ist, war es nicht das erste Mal, dass Quantencomputer zur Lösung des Problems des Handlungsreisenden eingesetzt wurden. Es gab bereits viele Fälle, in denen Enthusiasten und Forscher versuchten, das Problem mithilfe von Quantencomputern zu lösen. 

Im Dezember 2022 wurde a Krepppapier schlug einen Quantenalgorithmus für den TSP vor, der auf der Grover Adaptive Search (GAS) basiert. Unter dem GAS-Framework gibt es mindestens zwei grundlegende Schwierigkeiten: Lösungen sind möglicherweise nicht realisierbar, und die Anzahl der Qubits aktueller Quantencomputer ist sehr begrenzt und kann die Mindestanforderungen nicht erfüllen, was die Anwendung von Quantenalgorithmen für kombinatorische Optimierungsprobleme einschränkt. 

Daher hat das Papier das Orakel „Hamiltonian Cycle Detection“ (HCD) verfeinert, das unpraktische Lösungen automatisch während der Algorithmusausführung entfernen kann. Sie entwickelten außerdem eine „Ankerregister“-Strategie, um die Qubit-Nutzung einzusparen, wobei sie die Reversibilitätsanforderungen des Quantencomputings vollständig berücksichtigten und die Schwierigkeit überwanden, dass die verwendeten Qubits nicht einfach überschrieben oder freigegeben werden. Dadurch konnten für die Studie nur 31 Qubits benötigt werden, und die Lösung hatte eine Erfolgsquote von 86.71 %.

Im Jahr 2019 erklärte sich selbst der Physikkenner Joseph Cammidge schrieb über die Verwendung eines Annealing-Quantenprozessors, der es ihm ermöglichte, das Problem des Handlungsreisenden für sieben Städte zu lösen, und das theoretisch das Potenzial hat, das Problem für neun Städte zu lösen, sobald technologische Einschränkungen beseitigt sind. 

Eine neue Rechenmethode, Quantum Annealing, hat das Potenzial gezeigt, Optimierungsprobleme schneller als klassische Techniken zu lösen. Seine Theorie besagt, dass die Qubits bei Unterkühlung einen optimalen Niedrigenergiezustand erreichen. 

Doch im Jahr 2021, a Studie Johnson & Johnson wurde von Supply Chain Digital & Data Science finanziert und stellte fest, dass der Quanten-Annealer nur eine Problemgröße von 8 oder weniger Knoten bewältigen kann und seine Leistung im Vergleich zum klassischen Löser sowohl in Bezug auf Zeit als auch Genauigkeit unterdurchschnittlich ist.

Der Einsatz von Quantencomputing zur Lösung des TSP-Problems wird schon seit einiger Zeit praktiziert. Vor über zwei Jahrzehnten, im Jahr 2001, begann eine Studie Suche für einen Quantenalgorithmus zur Lösung des Problems.

In der Arbeit untersuchte Buckley Hopper von der University of Alabama die Quantencomputeralgorithmen von Grover und Shor. Er stellte fest, dass Grovers Algorithmus lediglich eine Verbesserung der Quadratwurzel liefert und somit ein klassisch unlösbares Problem nicht auf einem Quantencomputer lösbar machen kann. Was Shors Algorithmus betrifft, so stellte Hopper fest, dass er zwar ein vermeintlich unlösbares Primfaktorproblem auf der Quantenmaschine in ein lösbares umwandeln kann, sich aber nur für einen ganz bestimmten Problemtyp eignet. 

Insgesamt fand Hopper „kein zufriedenstellendes Ergebnis für einen Algorithmus zur Berechnung von Näherungslösungen für das Problem des Handlungsreisenden“.

Einige Jahre später gründete das Institute of Electrical and Electronics Engineers (IEEE) vorgeführt ein neuer Algorithmus zur Lösung des Problems, der sowohl von genetischen Algorithmen als auch von Quantencomputern inspiriert ist. Das IEEE stellte fest, dass die Ergebnisse der Anwendung des vorgeschlagenen Algorithmus auf einige Fälle des Problems des Handlungsreisenden erheblich besser sind als die Ergebnisse, die standardmäßige genetische Algorithmen liefern.

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 der Forschung und Entwicklung des Quantencomputings arbeiten:

# 1. IBM

Die International Business Machines Corporation ist in zahlreichen Branchen tätig, darunter KI, Cloud-Dienste, IT, Kundenfinanzierung und Unternehmensfinanzierung. Der Technologieriese engagiert sich zudem im Bereich Quantencomputing über seine IBM Quantum Platform, die öffentlichen und Premium-Zugang zu seinen Cloud-basierten Quantencomputing-Diensten bietet. Dazu gehören eine Reihe von IBM-Quantenprozessor-Prototypen, Tutorials zur Quantenberechnung und ein interaktives Lehrbuch.

Zuletzt IBM-Wissenschaftler angegeben dass sie der Überwindung eines Hindernisses, das das bahnbrechende Potenzial von Quantencomputern freisetzt, einen weiteren Schritt näher kommen. Dazu führten sie einen neuen Quantenfehlerkorrekturcode ein, der ihrer Meinung nach etwa zehnmal effizienter ist als bisherige Methoden. 

Ende letzten Jahres brachte das Unternehmen außerdem den Quantencomputer namens Condor auf den Markt, der über 1,121 supraleitende Qubits verfügt, die in einem Wabenmuster angeordnet sind. IBM stellte außerdem IBM Quantum System Two vor, seinen ersten modularen Quantencomputer und seine erste quantenzentrierte Supercomputing-Architektur, die skalierbar ist und daher mit Chips aufgerüstet werden kann, die in den nächsten fünf Jahren auf den Markt kommen.

Bei einer Marktkapitalisierung von 175 Milliarden US-Dollar notieren die IBM-Aktien bei 190.86 US-Dollar, ein Plus von 16.66 % seit Jahresbeginn. IBM erzielte einen Umsatz von 61.86 Milliarden US-Dollar bei einem Gewinn pro Aktie von 8.03, einem KGV von 23.76 und einer Eigenkapitalrendite von 33.36 %. Die Dividendenrendite beträgt 3.48 %.

# 2. D-Wave Systems

Dieses Quantencomputerunternehmen 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 Planung, Logistik, Arzneimittelentwicklung, Herstellungsprozesse und mehr. 

Anfang dieses Monats sagte D-Wave, dass Quantenmaschinen jetzt Probleme mit realen Anwendungen schneller lösen können als jeder gewöhnliche Computer. Anfang des Jahres kündigte das Unternehmen einen Quantencomputer mit 1,200 Qubits, 10,000 Kopplern und einer 20-mal schnelleren Lösungszeit bei schwierigen Optimierungsproblemen an.

Die Aktien des Unternehmens notieren derzeit bei 1.86 US-Dollar, ein Plus von 138.6 % seit Jahresbeginn (YTD), bei einer Marktkapitalisierung von 267 Millionen US-Dollar. Das Unternehmen meldete einen Umsatz von 8.247 Millionen US-Dollar (TTM), einen Gewinn pro Aktie von -0.66 (TTM) und ein KGV von -3.19 (TTM) und gab für das vierte Quartal und das Jahresende 20 ein Umsatzwachstum von über 4 % bekannt, während die Auftragseingänge um 2023 % bzw. 34 % zunahmen. 

Interessanterweise erklärte der CEO des Unternehmens, Dr. Alan Baratz, die Dynamik des Unternehmens und verwies dabei auf die mehrjährige strategische Partnerschaft des Unternehmens mit Zapata AI, die Einführung des über 1,200 Qubits umfassenden Advantage2-Prototyps, Joint Ventures mit NEC Australia und Deloitte Canada sowie die Ernennung der ehemaligen Heimatschutzministerin Kirstjen Nielsen in den Vorstand.

Fazit

Der Markt für Quantencomputing wird voraussichtlich wachsen 6.5 Milliarden US-Dollar erreichen im Jahr 2028 und sein Potenzial zur Lösung des Problems der Handlungsreisenden (Travelling Salesman Problem, TSP) hat Auswirkungen auf mehrere Branchen, wie Fertigung, Logistik, Lieferkettenmanagement, E-Commerce, Transport und Forschung. Schließlich kann es erhebliche Vorteile mit sich bringen, insbesondere die Produktivität steigern, Kosten senken und Innovationen in verschiedenen Sektoren vorantreiben.

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