Quantencomputer berechnen das Unberechenbare


D-Wave -Wave 2000 Qubit Processor. Bild: Steve Jurvetson/CC BY-2.0
Forscher zeigen, dass Quantencomputer wirklich etwas Neues sind: Sie lösen ein Problem, an dem jeder klassische Rechner unendlich lange beißen würde

Christian J. Meier | TELEPOLIS

Was ist besonders an Quantencomputern? Ihr atemberaubendes Rechentempo, lautet die gängige Antwort. Demnach können diese künftigen Rechner zwar nicht mehr als herkömmliche Computer, manches aber sehr viel schneller. Für das Zerlegen einer riesigen Zahl in ihre Primfaktoren etwa benötigt ein PC Jahrmilliarden. Ein Quantenrechner, wie er laut Expertenmeinung schon in einem Jahrzehnt verfügbar sein könnte, hingegen nur ein paar Minuten.

Zwei Informatiker zeigen nun aber, dass die Überlegenheit des Quantencomputers über bloße Schnelligkeit hinausgeht. Ran Raz und Avishay Tal haben ein Problem gefunden, das kein normaler Rechner je wird lösen können, selbst wenn er unendlich lange dafür Zeit hätte, ein künftiger Quantencomputer jedoch schon. Demnach spielt der Quantencomputer in einer anderen Liga: Das Wort „berechenbar“ überdeckt durch ihn eine größere Anzahl an Problemen – mindestens eines mehr, wie die beiden Forscher zeigen.

Raz, Professor an der Princeton University und am Weizmann Institut in Israel und sein ehemaliger Doktorand Tal, jetzt an der kalifornischen Stanford University, beschäftigen sich mit den Fähigkeiten von Computern. Klassische Rechner können zwar alles berechnen, was sich berechnen lässt, der Aufwand kann sich von Aufgabe von Aufgabe so sehr unterscheiden, dass manches praktisch unlösbar bleibt.

Ein Beispiel ist das schon genannte Faktorisierungsproblem. Primzahlen lassen sich zwar schnell multiplizieren, auch wenn es vielstellige Zahlen sind. Doch der umgekehrte Weg, ausgehend vom Produkt auf darin enthaltenen Primfaktoren zu schließen, kann sehr schwer werden: Die Zahl der nötigen Rechenschritte wächst unverhältnismäßig mit der Größe der zu zerlegenden Zahl.

weiterlesen