A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics

Technische Zusammenfassung: Polynomialzeitliche klassische Stichprobenverfahren für verrauschte Quantenschaltkreise

Problemstellung
Die vorliegende Arbeit befasst sich mit der Herausforderung, die Grenzen des Quantenvorteils in Gegenwart von Rauschen zu bestimmen. Während ideale Quantencomputer das Potenzial haben, klassische Computer exponentiell zu übertreffen, unterliegen experimentelle Geräte einem Rauschen, das die Rechenleistung typischerweise degradiert. Bestehende klassische Simulationsmethoden für allgemeine verrauschte Schaltkreise erfordern im Allgemeinen, dass die Tiefe des Schaltkreises super-logarithmisch mit der Systemgröße wächst ($d \sim \omega(\log n)$), damit das Rauschen den globalen Zustand in eine triviale, uniforme Verteilung überführt. Eine entscheidende offene Frage bleibt: Können verrauschte Quantenschaltkreise bei Tiefen, die unabhängig von der Systemgröße sind (konstante Tiefe), klassisch simulierbar sein, sofern die Rauschstärke ungleich Null ist? Insbesondere untersuchen die Autoren, ob ein „Worst-Case“-verrauschter, geometrisch lokaler Quantenschaltkreis klassisch simulierbar wird, bevor die Ausgabeverteilung gegen Uniformität konvergiert.

Methodik
Die Autoren entwickeln einen neuartigen klassischen Stichprobenalgorithmus, der Techniken der statistischen Mechanik und der Quanteninformationstheorie kombiniert. Die Kernmethodik umfasst drei Hauptschritte:

1. Abbildung auf Polymer-Modelle:
   Die Autoren bilden die Randwahrscheinlichkeiten der Ausgabeverteilung des verrauschten Quantenschaltkreises auf die Partitionsfunktion eines abstrakten Polymer-Modells in der statistischen Mechanik ab.

   • Sie zerlegen das Gitter in grobkörnige Blöcke der Seitenlänge $2d$.
   • Sie definieren „Polymere“ als verbundene Mengen dieser Blöcke.
   • Das Gewicht eines Polymers wird über die Heisenberg-Evolution von Pauli-Observablen definiert, die auf den Support dieses Polymers beschränkt sind.
   • Aufgrund der geometrischen Lokalität des Schaltkreises besitzen nicht benachbarte Blöcke disjunkte rückwärts gerichtete Lichtkegel, was es ermöglicht, die Partitionsfunktion in eine Summe über kompatible (nicht überlappende und nicht benachbarte) Polymer-Konfigurationen zu faktorisieren.

2. Abgeschnittene Cluster-Expansion:
   Um die Partitionsfunktion (und damit die Log-Randwahrscheinlichkeiten) zu berechnen, verwenden die Autoren eine Cluster-Expansion. Bei dieser Technik wird das Logarithmus der Partitionsfunktion als Summe über „Cluster“ von Polymeren expandiert.

   • Der Algorithmus schneidet diese Expansion ab, indem er nur über Cluster summiert, die auf $O(\log n)$ Blöcken gestützt sind.
   • Die Genauigkeit dieser Approximation beruht auf der Eigenschaft des „Gewichtsabfalls“ (Weight Decay): Der Beitrag eines Polymers muss exponentiell mit seiner Größe (Anzahl der Blöcke) abfallen.

3. Nachweis des Gewichtsabfalls mittels Hyperkontraktivität:
   Der zentrale technische Beitrag besteht im Nachweis, dass die Polymergewichte exponentiell abfallen, wenn die Tiefe $d$ des Schaltkreises einen kritischen Schwellenwert oberhalb der Systemgröße überschreitet.

   • Die Autoren nutzen Quanten-Hyperkontraktivität und $\ell_2$-Norm-Kontraktions-Bounds für depolarisierende Kanäle.
   • Sie konstruieren einen Pfad von Norm-Konversionen: ausgehend von der $\ell_\infty$-Norm, über $\ell_{1+(4d)^D}$ und $\ell_2$-Normen, um schließlich zur $\ell_1$-Norm zurückzukehren.
   • Durch Anwendung der Hyperkontraktivität beim Übergang zwischen den Normen und unter Verwendung der Kontraktivität des depolarisierenden Kanals (Fakt 5.2) zeigen sie, dass sich das Rauschen lokal akkumuliert. Da das System geometrisch lokal ist, kann die durch das Rauschen eingeführte Entropie (die mit dem Volumen skaliert) nicht so schnell entweichen, wie sie erzeugt wird (skaliert mit der Oberfläche), was zu einer lokalen Hochtemperaturphase führt, in der Korrelationen exponentiell abfallen.

