Noch gibt es keine Quantencomputer. Trotzdem hat sich ein amerikanisches Forscherteam in der aktuellen Ausgabe von Science schon mal Gedanken darüber gemacht, ob solche Computer das Problem des Handlungsreisenden lösen könnten. Damit das von den Forschern vorgeschlagene Verfahren funktioniert, müssen die Computer allerdings eine Voraussetzung erfüllen: Sie müssten ziemlich kalt sein.
Edward Farhi vom MIT in Cambridge hat zusammen mit seinen Kollegen die quantenmechanische Zustandsgleichung für einen Quantencomputer aufgestellt, dessen Temperatur nahe am absoluten Nullpunkt bei minus 273 Grad Celsius liegt. Nur bei dieser niedrigen Temperatur ist sichergestellt, dass der mathematische Operator, der den Energiezustand des Computers beschreibt, sich mit der Zeit nur langsam verändert.
Die Forscher konnten zeigen, dass ein Quantencomputer unter dieser Voraussetzung mathematische Aufgabenstellungen von der Art des Problems des Handlungsreisenden lösen kann. Bei diesem Problem geht es darum, die Reihenfolge herauszufinden, mit der ein Geschäftsmann eine vorgegebene Anzahl von Städten auf kürzestem Wege bereist.
Grundsätzlich lösen kann dieses Problem aber jeder Computer. Genauer geht es darum herauszufinden, ob das Problem in “polynomialer Zeit” zu lösen ist. Vereinfacht ausgedrückt: Wird beim Problem des Handlungsreisenden die Anzahl der Städte vergrößert, dann darf die Rechenzeit nicht exponentiell mit der Städtezahl anwachsen. Man vermutet, dass klassische Computer das Problem nicht in polynomialer Zeit lösen können.
Für die Forscher galt es also noch herauszufinden, ob Quantencomputer dies können. Dabei hatten sie allerdings ein Problem: Die dazu notwendigen Rechnungen konnten sie natürlich nur auf einem klassischen Computer durchführen, so dass sie sich auf einfache Probleme beschränken mussten. Für diese konnten sie aber ? nach mehreren Monaten Rechenzeit ? zeigen, dass Quantencomputer derartige Probleme in polynomialer Zeit lösen könnten, wenn es sie eines Tages geben sollte.
Axel Tillemans
