Quantencomputer beweist Überlegenheit Quantenschaltkreis rechnet klassischen PC an die Wand

Die Zukunft rechnet in Quanten: Schon lange schwören IT-Experten und Physiker auf die Quantentechnologie, wenn es um die Weiterentwicklung von Computern geht. Praktische Beweise für die Überlegenheit solcher Rechner fehlten aber bisher. Nun hat ein Team um Forscher der Technischen Universität München erstmals experimentell gezeigt, wie ein Quantencomputer einen herkömmlichen PC ausstechen kann.

München – Lange waren Quantencomputer nicht viel mehr als eine Idee. Jetzt investieren Konzerne und Länder 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.

1 oder 0? ... 1 und 0! – Rechnen mit Quanten

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 so genannte Superpositionsprinzip ermöglicht es Quantencomputern, viele Zahlen gleichzeitig zu 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.

Erstmals bewiesen: Überlegenheit des Quantenalgorithmus

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.

Schritte auf dem Weg zum Quantencomputer

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.

Originalpublikation: S. Bravyi, D. Gosset, R. König: Quantum advantage with shallow circuits. Science, 19 Oct 2018: Vol. 362, Issue 6412, pp. 308-311; DOI: 10.1126/science.aar3106

* L. Pietrzyk, Technische Universität München, 80333 München

(ID:45556312)