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.
