Quantencomputer sind überlegen

Robert König und Team erbringen den Beweis

18. Oktober 2018

Quantencomputer sollen - indem sie Quanteneffekte nutzen - Probleme effizienter lösen als konventionelle Computer. Dies ist zumindest die Vision, die dem Gebiet des Quantencomputings zugrunde liegt. Dass sie tatsächlich überlegen sind, beweist nun ein Forscherteam. Es entwickelte einen Quantenschaltkreis, der ein schwieriges algebraisches Problem lösen kann.

Der Schaltkreis ist einfach strukturiert und hat eine konstante Tiefe. Dabei ist die Tiefe die Anzahl der Zeitschritte, die benötigt werden, um den Schaltkreis auszuführen. Jeder Zeitschritt umfasst Gatter, die sich gleichzeitig ausführen lassen. Konstante Tiefe bedeutet, dass die Tiefe nicht von der Größe des Inputs - also des Problems - abhängt.

Mit ihrer Arbeit "Quantum advantage with shallow circuits" schaffen Robert König, Professor für die Theorie komplexer Quantensysteme, David Gosset von der University of Waterloo und Sergey Bravyi von IBM eine wichtige Grundlage für die Quantentechnologie. Denn sie belegen, dass ein klassischer Schaltkreis mit konstanter Tiefe das betrachtete Problem nicht lösen kann - und liefern so den Beweis, dass ein Quantenalgorithmus überlegen ist. Gleichzeitig beantworten sie, warum das so ist: Der Quantenschaltkreis profitiert von der Nicht-Lokalität der Quantenphysik.

Warum Quantencomputer "besser" sind

Jedes Ausgabe-Bit eines klassischen Schaltkreises konstanter Tiefe ist bestimmt durch die Eingabe-Bits in seinem "Lichtkegel". Im Gegensatz dazu können Quantenschaltkreise konstanter Tiefe das Phänomen der Quanten-Nicht-Lokalität ausnutzen, um Berechnungen durchzuführen, die über die Fähigkeiten ihrer klassischen Gegenstücke hinausgehen.

Konventionelle Computer folgen der klassischen Physik. Sie arbeiten mit binären Zahlen: 1 und 0. Die kleinste Informationseinheit, ein Bit, kann etwa durch die Präsenz oder Absenz elektrischer Ladung an einer bestimmten Stelle codiert werden. Diese entscheidet darüber, ob das Bit auf 1 oder 0 gestellt ist.

Bei einem Quantencomputer kann ein Bit zugleich 1 oder 0 sein. Denn nach den Regeln der Quantenphysik kann sich ein Elektron an mehreren Orten gleichzeitig aufhalten. Quantenbits oder Qubits befinden sich deshalb in einem Überlagerungszustand. Dieses sogenannte Superpositionsprinzip ermöglicht es Quantencomputern, viele Zahlen gleichzeitig zu verarbeiten, während ein einzelner konventioneller Rechner eine Operation nach der anderen ausführt.

Bisher gab es nur Indizien für die Überlegenheit der Quantencomputer. Der Quantenalgorithmus von Shor etwa löst auf effiziente Weise das Problem der Primfaktorzerlegung. Dass dieses Problem nur mit einem Quantencomputer effizient gelöst werden kann, ist jedoch eine komplexitätstheoretische Annahme.

Der nächste Schritt 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". Darüber hinaus tun sich aber auch nächste Schritte auf dem Weg zum Quantencomputer auf. Aufgrund ihrer einfachen Struktur könnten die flachen Schaltkreise bald die experimentelle Umsetzung von Quantenalgorithmen ermöglichen.

In den letzten Jahren hat sich in München 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).

Zur Pressemeldung der TUM: Erster Beweis, dass Quantencomputer überlegen sind.