Unbounded degree overhead for Alice-conditioned quantum Bell certificates

Technische Samenvatting: Onbegrensde Graad-overhead voor Alice-geconditioneerde Kwantum Bell-certificaten

Probleemstelling
Het artikel onderzoekt de computationele kosten van het certificeren van kwantum Bell-grenzen binnen de Navascués–Pironio–Acín (NPA) hiërarchie wanneer de certificaatstructuur beperkt is. Specifiek wordt gekeken naar "Alice-geconditioneerde" hiërarchieën, waarbij elke sum-of-squares (SOS) term in het duale certificaat slechts één van de meetvragen van Alice mag bevatten. Deze structuur is relevant voor gecompileerde niet-lokale spellen en specifieke cryptografische bewijzen van betrouwbaarheid (bijv. de "nice-SOS" route). De centrale vraag is of het beperken van het certificaat tot deze "enkele-vraag"-structuur een begrensde overhead oplegt in de graad van de SOS-decompositie vergeleken met standaard, onbeperkte certificaten. De auteur richt zich op de getilted-CHSH familie van Bell-functionalen, waarbij standaard certificaten bekend zijn als exact op niveau twee.

Methodologie
De auteur maakt gebruik van een combinatie van analytische constructie, algebraïsche verificatie en numerieke optimalisatie binnen het kader van semidefinitie programmering (SDP) en operator-algebra's.

