Quantencomputing ist eine aufstrebende Technologie, die die Gesetze der Quantenmechanik nutzt, um Berechnungen durchzuführen.
Quantencomputing ist eine aufstrebende Technologie, die die Gesetze der Quantenmechanik nutzt, um Berechnungen durchzuführen.
Während klassische Computer mit binären Bits arbeiten, die sich nur in einem einzigen Zustand befinden können – entweder "0" oder "1" –, betreiben Quantencomputer mit Qubits (Quantenbits), die sich gleichzeitig in einer Überlagerung von "0" und "1" befinden können.
Diese Eigenschaft ermöglicht es einem Quantencomputer, Berechnungen parallel durchzuführen. Dadurch können Quantencomputer bestimmte Probleme viel schneller lösen als klassische Computer.
Angesichts der jüngsten Durchbrüche in der Quantenwissenschaft und -technologie wollten wir die potenziellen Anwendungen für Quantencomputing im Bereich des Airline Revenue Management (RM) untersuchen. Zu diesem Zweck hat sich Amadeus mit dem dänischen Unternehmen Kvantify zusammengetan , das sich auf Quantenalgorithmen und High-Performance-Computing spezialisiert hat. Wir haben unsere Ergebnisse auf der AGIFORS 2023 Revenue Management Studie Group vorgestellt, die vom 5. bis 7. Juni in Helsinki stattfand , wo unser gemeinsamer Vortrag zum Thema "Application of quantum computing in airline revenue management" den Preis für die beste Innovation erhielt.
Welche Probleme lassen sich mit heutigen Quantencomputern lösen?
Wir begannen mit der Evaluierung, ob das Kernproblem von Airline-RM – das Single-Flight-Leg-Optimierungsproblem – mit der heute existierenden Quantenhardware gelöst werden kann. Die Lösung dieses Problems kann als Matrix ausgedrückt werden, die den Tarif (Preis) für einen Flug in Abhängigkeit von der verbleibenden Kapazität (x) des Flugzeugs und der verbleibenden Zeit (t) bis zum Abflug angibt. Dieses Problem wird routinemäßig von allen Fluggesellschaften gelöst und liefert uns einen Benchmark, um die Leistung des Quantencomputers zu bewerten.
Die genaue Lösung eines klassischen Computers ist in Abbildung 1 (links) dargestellt, wobei jedes farbige Quadrat den Tarif darstellt, der in Abhängigkeit von x und t berechnet werden sollte – hoch, niedrig oder geschlossen. Beachten Sie, dass die Flugkapazität hier nur 3 Sitzplätze beträgt. Wie sich herausstellt, ist dieses kleine Problem das Beste, was wir mit der heute existierenden Quantenhardware tun können.
Um dieses Problem auf einem echten Quantencomputer zu lösen, mussten wir einen Quantenalgorithmus entwickeln, der das Problem darstellt. Der Quantencomputer, für den wir uns entschieden haben, war auf die Lösung eines einzigen Problemtyps beschränkt: das Ising-Modell
, ein mathematisches Modell des Magnetismus. Deshalb mussten wir unser Airline-RM-Problem irgendwie in die Sprache der Magnete übersetzen. Gar nicht so offensichtlich!
Es ist uns jedoch gelungen und die Lösung aus dem Quantencomputer ist in Abbildung 1 (rechts) dargestellt.
Beim Vergleich der Matrizen stellen wir fest, dass der Quantencomputer selbst bei diesem winzigen Beispiel einen Fehler macht. Dies zeigt, dass die bestehende Quantenhardware noch einen langen Weg vor sich hat, bevor sie kommerziell relevant wird.
Hat Quantencomputing Anwendungen im Airline Revenue Management?
Stellen Sie sich nun vor, dass in der (hoffentlich nicht allzu fernen) Zukunft Quantenhardware so weit reift, dass wir Zugriff auf kommerziell skalierbare und fehlerfreie Quantencomputer haben. Gäbe es eine Anwendung für diese Computer in Airline RM?
Was würde passieren, wenn wir versuchen würden, alle Reiserouten im Netzwerk gleichzeitig zu bepreisen? Angenommen, die Fluggesellschaft kann für jede der 7 möglichen Reiserouten im Netzwerk zwischen 5 verschiedenen Tarifen (Preispunkten) wählen. In Abbildung 3 (links) stellen wir alle möglichen Kombinationen von Tarifen – auch Angebotssets genannt – als "Karten" dar, auf denen die Tarife für jede Reiseroute angegeben sind. Selbst in diesem kleinen Beispiel gibt es 279.936 Karten, unter denen die Fluggesellschaft suchen muss, um diejenigen zu finden, die den Umsatz maximieren. Es kann gezeigt werden, dass höchstens 6 der 279.936 Karten optimal sind. Das Problem besteht also darin, die richtigen zu identifizieren.
Auch wenn dies für dieses kleine Netzwerk nicht allzu schwierig sein mag, sollten Sie sich ein realistisches Airline-Netzwerk vorstellen – zum Beispiel 9 Tarifklassen und 20 alternative Reiserouten, die zwei Städte verbinden. In diesem Fall gibt es astronomische 10^20 oder 100 Trillionen Angebotsmengen, die es einem klassischen Computer unmöglich machen, sie zu durchsuchen.
Doch genau das kann ein Quantencomputer gut!
Im Gegensatz zu einem klassischen Computer, der die Angebotsmengen sequentiell durchsucht, erlauben uns die Eigenschaften des Quantencomputings, die Suchen parallel durchzuführen. In Abbildung 4 können wir sehen, wie sich die Magie entfaltet. Ausgehend von der Wolke aus 279.936 Punkten führen wir den Quantensuchalgorithmus aus. Dieser Algorithmus ist iterativ, und wir beobachten, wie aufeinanderfolgende Iterationen die Cloud allmählich "verdampfen" lassen, bis nur noch die guten Lösungen übrig bleiben.
Generell kann man beweisen, dass der Quantensuchalgorithmus eine quadratische Beschleunigung liefert. Das hat dramatische Folgen. Um auf die realistische Größe des Netzwerks zurückzukommen: Die Quantenbeschleunigung bedeutet, dass die Suche 10 Milliarden Mal schneller durchgeführt werden kann! Mit einer solchen Beschleunigung ist es nun möglich, die auf der Reiseroute basierende Netzwerkoptimierung innerhalb von Stunden zu lösen.
Kommerziell würde dies bedeuten, dass eine Fluggesellschaft ihren Umsatz um 2 % bis 3 % steigern könnte, wie die Forscher Qian Liu und Garrett Van Ryzin im Jahr 2008 gezeigt haben .
Die Quantentechnologie, die zur Lösung dieses Problems benötigt wird, existiert zwar noch nicht, aber die Wartezeit könnte nicht allzu lang sein. In der Roadmap
IBM, einem der führenden Anbieter von Quantenhardware, erwartet bis 2026+ kommerziell nutzbare Quantencomputer. Wie wir gezeigt haben, kann Quantencomputing bisher unlösbare Probleme lösen und Fluggesellschaften erhebliche Umsatzvorteile verschaffen. Bis die Quantenhardware ausgereift ist, ist die Zeit jedoch gut investiert, um nach einem ähnlichen Quantenvorteil in anderen Bereichen zu suchen.
TO TOP