Complexity of detecting large coefficients in the Pauli basis

Technische Zusammenfassung: Komplexität der Detektion großer Koeffizienten in der Pauli-Basis

Problemdefinition
Diese Arbeit befasst sich mit dem rechnerischen Problem zu entscheiden, ob ein Quantenzustand $\rho$, der durch einen kompakten Quantenschaltkreis $C$ präpariert wurde, einen „großen“ Koeffizienten in der Pauli-Basis besitzt. Formal gilt: Gegeben sei ein Zustandspräparationsschaltkreis $C$ und ein Schwellenwert $\epsilon > 0$, ist zu entscheiden, ob es eine Nicht-Identitäts-Pauli-Matrix $P \in \mathcal{P}_n \setminus \{I^{\otimes n}\}$ gibt, sodass $|\text{Tr}(P\rho)| \ge \epsilon$. Das Problem ist als Entscheidungsproblem (Promise Problem) formuliert: Der Algorithmus muss „Ja“ zurückgeben, wenn ein solches $P$ existiert, und „Nein“, wenn für alle Nicht-Identitäts-Pauli-Matrizen $P$ gilt, dass $|\text{Tr}(P\rho)| \le \epsilon/2$. Der Zustand $\rho$ ist als partieller Trace eines durch $C$ erzeugten reinen Zustands definiert, wobei die Arbeit auch den Fall betrachtet, in dem $\rho$ rein ist (keine Qubits verworfen).

Methodik
Die Kernmethodik umfasst eine Komplexitätstheoretische Reduktion vom $\lambda$-Gap Minimum-Weight Codeword ($\lambda$-GapMWC) Problem, einem bekannten schwierigen Problem für klassische lineare Codes.

1. Reduktionskonstruktion: Die Autoren konstruieren eine Abbildung von einer Instanz $(G, t)$ von $\lambda$-GapMWC (wobei $G$ eine Generatormatrix und $t$ ein Schwellenwert ist) auf eine Instanz des Large Pauli Coefficient (LPC) Problems.

   • Sie definieren eine Zufallsvariable $V$, die durch gleichmäßige Stichproben aus einer gepufferten Version von $G$ erzeugt wird.
   • Sie konstruieren eine Dichtematrix $\rho_{G,t}$ als Erwartungswert von $|V\rangle\langle V|$ über $k$ unabhängige Kopien von $V$, wodurch effektiv ein diagonaler Zustand in der Rechenbasis erzeugt wird.
   • Unter Verwendung von Lemma 3.2 etablieren sie eine direkte algebraische Verbindung zwischen dem Hamming-Gewicht von Codewörtern $xG$ und den Erwartungswerten diagonaler Pauli-Operatoren $Z^x$ auf $\rho_{G,t}$:
     $$\text{Tr}(Z^x \rho_{G,t}) = \left(1 - \frac{2\text{wt}(xG)}{N}\right)^k$$
   • Durch eine sorgfältige Wahl der Parameter $N$ (Padding-Größe) und $k$ (Anzahl der Stichproben) stellen sie sicher, dass, falls ein Codewort mit Gewicht $\le t$ existiert, der entsprechende Pauli-Erwartungswert $\epsilon$ überschreitet, während falls alle Codewörter ein Gewicht $> \lambda t$ haben, alle Erwartungswerte unter $\epsilon/2$ bleiben.

2. Erweiterung auf reine Zustände: Um den Fall zu adressieren, in dem $\rho$ ein reiner Zustand sein muss, verwenden die Autoren eine „Hiding“-Technik. Sie nutzen einen unitären Operator $U$ (der durch Konzentrationsargumente in Lemma 3.3 und 3.4 garantiert existiert), der die Erwartungswerte von Nicht-Identitäts-Pauli-Operatoren, die auf einem Hilfsregister wirken, unterdrückt. Dies ermöglicht es der Reduktion, die gemischte-Zustand-Logik in einen reinen Zustand $|\Psi_{G,t}\rangle$ einzubetten, ohne künstliche große Koeffizienten zu erzeugen.

