Quantencomputing im Einsatz für die Mathematische Optimierung

Herr Weissenbäck, Ihr Fachgebiet »mathematische Optimierung« ist im Zuge stetig voranschreitender Digitalisierung für verschiedenste logistische und industrielle Anwendungen immer wichtiger geworden. Was erwarten Sie vom Quantencomputing?

Markus Weissenbäck: In der Logistik müssen tagtäglich anspruchsvolle Optimierungsprobleme gelöst werden und dies derzeit häufig noch nicht ausreichend effizient. Man behilft sich über so genannte Heuristiken, also Annäherungen an die optimale Lösung und nimmt dafür meist sehr lange Berechnungszeiten in Kauf. Genau hier setzen wir in Zukunft auf die Vorteile durch Quantencomputing.

 

Was sind diese Vorteile und worauf fußen Ihre Hoffnungen?

Markus Weissenbäck: Bereits in den frühen neunziger Jahren wurde mit dem Algorithmus von Shor zur Primfaktorzerlegung und dem Algorithmus von Grover zur unsortierten Datenbanksuche gezeigt, dass Quantencomputing einen beweisbaren Vorteil gegenüber herkömmlichen Rechnern bieten kann.

Mit dem Grover-Algorithmus nutzt man die so genannte Amplitudenverstärkung (engl. amplitude amplification). Damit können z. B. durch dynamische Programmierung viele Lösungsverfahren quadratisch beschleunigt werden. Mathematisch gesprochen heisst dies, man spart sich einen »Wurzelfaktor« in der Komplexität basierend auf der Menge der Eingabedaten des Problems.

Der Algorithmus von Shor basiert vor allem auf der Quantum-Fouriertransformation. Mit ihm können beispielsweise lineare Gleichungssysteme mit exponentieller Beschleunigung gelöst werden.

 

Dies sind vor allem mathematische Überlegungen – wie sähe dies aber in der Übertragung auf realistische Herausforderungen aus?

 

Markus Weissenbäck: Für realistische Berechnungen aktueller Optimierungsaufgaben würde man beim derzeitigen Stand der Technik mehr als 10000 Qbits benötigen. Der aktuell neuste Quantencomputer, der IBM Q System One, besitzt 27 QBits. Dies klingt zunächst sehr wenig, aber bereits heute sind mit der aktuellen Hardwaregeneration, der so genannten NISQ (Quantum Approximate Optimization Algorithm)-Hardware einige Probleme lösbar. Mit variationellen Quantenalgorithmen (z.B. der QAOA-Algorithmus) oder Heuristiken erreicht man zwar noch nicht das Optimum bei der Berechnungsgeschwindigkeit aller Varianten einer Optimierung, aber man wird in Zukunft einen deutlichen Zeitgewinn gegenüber Berechnungen auf herkömmlichen Computern ereichen. Bis zur tatsächlichen Anwendung in der Industrie wird es aller Wahrscheinlichkeit nach noch einige Jahre dauern. Aber, mit unseren Optimierungsmethoden interessieren wir uns auch dafür, wie wir Quantencomputer effizienter machen können, insbesondere mit der Optimierung von Quantenschaltkreisen.