Studie beweist die Schwierigkeit der Simulation zufälliger Quantenschaltungen für klassische Computer.

6. September 2023 Merkmale

Dieser Artikel wurde gemäß dem Redaktionsprozess und den Richtlinien von Science X überprüft. Die Editoren haben die folgenden Merkmale hervorgehoben, um die Glaubwürdigkeit des Inhalts sicherzustellen:

• Faktengestützt
• Peer-reviewed Veröffentlichung
• Vertrauenswürdige Quelle
• Korrekturgelesen

von Ingrid Fadelli, Phys.org

Quantencomputer, Technologien, die Berechnungen unter Ausnutzung quantenmechanischer Phänomene durchführen, könnten letztendlich klassische Computer bei vielen komplexen rechenintensiven und Optimierungsproblemen übertreffen. Während einige Quantencomputer auf einigen Aufgaben bemerkenswerte Ergebnisse erzielt haben, ist ihr Vorteil gegenüber klassischen Computern noch nicht abschließend und konsistent nachgewiesen worden. 

Ramis Movassagh, ein Forscher bei Google Quantum AI, der früher bei IBM Quantum tätig war, hat kürzlich eine theoretische Studie durchgeführt, um die bemerkenswerten Vorteile von Quantencomputern mathematisch nachzuweisen. In seiner Veröffentlichung in Nature Physics zeigt er mathematisch, dass das Simulieren zufälliger Quantenschaltungen und das Schätzen ihrer Ausgänge für klassische Computer (sogenanntes #P-schwer) sehr schwierig sind.

"Eine Schlüsselfrage im Bereich der Quantenberechnung lautet: Sind Quantencomputer exponentiell leistungsfähiger als klassische Computer?" sagte Ramis Movassagh, der die Studie durchgeführt hat, zu Phys.org. "Die Quantenüberlegenheitsvermutung (die wir in Quantenprimatsvermutung umbenannt haben) besagt ja. Mathematisch gesehen ist es jedoch ein großes ungelöstes Problem, dies rigoros zu beweisen."

Forscher haben in letzter Zeit versucht, die Vorteile von Quantencomputern gegenüber klassischen Computern auf verschiedene Weisen zu demonstrieren, sowohl durch theoretische als auch experimentelle Studien. Ein Schlüssel für den mathematischen Nachweis wäre es, zu beweisen, dass es für klassische Computer schwer ist, die Ergebnisse von Quantencomputern mit hoher Präzision und kleinen Fehlerraten zu erreichen.

"2018 hat ein Kollege einen Vortrag am MIT gehalten, der damals ein kürzliches Ergebnis vorstellte, das versuchte, Belege für die Schwierigkeit des Sampling zufälliger Schaltungen (RCS) zu liefern", erklärte Movassagh. "RCS ist die Aufgabe, aus der Ausgabe einer zufälligen Quantenschaltung Proben zu ziehen und Google hatte sie gerade als Hauptkandidat für den Nachweis von Quantenprimat vorgeschlagen. Ich war im Publikum und hatte zuvor noch nie mit Quantenkomplexität gearbeitet; eigentlich habe ich als Doktorand sogar geschworen, dass ich nie in diesem Bereich arbeiten würde!"

Der mathematische Beweis, den Movassaghs Kollege 2018 am MIT präsentierte, löste das langjährige Problem der Demonstration des Quantenprimats nicht abschließend, war aber ein beträchtlicher Fortschritt in Richtung dieses Ziels. Der Beweis wurde durch eine Reihe von Approximationen und sogenannte Reihenabschneidungen erreicht; er war also etwas indirekt und führte zu unnötigen Fehlern.

"Ich liebe es, Mathematik zu nutzen, um große offene Probleme zu lösen, besonders wenn die Mathematik direkt ist, den Experten auf diesem Gebiet weitgehend unbekannt ist 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, wenn ich das Problem richtig lösen würde, das große offene Problem lösen könnte. Also habe ich mich daran gemacht, daran zu arbeiten."

Der von Movassagh vorgestellte mathematische Beweis unterscheidet sich stark von den bisherigen. Er basiert auf einer neuen Reihe von mathematischen Techniken, die gemeinsam zeigen, dass die Wahrscheinlichkeiten der Ausgänge eines durchschnittlichen Falls (d. h. zufällige Quantenschaltung) genauso schwierig sind wie der schlechteste Fall (d. h. am konstruiertesten).

"Die Idee ist, dass man den im Artikel vorgeschlagenen Cayley-Pfad verwenden kann, um zwischen zwei beliebigen Schaltungen zu interpolieren, was in diesem Fall zwischen dem schlechtesten Fall und dem Durchschnittsfall liegt", erklärte Movassagh. "Der Cayley-Pfad ist eine algebraische Funktion niedrigen Grades. Da der schlechteste Fall als #P-schwer gilt (also ein sehr schweres Problem), kann man mit Hilfe des Cayley-Pfads zum Durchschnittsfall interpolieren und zeigen, dass die zufälligen Schaltungen im Wesentlichen genauso schwierig sind wie der schlechteste Fall mit hoher Wahrscheinlichkeit."

Im Gegensatz zu anderen bisher abgeleiteten mathematischen Beweisen beinhaltet Movassaghs Beweis keine Approximationen und ist ziemlich direkt. Das bedeutet, dass er es den Forschern ermöglicht, die auftretenden Fehler explizit zu begrenzen und ihre Robustheit zu quantifizieren (d. h. ihre Toleranz gegenüber Fehlern).

Seit Movassagh den Beweis entwickelt hat, wurde er sowohl von seiner Forschungsgruppe als auch von anderen Teams weiter getestet und seine Robustheit verbessert. Damit könnte er bald zusätzliche Studien informieren, die darauf abzielen, den Beweis zu verbessern oder ihn zu nutzen, um das Potenzial von Quantencomputern zu verdeutlichen.

'We realized direct proofs of the hardness of estimating the output probabilities of quantum circuits,' Movassagh said, 'These provide computational barriers for the classical simulation of quantum circuits. The new techniques such as the Cayley path and rational function version of Berlekamp-Welch are of independent interest for quantum cryptography, computation and complexity, and coding theory. Currently, this is the most promising path toward eventual refutation of Extended-Church Turing thesis, which is an imperative goal of quantum complexity theory.'

The recent work by Movassagh greatly is a key contribution to ongoing research efforts exploring the advantages of quantum computers over classical computers. In his future studies, he plans to build on his current proof to mathematically demonstrate the huge potential of quantum computers for tackling specific problems.

'In my next studies, I hope to bridge this work to the hardness of other tasks to better map out the (in)tractability of quantum systems,' Movassagh added. 'I am investigating the applications of this work in quantum cryptography among others. And last but not least, I hope to prove the quantum primacy conjecture and prove that the Extended Church-Turing thesis is false!'

Journal information: Nature Physics

© 2023 Science X Network