3. Komplexitätsanalyse:

   • Mitgliedschaft: Die Arbeit zeigt, dass LPC in QCMA liegt. Ein klassisches Zeugnis (Witness) besteht in der Beschreibung der Pauli-Matrix $P$. Ein Quanten-Verifier kann $\text{Tr}(P\rho)$ durch wiederholte Pauli-Messungen schätzen. Wenn $\epsilon$ invers-polynomisch zur Schaltkreisgröße ist, läuft diese Verifikation in Polynomialzeit.
   • Schwierigkeit: Die Reduktion von $\lambda$-GapMWC zu LPC erfolgt in deterministischer Polynomialzeit. Da $\lambda$-GapMWC für NP schwer ist (speziell impliziert das Lösen in BQP, dass $\text{NP} \subseteq \text{BQP}$), überträgt sich die Schwierigkeit auf LPC.

Wesentliche Beiträge und Ergebnisse

• QCMA-Mitgliedschaft: Es wird gezeigt, dass das Problem in QCMA liegt, was bestätigt, dass eine klassische Beschreibung des Pauli-Operators für die Verifikation ausreicht.
• NP-Schwierigkeit unter BQP: Das primäre Ergebnis ist, dass, falls LPC in BQP (löslich durch einen Polynomialzeit-Quantenalgorithmus) läge, dann NP $\subseteq$ BQP gelten würde. Dies impliziert, dass unter der Standardannahme $\text{NP} \not\subseteq \text{BQP}$ kein effizienter Quantenalgorithmus zur Detektion großer Pauli-Koeffizienten für allgemeine Zustände existiert.
• Reiner Zustand-Schwierigkeit: Das Härte-Ergebnis gilt auch dann, wenn der Input-Zustand auf einen reinen Zustand beschränkt ist, was die Frage klärt, ob das Verwerfen von Qubits (gemischte Zustände) die Quelle der Schwierigkeit ist.
• BQP-Härte: Die Arbeit beweist weiter, dass LPC BQP-hart ist. Dies deutet darauf hin, dass das Problem wahrscheinlich nicht in NP liegt (es sei denn, $\text{BQP} \subseteq \text{NP}$), was darauf hindeutet, dass eine rein klassische Charakterisierung durch ein Zeugnis unwahrscheinlich ist.
• Konstanter Schwellenwert: Die Härte gilt selbst dann, wenn $\epsilon$ ein konstanter Wert ist, der unabhängig von der Eingabegröße ist, was die Möglichkeit ausschließt, dass die Schwierigkeit allein aus der Forderung nach hochpräziser Detektion resultiert.

Bedeutung und Behauptungen
Die Arbeit beansprucht, eine offene Frage bezüglich der Existenz effizienter tomographischer Verfahren zum Auffinden der größten Koeffizienten eines Quantenzustands in der Pauli-Basis zu klären. Die Ergebnisse deuten darauf hin, dass solche effizienten Verfahren unter Standard-Komplexitätsannahmen nicht existieren.

Die Autoren merken an, dass sie zwar eine Mitgliedschaft in QCMA und Härte für NP (sowie BQP-Härte) nachweisen, jedoch keinen engen Grenzwert (z. B. QCMA-Vollständigkeit) beweisen. Sie argumentieren jedoch, dass die Ergebnisse ausreichen, um die Landschaft zu klären: Algorithmen, die darauf abzielen, große Pauli-Koeffizienten mit polynomiellen Ressourcen zu finden, müssen auf zusätzliche strukturelle Annahmen über den Zustand zurückgreifen, wie etwa Pauli-Sparsity, Stabilizer-ähnliches Verhalten, niedrigen Rang, Lokalität oder geringe Verschränkung. Ohne diese Einschränkungen bleibt das allgemeine Problem rechnerisch unpraktikabel.