Vom erhofften Licht am Ende des Quantentunnels PlanQk-Messe 2021: „Quanten-Boost für die Optimierung“

Anbieter zum Thema

Rosenberger-OSI GmbH & Co. OHG

Fujitsu Technology Solutions GmbH

Fraunhofer Fokus

DB Systel GmbH

DB Systel GmbH / Deutsche Bahn AG

Wenn es um Optimierungsaufgaben geht, dann ist mittlerweile die Hoffnung auf das Quantencomputing nicht weit. Das wurde vor Kurzem in der Optimierungs-Session der virtuellen Messe der „PlanQK“-Community deutlich.

Ganz gleich ob es sich um Zugfahrpläne, die mit vorgeschriebenen Wartungsintervallen im Einklang stehen müssen, handelt, oder um möglichst flexible Schichtpläne in einer großen Uni-Klinik, ob es um die Optimierung von Netzkosten in einem landesweiten Energienetz geht oder um den zeitoptimierten Durchlauf von Werkstücken auf einer Kette von Bearbeitungsmaschinen: Mathematisch lassen sich alle vier Fallbeispiele als mehr oder weniger komplexe Optimierungsaufgabe formulieren.

Auf der kürzlich als Online-Veranstaltung durchgeführten Messe des Forschungs- und Entwicklungsverbunds PlanQK (Plattform und Ökosystem für Quantenunterstützte Künstliche Intelligenz) war die Vorstellung entsprechender Lösungen einem eigenen Teilforum unter dem Titel „Quanten-Boost für Optimierung“ gewidmet. Immer im Hinterkopf der Diskussionsteilnehmer*innen war dabei die Frage: lässt sich der Optimierungs-Algorithmus mit einem Quantencomputer seinerseits optimieren, wobei als Quantencomputer der Wahl in diesem Forum in allen Vorträgen Bezug auf den Quanten-Annealer der kanadischen Firma D-Wave Systems genommen wurde.

Wichtige Kürzel: QUBO, qbsolv, Leap

Der Quantenrechner von D-Wave basiert konzeptionell auf dem adiabatischen Theorem der Quantenmechanik und ist quasi durch sein Bauprinzip und die Nähe zur Born-Oppenheimer-Näherung (siehe: Ergänzendes zum Thema) in erster Linie (vielleicht sogar ausschließlich) für Optimierungen geeignet.

Dass alle vier Referenten in der Optimierungs-Session der PlanQK-Messe in Bezug auf den Quantenrechner mit D-Wave arbeiten, hat wohl zum einen mit der Wissenschaftshistorie dieses Quantencomputing-Modells zu tun, zum anderen mit der Tatsache, dass die Kanadier unter anderem mit dem Programm „qbsolv“ eine Software anbieten, mit der sich ein allgemeines QUBO-Optimierungsproblem automatisch in mathematisch „besser verdaubare Häppchen“ aufteilen lässt.

„QUBO“, ausgeschrieben „Quadratic Unconstrained Binary Optimization“ ist ein kombinatorisches Optimierungsverfahren, das sich unter anderem gut zur Modellierung von Aufgaben in der Verkehrsfluss-Steuerung eignet. Alle vier Referenten der Session stellten eine Problemlösung dar, die im weitesten Sinn hier einzuordnen ist.

Das Programm qbsolv von D-Wave ist auf den hauseigenen Quantenrechner zugeschnitten. Dieser sucht mehr oder weniger selbstständig für die gestellte Aufgabe ein optimales Ergebnis. Darüber hinaus bietet D-Wave mit der Cloud-Lösung „Leap“ für Anwender einen unkomplizierten Zugang in die Quantenrechner-Welt.

DB SysteL: Optimierung bei der Zug-Disposition

Eine QUBO-Optimierung für ein Tableau aus Zugfahrplänen, Wartungsintervallen, zielgenauer Verfügbarkeit von Wartungspersonal am Wartungsort, Minimierung von Leerfahrten etc. präsentierte Dr. Matthias Koch von DB Systel, dem IT- und Telekommunikationsdienstleister der Deutschen Bahn.

Angesichts von rund 300 Zügen, die die Deutsche Bahn im Fernverkehr betreibt (zumindest in Nicht-Pandemie-Zeiten), ergibt mit den oben genannten Parametern und zusammen mit vielen Neben- und Randbedingungen (beispielsweise „gefahrene Kilometer müssen kleiner sein als das Wartungsintervall“ oder „Bestimmte Fahrten dürfen sich nicht überlappen“) ein umfangreiches Gleichungssystem als Input für die Optimierungsrechnung.

Hier spätestens kommen Erkenntnisse der Quantenmechanik und des Quantencomputings ins Spiel, indem beispielsweise rechnerisch der Tunneleffekt nachgebildet wird und ein schneller Weg von einem relativen zu einem absoluten Minimum gefunden wird. DB Systel verwendet in diesem Zusammenhang offenbar auch die „Hybrid-Solver-Lösung“ von D-Wave Leap, bei der die bislang möglichen 5.000 binären Freiheitsgrade (Qubits) der Quantum Processing Unit von D-Wave aufgebohrt werden, um größere Variablenmengen verarbeiten zu können.