Wichtigste Ergebnisse
Die Arbeit etabliert das folgende Haupttheorem (informell):

• Theorem: Für jeden geometrisch lokalen Quantenschaltkreis, bestehend aus unitären Operationen mit ein-Qubit-Depolarisierungsrauschen der Stärke $p$, das nach jeder Schicht angewendet wird, existiert ein Algorithmus in Polynomialzeit, der aus der Ausgabeverteilung mit invers-polynomialer Total Variation Distance (und relativer Fehlerrate für Randwahrscheinlichkeiten) stichprobenartig ziehen kann, sofern die Tiefe $d$ des Schaltkreises gilt:
  $$d > d_{crit} = O(p^{-1} \log p^{-1})$$
• Algorithmische Fähigkeit: Der bereitgestellte Algorithmus ist ein Fully Polynomial-Time Approximation Scheme (FPTAS) für beliebige Randwahrscheinlichkeiten der Ausgabeverteilung. Er erreicht die Stichprobenziehung mit relativer Fehlerrate – eine Aufgabe, die für rauschfreie Schaltkreise und für verrauschte Schaltkreise unterhalb des $O(p^{-1})$-Tiefe-Schwellenwerts als klassisch schwer gilt.
• Komplexitätsregime: Das Ergebnis identifiziert ein neues Regime in der Komplexitätslandschaft verrauschter Schaltkreise. Während vorangegangene Arbeiten zeigten, dass die Härte bis zu Tiefen von $O(p^{-1})$ besteht und die Simulierbarkeit bei Tiefen, die mit $\log n$ (oder $\omega(\log n)$) skalieren, gegeben ist, beweist diese Arbeit die Simulierbarkeit bei konstanter Tiefe (unabhängig von $n$), sobald die Tiefe $O(p^{-1} \log p^{-1})$ überschreitet.

Bedeutung und Ansprüche
Die Autoren betonen, dass ihre Arbeit eine fundiertere Begründung dafür liefert, warum nicht-unitäre oder nicht-lokale Ressourcen (wie etwa Mid-Circuit-Messungen mit Feedback oder Qubit-Resets) fundamental notwendig sind, um Schaltkreistiefen zu erreichen, die mit der Systemgröße skalieren.

• Quanten-zu-Klassik-Übergang: Die Arbeit interpretiert das Ergebnis als einen „Quanten-zu-Klassik-Übergang“, der durch die Akkumulation von Wärme (Entropie) in offenen Quantensystemen getrieben wird. Es wird postuliert, dass das System ohne ein Niedrigtemperatur-Bad, das Wärme ableiten kann (d. h. ohne nicht-unitäre Operationen), nach einer kritischen Tiefe natürlich in eine klassisch simulierbare Hochtemperaturphase übergeht.
• Schärfe (Tightness): Die Autoren merken an, dass ihre Schranke bis auf logarithmische Faktoren scharf ist, da die Stichprobenziehung mit relativer Fehlerrate für Tiefen unter $O(p^{-1})$ als schwer bewiesen ist.
• Generalität: Das Ergebnis gilt für beliebige geometrisch lokale Quantenschaltkreise mit unitären Operationen und Depolarisierungsrauschen und subsumiert bisherige Arbeiten, die auf eingeschränkte Gate-Sets oder spezifische Rauschmodelle beschränkt waren.
• Philosophischer Kontext: Die Arbeit adresst die rechnerische Komplexität offener Quantensysteme „an sich selbst“ und legt nahe, dass die natürliche Dynamik verrauschter Vielteilchensysteme einen Übergang zur Klassizität aufweist, der unter Verwendung statistisch-mechanischer Werkzeuge rigoros charakterisiert werden kann.

Die Arbeit beansprucht nicht, spezifische experimentelle Geräte zu simulieren oder neue Hardware vorzuschlagen; vielmehr liefert sie eine theoretische Grenze für die Simulierbarkeit einer breiten Klasse verrauschter Quantendynamiken und deutet darauf hin, dass der „Quantenvorteil“ in solchen Systemen fragil ist und auf geringe Tiefen begrenzt bleibt, sofern keine spezifischen nicht-unitären Fehlerkorrekturmechanismen eingesetzt werden.