Studie belegt die Schwierigkeit, Zufallsquantenschaltungen für klassische Computer zu simulieren

Quantencomputer, also Technologien, die Berechnungen unter Nutzung quantenmechanischer Phänomene durchführen, könnten bei vielen komplexen Rechen- und Optimierungsproblemen letztendlich die Leistung klassischer Computer übertreffen. Während einige Quantencomputer bei einigen Aufgaben bemerkenswerte Ergebnisse erzielt haben, muss ihr Vorteil gegenüber klassischen Computern noch schlüssig und konsistent nachgewiesen werden.

Ramis Movassagh, ein Forscher bei Google Quantum AI und früher bei IBM Quantum, führte kürzlich eine theoretische Studie durch, die darauf abzielte, die bemerkenswerten Vorteile von Quantencomputern mathematisch zu demonstrieren. Sein Artikel, veröffentlicht in Naturphysikzeigt mathematisch, dass die Simulation zufälliger Quantenschaltkreise und die Schätzung ihrer Ergebnisse für klassische Computer so genannt #P-schwer (d. h. sehr schwierig) ist.

„Eine zentrale Frage im Bereich der Quantenberechnung ist: Sind Quantencomputer exponentiell leistungsfähiger als klassische?“ Ramis Movassagh, der die Studie durchgeführt hat, sagte gegenüber Phys.org. „Die Vermutung über die Quantenüberlegenheit (die wir in Quantenüberlegenheitsvermutung umbenannt haben) sagt ja. Allerdings war es mathematisch gesehen ein großes offenes Problem, das rigoros festgestellt werden musste.“

Forscher versuchen in letzter Zeit auf verschiedene Weise, sowohl durch theoretische als auch experimentelle Studien, die Vorteile von Quantencomputern gegenüber klassischen Computern aufzuzeigen. Ein Schlüssel, um dies mathematisch zu beweisen, wäre der Nachweis, dass es für klassische Computer schwierig ist, die Ergebnisse von Quantencomputern mit hoher Präzision und kleinen Fehlermargen zu erreichen.

„Im Jahr 2018 hielt ein Kollege am MIT einen Vortrag über ein damals aktuelles Ergebnis, das Beweise für die Härte des Random Circuit Sampling (RCS) liefern wollte“, erklärte Movassagh. „RCS ist die Aufgabe, Stichproben aus dem Ausgang eines zufälligen Quantenschaltkreises zu ziehen, und Google hatte es gerade als Hauptkandidaten für den Nachweis des Quantenprimats vorgeschlagen. Ich war im Publikum und hatte noch nie zuvor an Quantenkomplexität gearbeitet; tatsächlich erinnere ich mich daran Als Student habe ich mir sogar geschworen, nie in diesem Bereich zu arbeiten!“

Der mathematische Beweis, den Movassaghs Kollege 2018 am MIT vorlegte, löste das seit langem bestehende Problem des Nachweises des Quantenprimats nicht endgültig, war aber ein erheblicher Fortschritt in Richtung dieses Ziels. Der Beweis wurde durch eine Reihe von Näherungen und die sogenannte Reihentrunkierung erbracht; Daher war es eher indirekt und führte zu unnötigen Fehlern.

„Ich liebe es, Mathematik zu überbrücken, um große offene Probleme zu lösen, besonders wenn die Mathematik direkt ist, den Experten auf diesem Gebiet weniger bekannt und schön ist“, sagte Movassagh. „In diesem Fall hatte ich das Gefühl, dass ich wahrscheinlich einen besseren Beweis finden könnte, und dachte naiv, dass ich das große offene Problem vielleicht lösen könnte, wenn ich das Problem richtig löse. Also machte ich mich daran, daran zu arbeiten.“

Der von Movassagh vorgelegte mathematische Beweis unterscheidet sich erheblich von den bisher eingeführten. Es basiert auf einer Reihe neuer mathematischer Techniken, die zusammen zeigen, dass die Ausgabewahrscheinlichkeiten eines Durchschnittsfalls (dh eines zufälligen Quantenschaltkreises) genauso hart sind wie die des schlimmsten Falles (dh des am meisten erfundenen).

„Die Idee ist, dass man den in der Arbeit vorgeschlagenen Cayley-Pfad verwenden kann, um zwischen zwei beliebigen Schaltkreisen zu interpolieren, was in diesem Fall als zwischen dem Worst-Case und dem Durchschnittsfall angenommen wird“, sagte Movassagh. „Der Cayley-Pfad ist eine algebraische Funktion niedrigen Grades. Da der schlimmste Fall bekanntermaßen #P-schwer ist (d. h. ein sehr schwieriges Problem), kann man mit dem Cayley-Pfad auf den Durchschnittsfall interpolieren und zeigen, dass die Zufallsschaltungen vorliegen sind im Wesentlichen so schwer wie der schlimmste Fall mit hoher Wahrscheinlichkeit.“

Im Gegensatz zu anderen in der Vergangenheit abgeleiteten mathematischen Beweisen beinhaltet Movassaghs Beweis keine Näherungen und ist ziemlich direkt. Dies bedeutet, dass es Forschern ermöglicht, beteiligte Fehler explizit zu begrenzen und ihre Robustheit (dh ihre Fehlertoleranz) zu quantifizieren.

Seit Movassagh den Beweis erstmals erbracht hat, haben ihn sowohl seine Forschungsgruppe als auch andere Teams weiter getestet und seine Robustheit verbessert. Es könnte daher bald in weitere Studien einfließen, die darauf abzielen, den Beweis zu verbessern oder ihn zu nutzen, um das Potenzial von Quantencomputern hervorzuheben.

„Wir haben direkte Beweise für die Härte der Schätzung der Ausgabewahrscheinlichkeiten von Quantenschaltkreisen erbracht“, sagte Movassagh. „Diese stellen Rechenbarrieren für die klassische Simulation von Quantenschaltkreisen dar. Die neuen Techniken wie der Cayley-Pfad und die rationale Funktionsversion von Berlekemp-Welch.“ sind von unabhängigem Interesse für Quantenkryptographie, Berechnung und Komplexität sowie Kodierungstheorie. Derzeit ist dies der vielversprechendste Weg zur eventuellen Widerlegung der Extended-Church-Turing-These, die ein zwingendes Ziel der Quantenkomplexitätstheorie ist.“

Die jüngste Arbeit von Movassagh ist in hohem Maße ein wichtiger Beitrag zu den laufenden Forschungsbemühungen, die die Vorteile von Quantencomputern gegenüber klassischen Computern untersuchen. In seinen zukünftigen Studien möchte er auf seinen aktuellen Beweisen aufbauen, um das enorme Potenzial von Quantencomputern zur Lösung spezifischer Probleme mathematisch zu demonstrieren.

„In meinen nächsten Studien hoffe ich, diese Arbeit mit der Komplexität anderer Aufgaben zu verbinden, um die (Un)lenkbarkeit von Quantensystemen besser abzubilden“, fügte Movassagh hinzu. „Ich untersuche die Anwendungen dieser Arbeit unter anderem in der Quantenkryptographie. Und nicht zuletzt hoffe ich, die Quantenprimatsvermutung zu beweisen und zu beweisen, dass die Extended Church-Turing-These falsch ist!“

© 2023 Science X Network