1. Hiërarchieën en Conussen: De studie vergelijkt twee conussen van SOS-certificaten in de reële Bell-gap ruimte:

   • $D_k$: Standaard graad-$k$ certificaten (woorden met een totale gereduceerde lengte $\le k$).
   • $O_k$: Alice-geconditioneerde graad-$k$ certificaten (Bob-woorden van lengte $\le k$ in blokken geïndexeerd door Alice's vraag/antwoord).
     De conversie-graad $d_{std}$ en $d_{os}$ worden gedefinieerd als het minimale niveau vereist om een specifiek grenswaarde $\beta$ te certificeren.

2. Analytische Tegenvoorbeelden (Onbegrensde Overhead): Om te bewijzen dat geen enkele eindige geconditioneerde niveau alle standaard niveau-twee certificaten bevat, construeert de auteur een familie van haalbare getuigen (witnesses) met behulp van positieve functionalen op de oneindige dihedrale groep ($\mathbb{Z}_2 * \mathbb{Z}_2$).

   • Er wordt gebruikgemaakt van een Fejér-gewogen trace om een positief functionaal te construeren dat massa concentreert op specifieke Bob-woorden.
   • Door een rang-één term te aftrekken die overeenkomt met een deterministisch Bob-antwoord gewogen met $r_k \sim k^{-2}$, creëren zij een getuige die de positiviteitsbeperkingen van elk eindig geconditioneerd niveau $k$ schendt voor een specifiek tilt $\alpha_k$ die de lokale eindpunt nadert ($\alpha \to 2$).
   • Deze constructie berust op de Gram-matrix van een voortschrijdend gemiddelde, waarbij de rang-één aftrekking alleen positief semidefinit blijft als het geconditioneerde niveau voldoende hoog is.

3. Exacte Certificaten op Intervallen: Om daarentegen te identificeren in welke regimes de overhead begrensd is, construeert de auteur exacte certificaten voor specifieke intervallen van de tilt-parameter $\alpha$.

   • Optimal-Face Reductie: Zij maken gebruik van de optimale strategie van het getilted-CHSH spel om de kern (kernel) van de moment-matrices te identificeren. Dit reduceert de zoektocht naar het duale certificaat tot het vinden van positief semidefiniete (PSD) matrices op de orthogonale complement van de kern.
   • Rationale Functiefamilies: Voor het interval $\alpha \in [13/10, 3/2]$ parametriseert de auteur de kwantum-grenswaarde en de strategie-kernen met rationale functies. Zij construeren een continue familie van certificaten waarbij de Gram-matrices graad-20 matrix-polynomen zijn.
   • Bernstein Positiviteit: Zij verifiëren de positiviteit van deze polynomen over het interval door ze uit te breiden in Bernstein-bases en te controleren of alle coëfficiënt-matrices strikt PSD zijn.

4. Randomness Certificatie: Het artikel vertaalt deze Bell-grenswaarde-scheidingen naar device-independente randomness certificatie. Met behulp van een contact-criterium betreffende de concaviteit van de gokkans-functie, tonen zij aan dat een scheiding in Bell-grenswaarden direct een scheiding in gecertificeerde min-entropie impliceert.

Belangrijkste Bijdragen en Resultaten

• Onbegrensde Graad-overhead: Het primaire resultaat (Theorem 1) bewijst dat voor de getilted-CHSH familie geen enkel eindig niveau van de Alice-geconditioneerde hiërarchie alle standaard niveau-twee certificaten bevat. Specifiek, naarmate de tilt $\alpha$ de lokale eindpunt nadert ($\alpha \to 2$), groeit de vereiste geconditioneerde niveau $d_{os}$ ten minste als $\Omega((2-\alpha)^{-1/2})$.

  • Voor elk geheel getal $k$ bestaat er een tilt $\alpha_k$ zodanig dat het standaard certificaat exact is op niveau 2 ($d_{std}=2$), maar het geconditioneerde certificaat een niveau vereist dat strikt groter is dan $k$ ($d_{os} > k$).
  • Dit stelt vast dat de "enkele-vraag"-beperking een onbegrensde toename van algebraïsche middelen kan forceren, zelfs wanneer een laag-graads standaard certificaat bestaat.

• Exacte Eindige Conversie op Intervallen: Ondanks de onbegrensde overhead nabij de eindpunt, bewijst de auteur (Theorem 2) dat de overhead op het continue interval $\alpha \in [13/10, 3/2]$ exact één niveau is.

  • Voor alle $\alpha$ in dit bereik geldt $d_{std} = 2$ en $d_{os} = 3$.
  • Dit wordt aangetoond via een expliciete rationale-functie certificaatfamilie die is geverifieerd met Bernstein-positiviteit, wat bewijst dat de geconditioneerde hiërarchie exact kan sluiten op niveau 3 voor deze subfamilie.

• Scheiding van Niveau-Eén Waarden: Het artikel corrigeert een eerdere claim betreffende niveau-één equivalentie. Het bewijst (Theorem 3.7) dat voor getilted-CHSH met $\alpha > 0$, de standaard niveau-één waarde strikt groter is dan de Alice-geconditioneerde niveau-één waarde ($\omega_{std}^1 > \omega_{os}^1$). Dit komt doordat geconditioneerde blokken op niveau één impliciet totale-graad-drie momenten bevatten (via de blok-label) die afwezig zijn in de standaard niveau-één truncatie.

• Device-Independente Randomness: De auteur demonstreert (Theorem 3) dat de onbegrensde graad-overhead operationele gevolgen heeft. Geen enkel eindig geconditioneerd niveau kan de volledige optimale CHSH randomness tradeoff tegen kwantum zij-informatie certificeren, terwijl standaard niveau twee dat wel kan. Specifiek, voor een sequentie van CHSH-waarden $s_k \to 2$, is de gecertificeerde min-entropie met geconditioneerd niveau $k$ strikt lager dan het kwantum optimum, met een tekort dat voor specifieke punten groter is dan $10^{-3}$ bits.

• Implicaties voor Gecompileerde Betrouwbaarheid: De resultaten bieden een kwantitatieve obstructie voor "nice-SOS" inputs in gecompileerde niet-lokale spel betrouwbaarheidsbewijzen. De graad van de Bob-woord factoren in een exact nice-SOS certificaat voor een getilted grenswaarde nabij de eindpunt moet groeien als $\Omega(\epsilon^{-1/2})$, wat de efficiëntie van dergelijke bewijzen voor willekeurige tilts beperkt.

Betekenis en Claims
Het artikel claimt een scheiding tussen de "gewone SOS graad" en de "middelen opgelegd door de enkele-vraag certificaatstructuur". Het demonstreert dat structurele beperkingen op certificaten, vaak gemotiveerd door cryptografische toepassingen (gecompileerde spellen), de convergentie-eigenschappen van de NPA-hiërarchie fundamenteel kunnen veranderen.

• Bescheidenheid van Claims: De auteur geeft expliciet aan dat zij niet beweren dat er een falen is van de gecompileerde protocol veiligheid of een falen van de eindige-sleutel snelheid (finite-key rate). De resultaten betreffen de precisie van single-round certificeringsmethoden en de algebraïsche graad vereist voor exacte certificaten.
• Openstaande Problemen: Het artikel erkent dat hoewel een asymptotische ondergrens van $\Omega(\epsilon^{-1/2})$ bewezen is, een exacte bovengrens of bewijs van eindige exacte afsluiting voor elke vaste subkritische tilt openstaat. De numerieke verzadiging suggereert een wortel-groei, maar een rigoureuze bovengrens die deze exponent matcht is niet vastgesteld.
• Correctie van Literatuur: Het werk verfijnt het begrip van de relatie tussen standaard en geconditioneerde hiërarchieën, waarbij een eerdere bewering over de gelijkheid van niveau-één waarden voor getilted CHSH wordt gecorrigeerd en het onderscheid tussen POVM/localizer filtraties en de ruwe PVM quotient gebruikt wordt verduidelijkt.

Samenvattend stelt het artikel vast dat hoewel Alice-geconditioneerde hiërarchieën voor specifieke parameterregimes exact kunnen zijn op lage niveaus, zij lijden onder een onbegrensde graad-overhead nabij de grens van de kwantum verzameling, wat het universeel vervangen van standaard hiërarchieën voor exacte certificeringstaken verhindert.