Erster Beweis, dass Quantencomputer überlegen sind

18.10.2018

Sie werden als die Computing-Verheißung der Zukunft gehandelt: Quantencomputer. Dass sie tatsächlich Vorteile gegenüber konventionellen Rechnern haben, haben ein Wissenschaftler der Technischen Universität München (TUM) und seine Kollegen von der University of Waterloo und der Firma IBM nun erstmals bewiesen.

16662697764 62ebb49652 o 900x675Px — Layout einer supraleitenden quadratischen Schaltkreisvorrichtung mit vier Qbits von IBM. (Bild: IBM Research, https://www.flickr.com/photos/ibm_research_zurich/16662697764/in/album-72157663611181258/)

Lange waren Quantencomputer nicht viel mehr als eine Idee. Jetzt investieren Konzerne, Länder und Geheimdienste in die Entwicklung der Quantentechnologie. In diesem zukunftsträchtigen Feld hat nun Robert König, Professor für die Theorie komplexer Quantensysteme an der TUM, gemeinsam mit David Gosset von der University of Waterloo und Sergey Bravyi von IBM eine wichtige Grundlage gelegt.

Weshalb sollen Quantencomputer schneller sein?

Konventionelle Computer folgen der klassischen Physik. Sie arbeiten mit binären Zahlen, mit 1 und mit 0. Die Zahlen werden gespeichert und für Rechenoperationen genutzt. Auf konventionellen Datenspeichern wird jedes Bit, also die kleinste Informationseinheit, durch einen mikroskopischen Punkt auf einem Mikrochip repräsentiert. Auf diesem Punkt kann elektrische Ladung deponiert werden, die darüber entscheidet, ob das Bit auf 1 oder 0 gestellt ist.

Bei einem Quantencomputer kann ein Bit hingegen zugleich 1 oder 0 sein. Denn nach den Regeln der Quantenphysik kann sich ein Elektron an mehreren Orten gleichzeitig aufhalten. Quantenbits, Qubits genannt, befinden sich deshalb in einem Überlagerungszustand. Dieses sogenannte Superpositionsprinzip ermöglicht es Quantencomputern, viele Zahlen gleichzeitig verarbeiten, während ein einzelner konventioneller Rechner typischerweise eine Rechenoperation nach der anderen ausführt. Das Versprechen des Quantencomputers lautet daher, dass er einige Aufgaben sehr viel schneller lösen kann.

Von der Vermutung zum Beweis

Den wasserdichten Beweis für die Überlegenheit des Quantencomputers liefern jetzt König und seine Kollegen. Sie entwickelten einen Quantenschaltkreis, der ein bestimmtes „schwieriges“ algebraisches Problem lösen kann. Der neue Schaltkreis ist einfach strukturiert: Er führt auf jedem Qubit nur eine bestimmte Anzahl an Operationen aus. Man sagt, er hat eine konstante Tiefe. Mit ihrer Arbeit zeigen die Forscher eindeutig, dass dieses bestimmte Problem von klassischen Schaltkreisen mit konstanter Tiefe nicht gelöst werden kann. Außerdem beantworten sie die Frage, warum der Quantenalgorithmus allen vergleichbaren klassischen Schaltkreisen überlegen ist: Der Quantenalgorithmus profitiert von der Nicht-Lokalität der Quantenphysik.

Zuvor konnte die Überlegenheit der Quantencomputer weder bewiesen noch experimentell gezeigt werden – obwohl es Indizien gab, wie den Quantenalgorithmus von Shor, der auf effiziente Weise das Problem der Primfaktorzerlegung löst. Dass dieses Problem ohne Quantencomputer nicht effizient lösbar ist, ist jedoch eine komplexitätstheoretische Annahme. Letztendlich wäre es in diesem Fall auch möglich, dass man die richtige Lösungsmethode mit klassischen Computern einfach noch nicht gefunden hat.

Ein Schritt auf dem Weg zum Quantencomputer

Robert König sieht die neuen Ergebnisse in erster Linie als Beitrag zur Komplexitätstheorie: „Unser Resultat belegt, dass Quanteninformationsverarbeitung tatsächlich Vorteile bringt – ohne dass man sich auf unbewiesene komplexitätstheoretische Vermutungen stützen muss“, sagt er. Darüber hinaus tun sich aber auch nächste Schritte auf dem Weg zum Quantencomputer auf. Aufgrund seiner einfachen Struktur ist der neue Quantenschaltkreis ein Kandidat, der bald die experimentelle Umsetzung von Quantenalgorithmen ermöglichen könnte.

Publikation:

S. Bravyi, D. Gosset, R. König: “Quantum advantage with shallow circuits”, Science, 19. Oktober 2018. DOI: 10.1126/science.aar3106

Mehr Informationen:

Die Ergebnisse fallen in München auf fruchtbaren Boden: In den letzten Jahren hat sich hier ein weltweit beachteter Forschungsschwerpunkt in den Quantentechnologien entwickelt. An der TUM in Garching entsteht ein Forschungsneubau für die Quantenforschung und im September erhielt die TUM gemeinsam mit der Ludwigs-Maximilians-Universität München (LMU) den Zuschlag für das Exzellenzcluster Munich Center for Quantum Science and Technology (MCQST).