Künftige Quantenbit-Rechner werden nur bei Spezialaufgaben glänzen

Aus: Spektrum der Wissenschaft, Juli 2008

Oft wird behauptet, Quantencomputer – so es sie demnächst gibt – würden blitzschnell besonders schwierige mathematische Probleme lösen, an denen heute selbst die besten Rechner scheitern. Den Quantencomputern soll dieses Kunststück gelingen, weil sie Hardware enthalten, die alle möglichen Lösungen gleichzeitig zu verarbeiten vermag. Quantencomputer jonglieren nicht wie heutige Rechner mit gewöhnlichen Bits, die nur die Werte null oder eins annehmen können, sondern mit Quantenbits.

Solche „Qubits“ sind vieldeutige Überlagerungen von Nullen und Einsen, die erst beim Auslesen des Rechenergebnisses in eindeutige Zustände übergehen. Soweit wir derzeit wissen, würden sie bei gewissen Spezialaufgaben tatsächlich das Rechentempo drastisch steigern – etwa beim Knacken der kryptografischen Kodes, mit denen finanzielle Transaktionen im Internet verschlüsselt werden. Doch bei anderen Aufgaben wie Schachspielen, Aufstellen von Flugplänen oder mathematischen Beweisen dürften Quantencomputer an die gleichen Grenzen stoßen wie heutige Rechner. Diese prinzipiellen Schranken gelten ganz unabhängig von den praktischen Schwierigkeiten, solche Geräte zu bauen.

Für Informatiker ist eine Rechenaufgabe erst dann „echt schwierig“, wenn die Zeit, die ein Computer zur Lösung braucht, mit der Größe der Aufgabe quasi explodiert, das heißt exponenziell ansteigt. Zwei Zahlen mit je so und soviel Ziffern zu multiplizieren fällt einem Computer leicht, denn die erforderliche Rechenzeit wächst „nur“ mit dem Quadrat der Ziffernanzahl. Bei der Aufgabe, eine riesige Zahl in ihre kleinstmöglichen Teiler zu zerlegen, tun sich hingegen selbst heutige Supercomputer so schwer, dass darauf die besten Verschlüsselungen beruhen. Erst ein Quantencomputer wäre tatsächlich im Stande, solche Kodes zu knacken.

Wie der Mathematiker Scott Aaronson in der Juliausgabe von Spektrum der Wissenschaft vermutet, sind aber die meisten anderen „echt schwierigen“ Probleme auch für Quantencomputer nicht leichter lösbar als für klassische Rechner. Solche Aufgaben lassen sich oft trügerisch einfach formulieren, etwa das Dreifarbenproblem: Genügen drei Farben, sagen wir Rot, Blau, Gelb, um alle Staaten auf einer beliebigen Landkarte so zu kolorieren, dass nie zwei gleichfarbige Länder aneinander grenzen? Oder: Wie verstaut man viele unterschiedliche Kisten am besten in einem großen Kofferraum? Oder: Wie plant ein Handlungsreisender seine Route so, dass er jede Stadt nur einmal besucht? Für all diese Probleme gibt es keine simple Formel, die verhindern könnte, dass die Rechenzeit mit der Anzahl der Länder, Kisten oder Städte exponenziell aus dem Ruder läuft.

Laut Aaronson ist das eine mathematische Eigenschaft solcher „NP-vollständigen“ Probleme, die sich auch mit noch so raffinierter Technik nicht überlisten lässt – auch nicht mit den Mitteln der Quantenphysik. Aber könnte nicht eines Tages eine völlig neue Physik entdeckt werden, die Rechenmaschinen mit ungeahnten Fähigkeiten ermöglicht? Das will Aaronson zwar nicht von vornherein ausschließen, doch er argumentiert so: Postulieren wir erst einmal, dass es aus guten mathematischen Gründen für diese NP-vollständigen Probleme niemals eine fertige Lösung geben wird. Analog postulieren Physiker aus guten Gründen, dass selbst mit der abstrusesten Sciencefiction-Technik nie ein Perpetuum mobile gebaut werden wird.

Solche Verbotsgesetze haben Physikern und Mathematikern schon früher zu besonders grundlegenden Erkenntnissen verholfen, und so gesehen, hätten auch prinzipielle Leistungsgrenzen für künftige Computer ihr Gutes. Zum Beispiel könnte es sonst in ferner Zukunft Rechengeräte mit eingebauter Zeitmaschine geben, die sich die fertige Lösung aus noch fernerer Zukunft besorgen.

Wenn gilt, dass NP-vollständige Probleme „echt schwierig“ sind, das heißt nicht mit technischen Tricks lösbar, dann folgt daraus: Zeitreisen sind prinzipiell unmöglich. So etwas hören Physiker gern, denn die Paradoxien der Zeitreise bereiten ihnen Kopfzerbrechen, und das versüßt ihnen vielleicht die Botschaft von den begrenzten Fähigkeiten des ungeduldig ersehnten Quantencomputers.