Theoretischer Beweis: Quantencomputer sind (manchmal) besser als klassische Rechner

Anbieter zum Thema

TUM

IBM Deutschland GmbH

ET System electronic GmbH

MES Electronic Connect GmbH & Co. KG

Keysight Technologies Deutschland GmbH

Bislang wurde immer nur angenommen, dass Quantencomputer besser sind. Ein effektiver Beweis fehlte bislang aber noch. Nun haben Forscher von IBM und der TU München mathematisch bewiesen, dass Quantencomputer bei bestimmten Problemen schneller sind als ein klassischer Computer.

Die praktische Anwendbarkeit echter Quantencomputer rückt immer mehr in greifbare Nähe. Auch wenn es zu einer kommerziellen Realisierung eines Quantenrechners laut Experten noch fünf bis 10, nach einigen Einschättzungen sogar wenigstens noch 25 Jahre dauern wird, ist diese Rechnerform schon längst kein reines theoretisches Thema mehr. Namhafte Konzerne wie IBM, Google, Intel und Microsoft beschäftigen sich bereits intensiv mit der Fertigung von Prozessoren oder Programmiersprachen für Quantencomputer.

Aber um das Versprechen des Quantencomputings vollständig zu verwirklichen, wird es noch einige Jahre Forschung und wissenschaftliche Durchbrüche erfordern. Und tatsächlich bleibt abzuwarten, ob Quantencomputer dem Hype jemals gerecht werden. Nun existiert allerdings zumindest auf mathematischer Ebene erstmals ein Beweis, dass es in der Tat Berechnungen gibt, die Quantencomputer schneller abarbeiten können als jeder klassische Computer.

Mathematischer Nachweis für die Leistung von Quantencomputern erbracht

Im Fachmagazin Science erschien nun ein Paper ( „Quantum advantage with flat circuits“) von Sergey Bravyi von IBM Research, David Gosset vom Institute for Quantum Computing der University of Waterloo und Robert König vom Institute for Advanced Study und dem Zentrum Mathematik der Technischen Universität München. In diesem Beitrag beweisen die Forscher, dass ein Quantencomputer mit einer festen Schaltungstiefe in der Lage ist, einen klassischen Computer zu übertreffen, der das gleiche Problem anpackt, weil der klassische Computer benötigt, dass die Schaltungstiefe größer wird, während sie für den Quantencomputer konstant bleiben kann.

„Quantenschaltungen sind nicht nur im Grunde genommen gleich wie, sondern unterscheiden sich auch von klassischen Schaltungen“, sagt IBM Q Ecosystem und Strategy VP Bub Sutor gegenüber dem Online-Portal Techcrunch. „Klassische Schaltungen, [....] sind Bits, Nullen und Einsen, und es gibt binäre Logik, ANDs, ORs, NOTs und dergleichen. Die sehr, sehr einfachen Gatesätze, die Arten von Operationen, die man im Quantum durchführen kann, sind unterschiedlich. Wenn diese Qubits tatsächlich funktionieren, haben Sie mit diesem Begriff der Überlagerung viel, viel mehr, um den Ellbogenraum zu bedienen, nicht nur zwei Bits. Man hat hier tatsächlich eine enorme Menge mehr Platz.“ Und es sei dieser zusätzliche Raum, den man bekommt, denn Qubits können jede beliebige Zahl kodieren und nicht nur Nullen und Einsen, was es ihnen ermöglicht, leistungsfähiger zu sein als ein klassischer Computer, um die spezifische Art von Problem zu lösen, das die Forscher angegangen sind.

Sind Quantenschaltungen für komplexe Berechnungen wirklich besser?

Die Frage, die die Forscher hier stellten, war, ob Quantenschaltungen mit konstanter Tiefe ein Rechenproblem lösen können, das klassische Schaltungen mit konstanter Tiefe nicht lösen können? Das Problem, das sie sich anschauten, ist eine Variation des bekannten Bernstein-Vazirani-Problems, ein gerade im Quantencomputing immer wieder zitiertes Theorem zur Bestimmung der Komplexitätsklasse BQP (bounded error quantum polynomial time).

Um den Nachweis zu erbringen, dass Quantencomputern klassischen Rechnern hier überlegen sind, entwickelten die Forscher einen „einfach strukturierten“ Quantenschaltkreis: Dieser führt auf jedem Qubit nur eine bestimmte Anzahl an Operationen aus; er hat damit eine „konstante Tiefe“. Mit ihrer Arbeit zeigen die Forscher, 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. „Unser Resultat belegt, dass Quanteninformationsverarbeitung tatsächlich Vorteile bringt – ohne dass man sich auf unbewiesene komplexitätstheoretische Vermutungen stützen muss“, sagt Robert König, Professor für die Theorie komplexer Quantensysteme an der TUM.

Qubits sind nicht perfekt, da sie geringe Fehlerraten haben und nur für eine bestimmte Zeit existieren, bevor sie chaotisch werden. Dies wird als Kohärenzzeit bezeichnet, und es bedeutet, dass nur so viele Operationen durchgeführt werden können, bevor das Zeitlimit erreicht ist. Die Anzahl der durchgeführten Operationen ist die Tiefe, und die Gesamttiefe einer Quantenschaltung ist das Minimum aller Tiefen pro Qubit. Die Mathematik beweist, dass bestimmte Probleme nur eine feste Schaltetiefe benötigen, wenn sie auf einem Quantencomputer durchgeführt werden, egal wie die Anzahl der Eingänge zunimmt, während ein klassischer Computer verlangt, dass die Schaltetiefe größer wird, wenn die Eingänge für dasselbe Problem zunehmen.

Diese begrenzte Tiefe bedeutet, dass IBM-Wissenschaftler am meisten daran interessiert sind, was mit „short-depth“ Schaltungen gemacht werden kann, da sie praktisch für die Implementierung von Quantenalgorithmen sind und die Demonstration von Quantencomputing einen Vorteil gegenüber einem klassischen Ansatz hat. Der mathematische Beweis zeigt, dass fehlertolerante Quantencomputer einige Dinge besser können als klassische Computer - wenn auch nicht alle.

Quantencomputing hat noch einen lagen Weg vor sich

Die Forscher betonen, dass der erbrachte Beweis nur einen ersten, grundlegenden Schritt darstellt, als Beweis der Komplexitätstheorie. Sutor bestätigt, dass es wichtig sei, die an Erwartungen Quantencomputing noch ein wenig zu zügeln. Der bis dato stärkste Quantenprozessor bringt derzeit noch eine Leistung von 49 Qubits. Ernsthafte Anwendungen mit Quantencomputern würden dagegen eine Leistung von mindestens 1000 Qubits erfordern. Vor einer „Krypto-Apokalypse“, die auf einen Schlag alle derzeit gängigen Verschlüsselungsmethoden wirkungslos machen würde, seien wir demnach noch weit entfernt; laut Sutor wären dafür Quantenprozessoren mit 100 Millionen Qubits oder mehr nötig.

Post-Quantum-Kryptographie auf Embedded Systemen

Microsoft veröffentlicht Preview-Version eines Quantencomputer-Software-Kits

Rechnen mit Qubits: So arbeitet ein Quantencomputer

Wie programmiert man einen Quantenrechner?

(ID:45566998)