Unbounded degree overhead for Alice-conditioned quantum Bell certificates

Technische Zusammenfassung: Unbeschränkter Grad-Overhead für Alice-konditionierte Quanten-Bell-Zertifikate

Problemstellung
Die vorliegende Arbeit untersucht die rechnerische Komplexität der Zertifizierung von Quanten-Bell-Schranken innerhalb der Navascués–Pironio–Acín (NPA)-Hierarchie, wenn die Struktur des Zertifikats eingeschränkt ist. Konkret wird „Alice-konditionierte“ Hierarchien untersucht, bei denen jeder Summe-der-Quadrate (SOS)-Term nur eine der Fragen von Alice enthalten darf. Diese Struktur ist relevant für kompilierte nichtlokale Spiele und spezifische kryptographische Soundness-Beweise (z. B. den „nice-SOS“-Ansatz). Die zentrale Frage ist, ob die Beschränkung des Zertifikats auf diese „Einzel-Fragen-Struktur“ einen beschränkten Overhead im Grad der SOS-Zerlegung im Vergleich zu Standard-Zertifikaten ohne Einschränkungen erzwingt. Der Autor konzentriert sich auf die Familie der tilted-CHSH Bell-Funktionale, für die Standard-Zertifikate bekanntlich auf Level zwei exakt sind.

Methodik
Der Autor verwendet eine Kombination aus analytischer Konstruktion, algebraischer Verifikation und numerischer Optimierung innerhalb des Rahmens von semidefiniten Programmierungen (SDP) und Operator-Algebren.

1. Hierarchien und Konen: Die Studie vergleicht zwei Konen von SOS-Zertifikaten im reellen Bell-Gap-Raum:

   • $D_k$: Standardmäßige Grad-$k$-Zertifikate (Wörter mit totaler reduzierter Länge $\le k$).
   • $O_k$: Alice-konditionierte Grad-$k$-Zertifikate (Bob-Wörter der Länge $\le k$ in Blöcken, die durch Alices Frage/Antwort indiziert sind).
     Die Konvertierungsgrade $d_{std}$ und $d_{os}$ sind definiert als das minimale Level, das erforderlich ist, um eine spezifische Schranke $\beta$ zu zertifizieren.

2. Analytische Gegenbeispiele (Unbeschränkter Overhead): Um zu beweisen, dass kein endliches konditioniertes Level alle Standard-Level-Zwei-Zertifikate enthält, konstruiert der Autor eine Familie von zulässigen Zeugen unter Verwendung positiver Funktionale auf der unendlichen Diedergruppe ($\mathbb{Z}_2 * \mathbb{Z}_2$).

   • Sie nutzen ein Fejér-gewichtetes Trace, um ein positives Funktional zu konstruieren, das die Masse auf spezifische Bob-Wörter konzentriert.
   • Durch Subtraktion eines Rang-eins-Terms, der einer deterministischen Bob-Antwort entspricht, gewichtet mit $r_k \sim k^{-2}$, erzeugen sie einen Zeugen, der die Positivitätsbeschränkungen eines spezifischen Tilts $\alpha_k$, der sich dem lokalen Endpunkt ($\alpha \to 2$) nähert, für jedes endliche konditionierte Level $k$ verletzt.
   • Diese Konstruktion beruht auf der Gram-Matrix eines gleitenden Durchschnitts, wobei die Rang-eins-Subtraktion nur dann positiv semidefinit bleibt, wenn das konditionierte Level ausreichend hoch ist.

3. Exakte Zertifikate auf Intervallen: Umgekehrt identifiziert der Autor Regime, in denen der Overhead beschränkt ist, indem er exakte Zertifikate für spezifische Intervalle des Tilt-Parameters $\alpha$ konstruiert.

   • Optimal-Face-Reduktion: Sie nutzen die optimale Strategie des tilted-CHSH-Spiels, um den Kern der Moment-Matrizen zu identifizieren. Dies reduziert die Suche nach dem dualen Zertifikat auf das Finden positiv semidefiniter (PSD) Matrizen auf dem orthogonalen Komplement des Kerns.
   • Rationale Funktionen: Für das Intervall $\alpha \in [13/10, 3/2]$ parametrisieren sie die Quanten-Schranke und die Strategie-Kerne mittels rationaler Funktionen. Sie konstruieren eine kontinuierliche Familie von Zertifikaten, bei denen die Gram-Matrizen Matrix-Polynome vom Grad 20 sind.
   • Bernstein-Positivität: Sie verifizieren die Positivität dieser Polynome über dem Intervall, indem sie sie in eine Bernstein-Basis expandieren und prüfen, ob alle Koeffizienten-Matrizen strikt PSD sind.

4. Randomness-Zertifizierung: Das Papier überträgt diese Bell-Schranken-Separationen auf die geräteunabhängige Randomness-Zertifizierung. Unter Verwendung eines Kontakt-Kriteriums, das die Konkavität der Guessing-Probability-Funktion nutzt, zeigen sie, dass eine Separation in Bell-Schranken direkt eine Separation in der zertifizierten Min-Entropie impliziert.

Wesentliche Beiträge und Ergebnisse

