Der Handlungsreisende mit dem Quantencomputer

Weder im Fachgeschäft noch beim Discounter werden sie angeboten, aber sie beschäftigen bereits die Wissenschaftler: Quantencomputer. Und obwohl bisher weder ihre Herstellerfirmen noch das Jahr ihrer Cebit-Präsentation feststehen, ist das Funktionsprinzip der traumhaft performanten Maschine klar: Die Gesetze der Quantenmechanik, bislang eher der Zuständigkeitsbereich für die Welt der Elementarteilchen, Atome und Moleküle, werden den Quanten-Rechnern Beine machen, wo klassische Computer erlahmen müssen.

Während in den heutigen Computern die Bits entweder die Werte Null oder Eins annehmen, besitzen die qbits des Quantencomputers Dank des quantenmechanischen Superpositionsprinzips alle Werte gleichzeitig. Ein Beispiel: Zwei qbits können gleichzeitig die vier Zustände 00, 01,10, und 11 annehmen. Bereits 32 qbits ermöglichen vier Milliarden Kombinationen. Die neuen Computer werden natürlich auf Parallelverarbeitung setzten: Jede Rechenoperation würde in allen Zuständen gleichzeitig ablaufen. Die 32 qbits könnten, wären sie eines fernen Tages in der CPU eines Quantenrechners ansässig, vier Milliarden Rechenoperationen in einem Arbeitsgang abhandeln.

Für solche rasanten Numbercruncher sind natürlich nur die schwierigsten mathematischen Probleme gerade gut genug. Das Wissenschaftsmagazin Science berichtet in seiner jüngsten Ausgabe, die so genannten nondeterministischen, polynomiellen Probleme, für deren Lösung bisher kein effizienter Lösungsalgorithmus gefunden wurde, seien mit qbits in den Griff zu bekommen. Zu diesen NP-Problemen gehört auch das Problem, das unter dem Namen "Traveling Salesman" bekannt wurde. Dieser steht bekanntlich ratlos vor der Aufgabe, die kürzeste Verbindungsstrecke zwischen einer größeren Anzahl von Städten zu finden, die er jeweils genau ein Mal besuchen muss. Bisher ist er auf die Hilfe rückschrittlicher klassischer Computer angewiesen. Da diese mit ihren Algorithmen mit wachsender Zahl der zu bereisenden Städte exponenziell Rechenzeit konsumieren, liegt die Weltrekordmarke derzeit lediglich bei 3038 Städten.

Um zukünftig Handlungsreisenden neue Perspektiven bieten zu können, haben amerikanische Wissenschaftler am Massachusetts Institute of Technology und an der Bostoner Northeastern University jetzt schon Algorithmen für zukünftige Quantencomputer getestet. Auch wenn sie für ihre Simulation auf gestrige Computertechnik von heute zurückgreifen mussten und ihre Ergebnisse ebenso vorläufig wie spekulativ sind, wird ihr Science-Artikel die Softwarehäuser bestimmt zu ihrem übernächsten Produkt animieren: dem Quanten-Routenplaner. (thd)