Schnelle klassische Simulation von Quantenalgorithmen

10

Gibt es Beispiele für Fälle, in denen die klassische Simulation eines Quantenalgorithmus für ein Problem den bisher bekanntesten klassischen Algorithmus für dieses Problem übertrifft? "Outperforms" muss nicht unterschiedliche Komplexitätsklassen bedeuten, es könnte einfach eine bessere Skalierung sein.

Diese Frage wurde durch den Fall einer effizienten klassischen Simulation eines Quantenempfehlungsalgorithmus inspiriert .

cc.complexity-theory quantum-computing quantum-information delete000
quelle
1
Ihre Frage macht wie gesagt keinen Sinn. Eine klassische Simulation eines Quantenalgorithmus ist eine bestimmte Art von klassischem Algorithmus, daher kann er nicht schneller sein als der beste klassische Algorithmus. Es könnte sein , die am schnellsten bekannten klassische Algorithmus, aber es kann nicht sein , besser da , dass es als selbst besser machen würde.
Craig Gidney
Ich denke, Sie meinten "Übertrifft den bisher bekanntesten klassischen Algorithmus"
Frédéric Grosshans
Ich dachte an diese Einschränkung, als ich die Frage las, aber ich erwartete, dass es offensichtlich sein würde, dass einer der beiden klassischen Algorithmen eine "zuvor bekannte" Nicht-Simulation des Quantenalgorithmus sein würde. Ich weiß es jetzt besser.
delete000

Antworten:

6

Ihre Frage wurde von dem jüngsten quanteninspirierten klassischen Fortschritt im Empfehlungsalgorithmus inspiriert. Beachten Sie, dass es nicht die erste Zeit ist, in der so etwas passiert. Im Jahr 2015 gab es ähnliche Entwicklungen mit dem ungefähren MAX3LIN : Ein Quanutm-Algorithmus, der alle bisher bekannten klassischen Algorithmen übertraf, motivierte eine erfolgreiche Suche nach einem besseren klassischen Algorithmus. Soweit ich weiß, sehen die klassischen Algorithmen in beiden Fällen jedoch nicht wie eine klassische Simulation einer Quantenentwicklung aus.

Ich kenne einen Artikel, der eine klassische Simulation eines Quantensystems beschreibt, mit dem bisher bekannte Algorithmen übertroffen werden können (vollständige Offenlegung: Die Autoren sind Freunde von mir) :

Ein quanteninspirierter Algorithmus zur Schätzung der Permanente positiver semidefiniter Matrizen von L. Chakhmakhchyan, NJ Cerf, R. Garcia-Patron, arXiv: 1609.02416 / Phys. Rev. A 96 , 022329

Dies basiert auf der Verbindung zwischen der permanenten und der Quantenoptik, die durch Boson-Sampling gezeigt wird . Im Gegensatz zum üblichen Ansatz betrachten sie Zustände, von denen bekannt ist, dass sie leicht zu simulieren sind (thermische Zustände), und verwenden diese Simulation, um eine Monte-Carlo-Berechnung der permanenten hermitischen positiven semidefiniten Matrizen durchzuführen. Für einige Klassen von Matrizen bietet dieser Algorithmus eine bessere Annäherung als der bisher bekannteste Algorithmus (Gurvits-Algorithmus).

Frédéric Grosshans
quelle