Quanten und das binäre Lackierereiproblem

Kombinatorische Optimierungsprobleme gehören zu den komplexesten Aufgaben überhaupt. Ein bekanntes Beispiel dafür ist das Problem des Handlungsreisenden: Er muss eine Anzahl Kunden an verschiedenen Orten so besuchen, dass er an jedem Ort nur einmal eintrifft und die Gesamtstrecke möglich kurz ist. Selbst die schnellsten Superrechner stoßen bereits bei mittelgroßen Aufgaben dieser Art an ihre Grenzen. Gleichzeitig finden sich diese Fragestellungen in vielen Bereichen, etwa der Logistik, in der vernetzten Produktion und der Mobilität. Sie alle würden schneller, umweltfreundlicher und kostengünstiger, könnte man die jeweiligen kombinatorischen Optimierungsprobleme lösen. Quantenalgorithmen reduzieren den Rechenaufwand und rücken damit die Lösungen in greifbare Nähe. Im Folgenden soll ein Beispiel aus der Produktion die Schritte dafür erläutern (siehe Abbildung 1).

Als Beispiel dient die Lackiererei in einer Autofabrik. Die Fahrzeuge durchlaufen sie in einer vorgegebenen Reihenfolge, und ein Roboter lackiert sie. Die Sequenz besteht aus Paaren identischer Autos, die sich nur in der aufzubringenden Farbe unterscheiden. Dafür gibt es zwei Möglichkeiten, rot und blau, was der Aufgabe den Namen binäres Lackierereiproblem oder Binary Paint Shop Problem gab. Jeweils ein Auto eines Paares muss blau, das andere rot lackiert werden. Die einzelnen Fahrzeuge kommen jedoch in einer zufälligen, beliebigen Reihenfolge in der Lackiererei an.