»Das Bestimmen der kürzesten Wege ist heute Grundlage jedes Navigationssystems. Doch sobald mehrere davon gefunden werden sollen, die auch noch miteinander interagieren, kommen klassische Computer schnell an ihre Grenzen. In unserem Szenario ist die Anzahl möglicher Interaktionen hoch, da die Drohnen nicht miteinander oder mit Gebäuden kollidieren dürfen. Mit Quantencomputern können wir solche Interaktionen direkt in die Qubits einkodieren«, erklärt der Informatiker. Für Thales formalisierte er mit seinem Team zunächst die Fragestellung mitsamt allen relevanten Faktoren mathematisch. Aus einer Geodatenbank mit Höheninformationen extrahierten sie ein 3D-Modell von Bonn, ergänzt um die vierte Dimension der Zeit. In diesem Graphen modellierten sie die verschiedenen möglichen Wege mehrerer Drohnen als schlauchartige Räume, um gleiche Wege zu vermeiden. Das Problem: Allein über der Innenstadt von Bonn gäbe es mehr als 1,2 Millionen Knoten, also Orte, an denen sich eine Drohne theoretisch aufhalten könnte. Für derzeitige Quantencomputer ist das viel zu groß.
Daher entlasten die Forschenden den Quantenrechner um Aufgaben, die klassische Rechner ohnehin sehr gut können: »Wir setzen die Start- und Zielpunkte fest und lassen einen klassischen Computer die kürzesten Routen berechnen. Aus diesen vorausgewählten Wegen muss dann der Quantencomputer nur noch die Routen ohne Kollisionen herausfinden. Er zieht also nicht mehr 1,2 Millionen Punkte in Betracht, sondern muss nur noch ein paar hundert Wege berücksichtigen.« Das Quantenergebnis wird dann wieder von einem klassischen Algorithmus geprüft und wenn es trotzdem noch Kollisionen gibt, kann die Menge an Pfadmöglichkeiten erweitert werden. »Ein entscheidender Punkt ist also herauszufinden, welcher Teil des Problems sich für einen Quantencomputer eignet und welcher nicht«, betont Dr. Nico Piatkowski.
Für ihre Berechnungen verglichen die Forschenden einen Simulated-Annealing-Software-Algorithmus, einen D-Wave-Quantencomputer, und die an ihrem Institut patentierte Hardware »IAIS Evo Annealer«, die die Funktionsweise eines Quantencomputers nachbildet. Damit lässt sich deutlich effizienter als bisher möglich prüfen, inwiefern sich spezifische mathematische Probleme künftig mit Quantencomputing lösen lassen. »Wir erzielen für ein Beispiel mit zwanzig Drohnen in einem eingeschränkten Gebiet bereits profitable Ergebnisse auf beiden Systemen, mit null Kollisionen und der bestmöglichen Weglänge«, freut sich Piatkowski. Damit konnten die Forschenden zeigen, dass sich das Drone-Path-Finding-Problem mithilfe von Qubits lösen lässt. Im nächsten Schritt soll der entworfene Quantenalgorithmus auf weiteren Quantencomputern getestet werden.