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 ¨C 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 SeiteDiskussion unter ?Responsescall_made?). 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 SeiteKomplexonautencall_made? genannt, weil er sich bis zu den komplexesten Problemen vorwagt, um die prinzipiellen M?glichkeiten und Grenzen von Computern auszuloten ¨C 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 SeiteZoo der Kom?plexi?t?tencall_made? 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 ¨C 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 ¨C 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 SeiteImplikationen von Quantencomputerncall_made.

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?