Quantencomputer und die Zukunft des Berechenbaren

2007 lief in Australien ein TV-Werbespot. Darin unterhielten sich zwei Models in der Garderobe über Quantenmechanik. Interessant sei, so die beiden, dass sie anders als sonst in der Physik üblich nicht von Materie, Energie oder Wellen handle, sondern von Information, Wahrscheinlichkeiten und Beobachtungsgrössen.

Bemerkenswert an diesem Werbefilm ist nicht, dass sich zwei Mannequins über eine Theorie der Physik unterhalten, sondern vielmehr, dass der Film die Quantenmechanik nicht nur als interessante Forschungsperspektive für die Physik darstellt, sondern auch für die Informatik. Diese wissenschaftliche Position war vor zwölf Jahren noch nicht so verbreitet wie heute, da sich die Quanteninformatik schnell entwickelt und sich auch an der ETH Zürich ausserhalb der Physik etabliert.

Seither konnte eine Reihe von Experimenten, darunter solche von ETH-Forschenden, belegen, dass der Bau von Computern, die nach den Regeln der Quantenmechanik funktionieren, grundsätzlich möglich ist – es gibt verschiedene Technologien dafür und seit einiger Zeit besteht ein regelrechter Wettbewerb, wer den ersten Quantencomputer bauen kann (vgl. Globe 2/2018).

Vordenker und Zoowärter der Komplexitäten

Ein Computerwissenschaftler, der immer wieder originelle Argumente vorträgt, inwiefern Quantencomputer dereinst auch Probleme lösen könnten, die für heutige Computer zu komplex sind, ist Scott Aaronson, Professor für Informatik und Gründungsdirektor des Quantum Information Center an der Universität von Texas in Austin. Der Dialog der Models ist denn auch ein einziges wörtliches Zitat, das man in seinem Buch «Quantenrechnen seit Demokrit» nachlesen kann.

«Typisch für Scott Aaronson ist, dass er über das klassische Computer­mo­dell hinausdenkt und ganz grundsätzlich danach fragt, welche Typen von Computern vermutlich mehr Probleme lösen können als die heutigen Computer», sagt ETH-Professor Renato Renner. Der Physiker ist ein Spezialist für Quanteninformationstheorie. Er hat schon selber intensiv mit Aaronson auf dessen Blog debattiert (vgl. externe Seite Diskussion unter «Responses»). Aaronson seinerseits war früher bereits Gast an der ETH Zürich, etwa am Zurich Physics Colloquium 2009.

Man hat Scott Aaronson schon einmal einen «externe Seite Komplexonauten» genannt, weil er sich bis zu den komplexesten Problemen vorwagt, um die prinzipiellen Möglichkeiten und Grenzen von Computern auszuloten – seien das nun Computer wie wir sie heute kennen, Quantencomputer oder ganz andere Typen von Computern, die man sich heute noch fast nicht vorstellen kann. In seinem bekannten und im Internet abrufbaren «externe Seite Zoo der Kom­plexi­täten» gruppiert er verschiedene Klassen von Problemen so, dass man sieht, wie gut die Computer diese Probleme jeweils berechnen und lösen können.

Auf jeden Fall ist Scott Aaronson ein Forscher, der sich gern grossen und grundsätzlichen Fragen stellt. So wird er auch in Zürich, wo er im Rahmen der Bernays Lectures 2019 auftritt, drei Schlüsselfragen der theoretischen Informatik und Physik diskutieren.
 

1. Was können Computer überhaupt berechnen und inwiefern erweitern neue Erkenntnisse aus der Quantenphysik die Rechenfähigkeit von Computern?
2. Gibt es Probleme, die neuartige Computertypen wie die Quanten­com­puter schneller und effizienter berechnen als heutige Computer? Gibt es sogar bestimmte, besonders komplexe Probleme, die nur Quanten­computer oder andere zukünftige Computer lösen können?
3. Lassen sich überhaupt nützliche Quantencomputer herstellen, und was ist aktuell der Stand der verschiedenen Ansätze zum Bau eines Quanten­computers?

Aaronsons Überlegungen setzen bei den theoretischen Grundlagen und der «Church-Turing-These» an. Diese zentrale These der Computer­wis­sen­schaft geht auf die Mathematiker und Computerpioniere Alonzo Church (1903-1995) und Alan Turing (1912-1954) zurück. Stark vereinfacht besagt sie, dass alle Probleme, zu denen man sich intuitiv eine Lösung vorstellen und formulieren kann, auch auf einem Computer berechenbar sind. Damit sind im Prinzip alle Probleme, die heutige Computermodelle prinzipiell berechnen können, mit heutigen Computern auch wirklich lösbar.

Lösen Quantencomputer mehr Probleme?

Alle? Nicht ganz. Es gibt auch Probleme, die sich im Prinzip zwar durchaus berechnen und lösen lassen, ein Computer bräuchte aber viel zu viel Zeit, um sie zu berechnen. Solche Probleme, die Computer nicht innert nützlicher Frist lösen können, bezeichnen die Computerwissenschaftler als nicht effizient lösbar.

Typischerweise sind viele Erscheinungen der Quantenphysik heute nicht effizient berechenbar. Darum untersuchen sowohl Physiker als auch Informatiker, ob Quantencomputer mehr Probleme effizient lösen könnten als konventionelle. «Nach dem heutigen Stand des Wissens sind sich fast alle einig, dass Quantencomputer schneller rechnen als klassische. Beweisen konnte das aber noch niemand. Darum zählt diese Vermutung zu den grossen Fragen der Computerwissenschaft», sagt Renato Renner, der Scott Aaronson an den Paul Bernays Lectures vorstellt.

Es gibt Gegenargumente: Die Church-Turing-These sagt, dass alle lösbaren Probleme auf einem klassischen Computer lösbar sind. Ihre Er­wei­terung besagt, dass alle effizient lösbaren Probleme auch auf einem klassischen Computer effizient lösbar sind. Bekannt ist, dass ein klassischer Computer einen Quantencomputer simulieren kann – bloss nicht effizient.

Wenn es gelingt, auf einem klassischen Computer einen Quantencomputer effizient zu simulieren, dann könnte ein klassischer Computer dieselben Probleme lösen wie ein Quantencomputer – und dann könnte umgekehrt kein Quantencomputer grundsätzlich andere Probleme lösen als ein klassischer. Aaronson selbst argumentiert in die andere Richtung.

Verschlüsselung und Gravitation

Ein bekanntes Beispiel, bei dem man heute für klassische Computer keinen Algorithmus kennt, der das effizient berechnen kann, betrifft die Faktorisierung, also die Zerlegung einer grossen, zusammengesetzten Zahl in einzelne Teiler. «Im Fall des Faktorisierens gibt es jedoch Algo­rithmen, die dieses Problem effizient lösen können. Diese laufen aber nur auf einem Quantencomputer», sagt Renner. Da heutige Verschlüsselungs- und Sicherheitstechniken im Internet auf dem Faktorisierungsproblem beruhen, forscht Aaronson auch über die sicherheitsrelevanten externe Seite Implikationen von Quantencomputern.

Mit Blick auf die Zukunft des Computers denken Aaronson und Renner noch weiter: Vielleicht gibt es dereinst gar noch ganz andere Computer, die andere physikalische Phänomene nutzen als Quantenmechanik? Gravitationstheorie zum Beispiel. Dann liessen sich vielleicht sogar Probleme lösen, die nicht einmal Quantencomputer effizient lösen?