• Unbeschränkter Grad-Overhead: Das primäre Ergebnis (Theorem 1) beweist, dass für die tilted-CHSH-Familie kein endliches Level der Alice-konditionierten Hierarchie alle Standard-Level-Zwei-Zertifikate enthält. Speziell gilt: Wenn der Tilt $\alpha$ sich dem lokalen Endpunkt nähert ($\alpha \to 2$), wächst der erforderliche konditionierte Grad $d_{os}$ mindestens mit $\Omega((2-\alpha)^{-1/2})$.

  • Für jedes ganze Zahl $k$ existiert ein Tilt $\alpha_k$, sodass das Standard-Zertifikat auf Level 2 exakt ist ($d_{std}=2$), aber das konditionierte Zertifikat ein Level benötigt, das strikt größer als $k$ ist ($d_{os} > k$).
  • Dies etabliert, dass die „Einzel-Fragen-Beschränkung“ einen unbeschränkten Anstieg der algebraischen Ressourcen erzwingen kann, selbst wenn ein niedriggradiges Standard-Zertifikat existiert.

• Exakte endliche Konvertierung auf Intervallen: Trotz des unbeschränkten Overheads nahe dem Endpunkt beweist der Autor (Theorem 2), dass der Overhead auf dem kontinuierlichen Intervall $\alpha \in [13/10, 3/2]$ genau ein Level beträgt.

  • Für alle $\alpha$ in diesem Bereich gilt $d_{std} = 2$ und $d_{os} = 3$.
  • Dies wird durch eine explizite rationale Funktions-Zertifikatsfamilie demonstriert, die mittels Bernstein-Positivität verifiziert wurde, was beweist, dass die konditionierte Hierarchie für diese Teilfamilie exakt auf Level 3 abschließt.

• Separation von Level-Eins-Werten: Das Papier korrigiert eine frühere Behauptung bezüglich der Level-Eins-Äquivalenz. Es beweist (Theorem 3.7), dass für tilted-CHSH mit $\alpha > 0$ der Standard-Level-Eins-Wert strikt größer ist als der Alice-konditionierte Level-Eins-Wert ($\omega_{std}^1 > \omega_{os}^1$). Dies liegt daran, dass konditionierte Blöcke auf Level eins implizit Terme des Gesamtgrades drei enthalten (über das Block-Label), die in der Standard-Level-Eins-Trunkierung fehlen.

• Geräteunabhängige Randomness: Der Autor zeigt (Theorem 3), dass der unbeschränkte Grad-Overhead operationale Konsequenzen hat. Kein endliches konditioniertes Level kann den gesamten optimale CHSH-Randomness-Tradeoff gegen Quanten-Seiteninformationen zertifizieren, während Standard-Level-Zwei dies kann. Speziell für eine Sequenz von CHSH-Werten $s_k \to 2$ ist die mittels konditioniertem Level $k$ zertifizierte Min-Entropie strikt niedriger als das Quanten-Optimum, wobei das Defizit an spezifischen Punkten $10^{-3}$ Bits übersteigt.

• Implikationen für die kompilierte Soundness: Die Ergebnisse liefern ein quantitatives Hindernis für „nice-SOS“-Inputs in der Soundness-Analyse kompilierter nichtlokaler Spiele. Der Grad der Bob-Wort-Faktoren in einem exakten nice-SOS-Zertifikat für einen tilted-Bound nahe dem Endpunkt muss als $\Omega(\epsilon^{-1/2})$ wachsen, was die Effizienz solcher Beweise für beliebige Tilts begrenzt.

Bedeutung und Behauptungen
Das Papier beansprucht, den „gewöhnlichen SOS-Grad“ von den „Ressourcen, die durch die Einzel-Fragen-Zertifikatsstruktur auferlegt werden“, zu trennen. Es zeigt, dass strukturelle Beschränkungen auf Zertifikate, die oft durch kryptographische Anwendungen (kompilierte Spiele) motiviert sind, die Konvergenzeigenschaften der NPA-Hierarchie fundamental verändern können.

• Bescheidenheit der Ansprüche: Der Autor stellt explizit klar, dass er keinen Ausfall der Sicherheit kompilierter Protokolle oder eines Finite-Key-Rate-Ausfalls behauptet. Die Ergebnisse betreffen die Präzision von Single-Round-Zertifizierungsmethoden und den algebraischen Grad erforderlicher exakter Zertifikate.
• Offene Probleme: Das Papier räumt ein, dass zwar eine asymptotische untere Schranke von $\Omega(\epsilon^{-1/2})$ bewiesen wurde, eine exakte obere Schranke oder ein Beweis für den endlichen exakten Abschluss für jeden fixen subkritischen Tilt jedoch offen bleibt. Die numerische Sättigung deutet auf ein quadratisches Wachstum hin, aber eine rigorose obere Schranke, die diesen Exponenten exakt matcht, ist nicht etabliert.
• Korrektur der Literatur: Die Arbeit präzisiert das Verständnis des Verhältnisses zwischen Standard- und konditionierten Hierarchien und korrigiert dabei eine frühere Aussage über die Gleichheit der Level-Eins-Werte für tilted CHSH sowie klärt die Unterscheidung zwischen POVM/Localizer-Filtrationen und dem hier verwendeten rohen PVM-Quotienten.

Zusammenfassend lässt sich sagen, dass das Paper etabliert, dass während Alice-konditionierte Hierarchien für spezifische Parameterregime auf niedrigen Levels exakt sein können, sie in der Nähe der Grenze des Quanten-Sets unter einem unbeschränkten Grad-Overhead leiden, was sie universell ungeeignet macht, Standard-Hierarchien für exakte Zertifizierungsaufgaben zu ersetzen.