New lower bounds for CDS and $f$-routing

Technische Samenvatting: Nieuwe Ondergrenzen voor CDS en f-routing

Probleemstelling
Dit artikel behandelt de fundamentele limieten van de kosten van middelen in twee gerelateerde kwantum- en klassieke informatietaken: Non-Lokale Kwantumcomputatie (NLQC), specifiek het f-routing probleem, en Conditional Disclosure of Secrets (CDS).

• f-routing: In deze taak ontvangen Alice en Bob klassieke inputs $x$ en $y$ en een gedeelde verstrengelde toestand. Alice houdt een onbekend kwantumsysteem $Q$ vast. Ze moeten lokale operaties en één ronde van simultane kwantumcommunicatie uitvoeren zodat als $f(x,y)=0$, Alice $Q$ herstelt, en als $f(x,y)=1$, Bob $Q$ herstelt. Het primaire doel is om de ondergrenzen vast te stellen voor de verstrengelingskosten (Schmidt-rang van de gedeelde toestand) die vereist zijn voor deze taak. Hoewel er bovengrenzen bestaan (bijv. $2^{O(\sqrt{n \log n})}$), was het bewijzen van ondergrenzen voor robuuste protocollen (die een constante fout toestaan op beide inputklassen) een belangrijk openstaand probleem. Eerdere resultaten door Asadi, Culf en May (ACM25) boden alleen groeiende ondergrenzen voor éénzijdige perfecte protocollen (perfect herstel op één inputklasse, constante fout op de andere).
• CDS: Een klassieke primitief waarbij Alice $(x, s)$ bezit en Bob $y$ bezit, met gedeelde willekeur $R$. Ze sturen berichten naar een referee die $(x,y)$ kent. Als $f(x,y)=1$, herstelt de referee $s$; als $f(x,y)=0$, onthullen de berichten geen informatie over $s$. Het onderzoek richt zich op de gedeelde willekeur-kosten in de robuuste setting (waarbij een constante fout wordt toegestaan in zowel correctheid als privacy), een setting waarin eerdere ondergrenzen beperkt waren of niet bestonden onder onbeperkte communicatie en private willekeur.

Methodologie
De auteurs hanteren twee verschillende technische benaderingen om hun ondergrenzen af te leiden:

1. Robuuste CDS via Transcriptiedistributies en Dekkingsgetallen:

   • De auteurs analyseren de totale variatieafstand $D(x,y)$ tussen de transcriptiedistributies die overeenkomen met geheimen $s=0$ en $s=1$.
   • Constraints op correctheid en privacy dwingen $D(x,y)$ om groot te zijn wanneer $f(x,y)=1$ en klein wanneer $f(x,y)=0$.
   • Ze representeren de rij- en kolomafstandfuncties van $f$ als verwachtingswaarden van functies die behoren tot een specifieke klasse $\mathcal{F}_q$, waarbij $q$ de support-grootte van de gedeelde willekeur is. Deze functies zijn gedefinieerd op de waarschijnlijkheidssimplex $\Delta_q$.
   • Door gebruik te maken van een dekkingsgetalargument (het construeren van een $\eta$-net voor $\mathcal{F}_q$), begrenzen ze het aantal verschillende functies dat gegenereerd kan worden door een gedeelde willekeur van grootte $q$.
   • Door de separatie van deze afstandfuncties te relateren aan het aantal verschillende rijen en kolommen in de communicatiematrix van $f$, koppelen ze de gedeelde willekeur-kosten aan de deterministische Simultane Message Passing (SMP) communicatiecomplexiteit, aangeduid als $D_{\parallel}(f)$.

2. Éénzijdig-perfecte f-routing via Sign-Rank:

   • De auteurs herzien de rank-methode geïntroduceerd door Asadi, Culf en May (ACM25), die een niet-negatieve matrix $G$ associeert met het protocol, waarbij $G_{x,y}=0$ voor $f(x,y)=0$ en $G_{x,y}>0$ voor $f(x,y)=1$, met $\text{rank}(G) \le d_E^4$ ($d_E$ is de Schmidt-rang).
   • Ze maken gebruik van de positiviteit van $G$ om een matrix $A = G - \tau J$ te construeren (waarbij $J$ de eenheidsmatrix is en $\tau$ een kleine constante). Deze matrix $A$ heeft hetzelfde tekenpatroon als de sign-matrix $S_f$ van de functie $f$.
   • Met behulp van de subadditiviteit van de matrix-rang tonen ze aan dat $\text{signrank}(S_f) \le \text{rank}(A) \le \text{rank}(G) + 1 \le d_E^4 + 1$.
   • Dit vestigt een directe ondergrens op de verstrengelingskosten in termen van de unbounded-error communicatiecomplexiteit ($UPP_{cc}$) via bekende resultaten.

