Unbounded degree overhead for Alice-conditioned quantum Bell certificates

Sintesi Tecnica: Overhead di Grado Illimitato per i Certificati Bell Quantistici Condizionati ad Alice

Enunciato del Problema
Il saggio investiga il costo computazionale della certificazione dei limiti Bell nella gerarchia di Navascués–Pironio–Acín (NPA) quando la struttura del certificato è vincolata. Nello specifico, esamina le gerarchie "condizionate ad Alice", in cui ogni termine somma-di-quadrati (SOS) nel certificato duale deve coinvolgere solo una delle domande di Alice. Questa struttura è rilevante per i giochi non locali compilati e per specifici processi di prova di correttezza (soundness) crittografica (ad esempio, la via "nice-SOS"). La questione centrale è se restringere il certificato a questa struttura a "singola domanda" imponga un overhead di grado limitato rispetto ai certificati standard non vincolati. L'autore si concentra sulla famiglia di funzionali Bell CHSH-tilted, per i quali i certificati standard sono noti per essere esatti al livello due.

Metodologia
L'autore impiega una combinazione di costruzione analitica, verifica algebrica e ottimizzazione numerica all'interno del framework di programmazione semidefinita (SDP) e delle algebre di operatori.

1. Gerarchie e Coni: Lo studio confronta due coni di certificati SOS nello spazio reale del gap Bell:

   • $D_k$: Certificati di grado standard $k$ (parole di lunghezza totale ridotta $\le k$).
   • $O_k$: Certificati di grado $k$ condizionati ad Alice (parole di Bob di lunghezza $\le k$ in blocchi indicizzati dalla domanda/risposta di Alice).
     La conversione di grado $d_{std}$ e $d_{os}$ è definita come il livello minimo richiesto per certificare un particolare limite $\beta$.

2. Controesempi Analitici (Overhead Illimitato): Per dimostrare che nessun livello condizionato finito contiene tutti i certificati standard di livello due, l'autore costruisce una famiglia di testimoni (witnesses) ammissibili utilizzando funzionali positivi sul gruppo diedro infinito ($\mathbb{Z}_2 * \mathbb{Z}_2$).

   • Utilizzano una traccia pesata di Fejér per costruire un funzionale positivo che concentra la massa su specifiche parole di Bob.
   • Sottraendo un termine di rango uno corrispondente a una risposta deterministica di Bob pesata con $r_k \sim k^{-2}$, creano un testimone che viola i vincoli di positività di qualsiasi livello condizionato $k$ finito per un particolare tilt $\alpha_k$ che tende al limite locale ($\alpha \to 2$).
   • Questa costruzione si basa sulla matrice di Gram di una media mobile, dove la sottrazione di rango uno rimane semidefinita positiva solo se il livello condizionato è sufficientemente elevato.

3. Certificati Esatti su Intervalli: Viceversa, per identificare i regimi in cui l'overhead è limitato, l'autore costruisce certificati esatti per specifici intervalli del parametro di tilt.

   • Riduzione all'Ottimo-Faccia (Optimal-Face Reduction): Utilizzano la strategia ottimale del gioco CHSH-tilted per identificare il nucleo (kernel) delle matrici di momento. Ciò riduce la ricerca del certificato duale alla ricerca di matrici definite positive (PSD) sul complemento ortogonale del nucleo.
   • Famiglie di Funzioni Razionali: Per l'intervallo $\alpha \in [13/10, 3/2]$, parametrizzano il limite quantistico e i nuclei delle strategie utilizzando funzioni razionali. Costruiscono una famiglia continua di certificati dove le matrici di Gram sono polinomi matriciali di grado 20.
   • Positività di Bernstein: Verificano la positività di questi polinomi sull'intervallo espandendoli in basi di Bernstein e controllando che tutte le matrici dei coefficienti siano strettamente PSD.

4. Certificazione della Casualità: Il saggio traduce queste separazioni dei limiti Bell nella certificazione della casualità device-independent. Utilizzando un criterio di contatto basato sulla concavità della funzione di probabilità di indovinare, dimostrano che una separazione nei limiti Bell implica direttamente una separazione nell'entropia minima certificata.

Contributi Chiave e Risultati