Planerio: Dienstplan-Optimierung im Gesundheitswesen

Nicht weniger umfangreich war das Tableau an Parametern inklusive Rand- und Nebenbedingungen, das Stephanie Troppmann vom Münchner Start-up Planerio für den Use Case „Dienstplan-Optimierung im Gesundheitswesen“ in ihrem Vortrag präsentierte. Troppmann erklärte, welche Bedingungen im Modell nicht „verhandelbar“ sind („eine Mitarbeiter*in kann nur eine Schicht zur gleichen Zeit übernehmen“ oder eine Mitarbeiter*in kann nur eine Schicht übernehmen, für die sie qualifiziert ist) und welche Bedingungen flexibel gehandhabt werden können (eine Mitarbeiter*in tritt die Schicht eine Stunde später an, um das Kind in die Kita bringen zu können “, dafür wird die Schicht des Vorgängers angepasst). Derzeit arbeiten Troppmann und ihre Kollegen bei Planerio aber noch mit einem starren Planungsmodell, die Schichtlängen „atmen“ also noch nicht.

In dieser Konstellation lässt sich die Optimierungs-Zielfunktion mit QUBO gut beschreiben, sogar ohne Einsatz von Schlupfvariablen (slack variables). [Anmerkung: mit solchen Hilfsvariablen lässt sich unter bestimmten Bedingungen die Rechnung vereinfachen, ohne dass das Ergebnis allzu sehr verzerrt wird.]

Derzeit sei das Tableau der Schichtpläne leider noch zu klein, um Quantencomputing einsetzen zu können, führte Troppmann aus, gab aber eine Schätzung ab: So meinte sie, dass man mit 5.000 Qubits (also 5.000 binären Freiheitsgraden beim adiabatischen Quantenrechner) die Besetzung von 105 Schichten darstellen könne. Ganz allgemein benötige Planerio aber mindestens 16.000 Qubits, um die Mehrzahl seiner Kunden „quantenrechnerisch“ sínnvoll bedienen zu können.

d-fine: Netzkosten-Optimierung in Zeiten der Energiewende

Eine Minimierung der Netzkosten über die Zeit ist das Optimierungsziel, das Benjamin Obert von d-fine in seiner Präsentation vorstellte. Den kontextuellen Rahmen bilden die Herausforderungen der Energiewende in Deutschland und Europa. Relevante Parameter bei der Lösung des Optimierungsproblems sind laut Obert Energieleistung, Lastfluss und Leistungsbilanz.

Man könne auch Ein- und Ausschaltvorgänge der Kraftwerke in das Modell aufnehmen. Bei der Lösung spielen Diskretitieren und der QUBO-Ansatz die entscheidende Rolle. Auch bei dieser Aufgabe kann laut Obert „Tunneln“ eine Möglichkeit sein, bessere Lösungen zu finden. Man sei dabei, „das Tunneln“ mit Quanten-Annealern, also in erster Linie dem D-Wave-Ansatz, zu simulieren.

Fraunhofer Fokus: Durchlaufdauer von Werkstücken minimieren

Der zeitoptimierte Durchlauf von Werkstücken in einer Kette von Bearbeitungsmaschinen war der Use Case, den Cristian Grozea vom Fraunhofer Institut Fokus in seinem Vortrag vorstellte. Das „Job-Scheduling-Problem“ bestand konkret darin, dass vier Werkstücke auf jeweils drei Werkzeugmaschinen bearbeitet werden sollten. Überschneidungen an einer bestimmten Maschine sind naturgemäß nicht möglich, Wartezeiten sind nicht erwünscht, jedenfalls keine langen. Das ganze Tableau enthält auch hier wieder die Aufgabe, die Dauer der gesamten Verarbeitungszeit zu minimieren.

Fermis Goldene Regel gibt Hoffnung

Tunneln ist auch hier die Quantenrechner-Lösung, die einem von irgendeinem lokalen Minimum zum absoluten Minimum bringen soll. Aber Tunneln ist im Quantencomputing leichter gedacht und gesagt als rechentechnisch umgesetzt.

„Was verhindert eigentlich, dass man nach dem Hineintunneln in das globale Minimum nicht auch gleich wieder heraustunnelt“, war eine der Fragen aus dem virtuellen Publikum in diesem Forum. Matthias Koch von DB Systel wagte eine Antwort: Das verhindere wohl Fermis goldene Regel, die sehr vereinfacht und umgangssprachlich ausgedrückt, besagt, dass dann, wenn die Temperatur geringer wird, kein höheres Energieniveau erreicht werden kann. Mit anderen Worten: Tunneln ist in der Regel offenbar eine Art Einbahnstraße und das ist in diesem Fall eine absolut gute Nachricht.

(ID:47317406)