Belangrijkste Bijdragen en Resultaten

1. Ondergrens voor Robuuste CDS (Stelling 1.1):

   • Het artikel bewijst dat voor elk $\epsilon$-correct en $\delta$-privaat CDS-protocol (met $2\epsilon + \delta < 1$), de gedeelde willekeur-kosten $\log_2 q$ voldoen aan:
     $$\log_2 q = \Omega(\log_2 D_{\parallel}(f))$$
   • Deze grens geldt zelfs wanneer private willekeur en berichtlengtes onbeperkt zijn.
   • Tightheid: Voor de gelijkheidsfunctie ($n$-bits), $D_{\parallel}(f) = \Theta(n)$, wat een $\Omega(\log n)$ ondergrens oplevert. De auteurs leveren een bijbehorende bovengrens in Appendix A, waarmee zij aantonen dat dit resultaat voor gelijkheid tight is tot aan constante factoren.

2. Sign-Rank Ondergrenzen voor Éénzijdig-perfecte f-routing (Stelling 1.2):

   • Voor protocollen die exact zijn op één inputklasse (0-inputs of 1-inputs) en een constante fout hebben op de andere, wordt de verstrengelingskosten ondergrenst door:
     $$\text{Kosten} \ge \frac{1}{4} \log_2(\max\{1, \text{signrank}(S_f) - 1\})$$
   • Dit impliceert een grens in termen van de unbounded-error communicatiecomplexiteit: $\text{Kosten} \ge \frac{1}{4} UPP_{cc}(f) - O(1)$.
   • Toepassing op Inner Product: Voor de inner-product functie $IP_n$ is de sign-rank bekend als exponentieel ($2^{n/2}$). Dit levert een lineaire ondergrens op:
     $$\text{Kosten} \ge \frac{n}{8} - \frac{1}{4}$$
   • Dit komt overeen met de bekende $O(n)$ bovengrens afgeleid van de garden-hose constructie, wat de complexiteit voor $IP_n$ in de éénzijdig-perfecte setting oplost. De auteurs merken op dat hun coëfficiënt ($1/4$) de $1/8$ coëfficiënt verbetert die is afgeleid van het combineren van eerdere nondeterministische rank-bounds met sign-rank relaties.

3. Corollaria voor Gerelateerde Taken:

   • Door middel van reducties van f-routing naar f-BB84 en CDS, leiden de auteurs overeenkomstige ondergrenzen af voor deze taken in termen van sign-rank en $UPP_{cc}$. Specifiek vestigen ze $\Omega(\log(\text{signrank}(S_f)))$ ondergrenzen voor CDS met perfecte privacy of perfecte correctheid.

Betekenis en Claims
Het artikel claimt de volgende bijdragen aan het vakgebied te hebben geleverd:

• Resolutie van een Open Probleem voor CDS: Het biedt de eerste ondergrens op gedeelde willekeur voor robuuste CDS die constante fout toestaat in zowel correctheid als privacy, met onbeperkte communicatie en private willekeur. Het resultaat is tight voor de gelijkheidsfunctie.
• Verbeterde Grenzen voor f-routing: Waar eerder werk (ACM25) geen groeiende ondergrens kon afleiden voor de inner-product functie in de éénzijdig-perfecte setting (wat slechts een constante grens opleverde via nondeterministische rank), levert dit artikel succesvol een lineaire ondergrens ($\Omega(n)$ op via de sign-rank benadering), wat de bekende bovengrens evenaart.
• Methodologische Distinctie: De auteurs benadrukken dat hun sign-rank formulering de nondeterministische rank-argumentatie van ACM25 niet vervangt, maar een complementair en soms sterker perspectief biedt (bijv. voor $IP_n$). Omgekeerd vangt hun robuuste CDS-grens (gebaseerd op deterministische SMP-complexiteit) functies zoals gelijkheid op waar de sign-rank constant is, wat aantoont dat de twee methoden verschillende aspecten van complexiteit vatten.
• Onafhankelijkheid: De auteurs erkennen het onafhankelijke werk van Bogner (2026), dat een logaritmische ondergrens bewees voor f-routing met inner product in de twee-zijdige fout-regime. De auteurs verduidelijken dat hun robuuste CDS-resultaat onderscheidend is en niet wordt opgenomen door Bogner's werk, aangezien het van toepassing is op functies met een constante sign-rank maar lineaire deterministische SMP-complexiteit.

Het artikel concludeert door op te merken dat het verkrijgen van polynomiale ondergrenzen voor f-routing in de volledig robuuste (twee-zijdige fout) setting een open probleem blijft, en dat het ontwikkelen van sterkere technieken voor CDS gedeelde-willekeur-ondergrenzen inzichten kan bieden voor de kwantumsetting.