• Overhead di Grado Illimitato: Il risultato primario (Teorema 1) dimostra che, per la famiglia CHSH-tilted, nessun livello finito della gerarchia condizionata ad Alice contiene tutti i certificati standard di livello due. Nello specifico, mentre il tilt $\alpha$ si avvicina al limite locale ($\alpha \to 2$), il livello condizionato richiesto $d_{os}$ cresce almeno come $\Omega((2-\alpha)^{-1/2})$.

  • Per ogni intero $k$, esiste un tilt $\alpha_k$ tale che il certificato standard è esatto al livello 2 ($d_{std}=2$), ma il certificato condizionato richiede un livello strettamente maggiore di $k$ ($d_{os} > k$).
  • Ciò stabilisce che la restrizione a "singola domanda" può forzare un aumento illimitato delle risorse algebriche, anche quando esiste un certificato standard di basso grado.

• Conversione Finita Esatta su Intervalli: Nonostante l'overhead illimitato vicino al limite, l'autore dimostra (Teorema 2) che, sull'intervallo continuo $\alpha \in [13/10, 3/2]$, l'overhead è esattamente di un livello.

  • Per tutti gli $\alpha$ in questo intervallo, $d_{std} = 2$ e $d_{os} = 3$.
  • Ciò è dimostrato tramite una famiglia esplicita di certificati a funzioni razionali verificata tramite la positività di Bernstein, provando che la gerarchia condizionata può chiudersi esattamente al livello 3 per questa sottofamiglia.

• Separazione dei Valori di Livello Uno: Il saggio corregge una precedente affermazione riguardante l'equivalenza di livello uno. Dimostra (Teorema 3.7) che per il CHSH-tilted con $\alpha > 0$, il valore standard di livello uno è strettamente maggiore del valore condizionato ad Alice di livello uno ($\omega_{std}^1 > \omega_{os}^1$). Ciò è dovuto al fatto che i blocchi condizionati al livello uno includono implicitamente momenti di grado totale tre (tramite l'indice del blocco) che sono assenti nella troncatura standard di livello uno.

• Casualità Device-Independent: L'autore dimostra (Teorema 3) che l'overhead di grado illimitato ha conseguenze operative. Nessun livello condizionato finito può certificare l'intero tradeoff della casualità CHSH ottimale contro informazioni laterali quantistiche, mentre il livello standard due può farlo. Nello specifico, per una sequenza di valori CHSH $s_k \to 2$, l'entropia minima certificata usando il livello condizionato $k$ è strettamente inferiore all'ottimo quantistico, con un deficit superiore a $10^{-3}$ bit per punti specifici.

• Implicazioni per la Correttezza Compilata (Compiled Soundness): I risultati forniscono un'ostruzione quantitativa per gli input "nice-SOS" nelle prove di correttezza di giochi non locali compilati. Il grado dei fattori delle parole di Bob in un certificato nice-SOS esatto per un limite tilted vicino al limite deve crescere come $\Omega(\epsilon^{-1/2})$, limitando l'efficienza di tali prove per tilt arbitrari.

Significato e Rivendicazioni
Il saggio rivendica la separazione tra il "grado SOS ordinario" e le "risorse imposte dalla struttura del certificato a singola domanda". Dimostra che i vincoli strutturali sui certificati, spesso motivati da applicazioni crittografiche (giochi compilati), possono alterare fondamentalmente le proprietà di convergenza della gerarchia NPA.

• Modestia delle Rivendicazioni: L'autore dichiara esplicitamente di non rivendicare un fallimento della sicurezza del protocollo compilato o un fallimento del tasso di chiave finita. I risultati riguardano la precisione dei metodi di certificazione a singolo round e il grado algebrico richiesto per i certificati esatti.
• Problemi Aperti: Il lavoro riconosce che, sebbene sia stato dimostrato un limite inferiore asintotico di $\Omega(\epsilon^{-1/2})$, rimane aperto un limite superiore esatto o la prova di una chiusura finita esatta per ogni fissato tilt subcritico. La saturazione numerica suggerisce una crescita di tipo radice quadrata, ma non è stabilito un limite superiore rigoroso che corrisponda a questo esponente.
• Correzione della Letteratura: Il lavoro perfeziona la comprensione della relazione tra le gerarchie standard e condizionate, correggendo una precedente asserzione sull'uguaglianza dei valori di livello uno per il CHSH-tilted e chiarendo la distinzione tra le filtrazioni POVM/localizzatore e il qui utilizzato quoziente PVM grezzo.

In sintesi, il saggio stabilisce che, sebbene le gerarchie condizionate ad Alice possano essere esatte a bassi livelli per specifici regimi di parametri, esse soffrono di un overhead di grado illimitato vicino al confine dell'insieme quantistico, impedendo loro di sostituire universalmente le gerarchie standard per compiti di certificazione esatta.