Unbounded degree overhead for Alice-conditioned quantum Bell certificates

Résumé Technique : Surcharge de Degré Non Bornée pour les Certificats de Bell de type Alice-Conditionné

Énoncé du Problème
L'article étudie le coût computationnel de la certification des bornes de Bell quantiques au sein de la hiérarchie de Navascués–Pironio–Acín (NPA) lorsque la structure du certificat est contrainte. Plus précisément, il examine les hiérarchies « conditionnées par Alice », où chaque terme de somme de carrés (SOS) dans le certificat dual doit impliquer une seule des questions de mesure d'Alice. Cette structure est pertinente pour les jeux non locaux compilés et certains types de preuves de robustesse cryptographique (par exemple, la voie « nice-SOS »). La question centrale est de savoir si la restriction du certificat à cette structure à « question unique » impose une surcharge bornée du degré de la décomposition SOS par rapport aux certificats standards non contraints. L'auteur se concentre sur la famille de fonctionnelles de Bell de type CHSH titrée (tilted-CHSH), pour laquelle les certificats standards sont connus pour être exacts au niveau deux.

Méthodologie
L'auteur emploie une combinaison de construction analytique, de vérification algébrique et d'optimisation numérique dans le cadre de la programmation semi-définie (SDP) et des algèbres d'opérateurs.

1. Hiérarchies et Cônes : L'étude compare deux cônes de certificats SOS dans l'espace réel du gap de Bell :

   • $D_k$ : Certificats de degré-$k$ standards (mots de longueur réduite totale $\le k$).
   • $O_k$ : Certificats de degré-$k$ conditionnés par Alice (mots de Bob de longueur $\le k$ dans des blocs indexés par la question/réponse d'Alice).
     Le degré de conversion $d_{std}$ et $d_{os}$ est défini comme le niveau minimum requis pour certifier une borne $\beta$ spécifique.

2. Contre-exemples Analytiques (Surcharge Non Bornée) : Pour prouver qu'aucun niveau conditionné fini ne contient tous les certificats de niveau deux standards, l'auteur construit une famille de témoins réalisables utilisant des fonctionnelles positives sur le groupe diédral infini ($\mathbb{Z}_2 * \mathbb{Z}_2$).

   • Ils utilisent une trace pondérée par Fejér pour construire une fonctionnelle positive qui concentre la masse sur des mots de Bob spécifiques.
   • En soustrayant un terme de rang un correspondant à une réponse déterministe de Bob pondérée par $r_k \sim k^{-2}$, ils créent un témoin qui viole les contraintes de positivité de tout niveau conditionné fini $k$ pour un tilt $\alpha_k$ spécifique approchant la limite locale ($\alpha \to 2$).
   • Cette construction repose sur la matrice de Gram d'une moyenne mobile, où la soustraction de rang un reste semi-définie positive uniquement si le niveau conditionné est suffisamment élevé.

3. Certificats Exacts sur des Intervalles : Inversement, pour identifier les régimes où la surcharge est bornée, l'auteur construit des certificats exacts pour des intervalles spécifiques du paramètre de tilt $\alpha$.

   • Réduction par Face Optimale : Ils utilisent la stratégie optimale du jeu CHSH titré pour identifier le noyau des matrices de moments. Cela réduit la recherche du certificat dual à la recherche de matrices semi-définies positives (PSD) sur le complément orthogonal du noyau.
   • Familles de Fonctions Rationnelles : Pour l'intervalle $\alpha \in [13/10, 3/2]$, ils paramètrent la borne quantique et les noyaux de stratégie par des fonctions rationnelles. Ils construisent une famille continue de certificats où les matrices de Gram sont des polynômes matriciels de degré 20.
   • Positivité de Bernstein : Ils vérifient la positivité de ces polynômes sur l'intervalle en les développant en bases de Bernstein et en vérifiant que toutes les matrices de coefficients sont strictement PSD.

4. Certification de l'Aléatoire : L'article traduit ces séparations de bornes de Bell en certification d'aléa indépendant du dispositif. En utilisant un critère de contact impliquant la concavité de la fonction de probabilité de devinement, ils montrent qu'une séparation dans les bornes de Bell implique directement une séparation dans l'entropie min quantique certifiée.

Contributions Clés et Résultats

• Surcharge de Degré Non Bornée : Le résultat principal (Théorème 1) prouve que pour la famille CHSH titrée, aucun niveau fini de la hiérarchie conditionnée par Alice ne contient tous les certificats de niveau deux standards. Spécifiquement, à mesure que le tilt $\alpha$ approche la limite locale ($\alpha \to 2$), le degré conditionné requis $d_{os}$ croît au moins comme $\Omega((2-\alpha)^{-1/2})$.

  • Pour tout entier $k$, il existe un tilt $\alpha_k$ tel que le certificat standard est exact au niveau 2 ($d_{std}=2$), mais le certificat conditionné nécessite un niveau strictement supérieur à $k$ ($d_{os} > k$).
  • Cela établit que la restriction à la « question unique » peut forcer une augmentation non bornée des ressources algébriques, même lorsqu'un certificat de faible degré standard existe.

• Conversion Finie Exacte sur des Intervalles : Malgré la surcharge non bornée près de la limite, l'auteur prouve (Théorème 2) que sur l'intervalle continu $\alpha \in [13/10, 3/2]$, la surcharge est exactement d'un niveau.

  • Pour tout $\alpha$ dans cet intervalle, $d_{std} = 2$ et $d_{os} = 3$.
  • Ceci est démontré via une famille explicite de certificats par fonctions rationnelles vérifiée par la positivité de Bernstein, prouvant que la hiérarchie conditionnée peut se fermer exactement au niveau 3 pour cette sous-famille.

• Séparation des Valeurs de Niveau Un : Le papier corrige une affirmation précédente concernant l'équivalence de niveau un. Il prouve (Théorème 3.7) que pour le CHSH titré avec $\alpha > 0$, la valeur de niveau un standard est strictement supérieure à la valeur de niveau un conditionnée par Alice ($\omega_{std}^1 > \omega_{os}^1$). Ceci est dû au fait que les blocs conditionnés au niveau un incluent implicitement des moments de degré total trois (via l'étiquette du bloc) qui sont absents de la troncature standard de niveau un.

• Aléatoire Indépendant du Dispositif : L'auteur démontre (Théorème 3) que la surcharge de degré non bornée a des conséquences opérationnelles. Aucun niveau conditionné fini ne peut certifier l'intégralité du compromis d'aléa CHSH optimal contre une information latérale quantique, alors que le niveau deux standard le peut. Plus précisément, pour une séquence de valeurs CHSH $s_k \to 2$, l'entropie min certifiée utilisant le niveau conditionné $k$ est strictement inférieure à l'optimum quantique, avec un déficit dépassant $10^{-3}$ bits pour des points spécifiques.

• Implications pour la Robustesse Compilée : Les résultats fournissent une obstruction quantitative pour les entrées « nice-SOS » dans les preuves de robustesse de jeux non locaux compilés. Le degré des facteurs de mots de Bob dans un certificat exact de type nice-SOS pour un tilt proche de la limite doit croître comme $\Omega(\epsilon^{-1/2})$, limitant l'efficacité de telles preuves pour des tilts arbitraires.

Signification et Revendications
L'article affirme séparer le « degré SOS ordinaire » des « ressources imposées par la structure de certificat à question unique ». Il démontre que les contraintes structurelles sur les certificats, souvent motivées par des applications cryptographiques (jeux compilés), peuvent fondamentalement altérer les propriétés de convergence de la hiérarchie NPA.

• Modestie des Revendications : L'auteur précise explicitement qu'il ne revendique pas l'échec de la sécurité des protocoles compilés ou l'échec du taux de clé finie. Les résultats concernent la précision des méthodes de certification à un tour et le degré algébrique requis pour les certificats exacts.
• Problèmes Ouverts : L'article reconnaît que bien qu'une borne inférieure asymptotique de $\Omega(\epsilon^{-1/2})$ soit prouvée, une borne supérieure exacte ou une preuve de fermeture exacte finie pour chaque tilt subcritique fixé reste ouverte. La saturation numérique suggère une croissance en racine carrée, mais une borne supérieure rigoureuse correspondant à cet exposant n'est pas établie.
• Correction de la Littérature : Ce travail affine la compréhension de la relation entre les hiérarchies standard et conditionnées, en corrigeant une assertion précédente sur l'égalité des valeurs de niveau un pour le CHSH titré et en clarifiant la distinction entre les filtrations POVM/localiseur et le quotient PVM brut utilisé ici.

En résumé, l'article établit que si les hiérarchies conditionnées par Alice peuvent être exactes à bas niveaux pour des régimes de paramètres spécifiques, elles souffrent d'une surcharge de degré non bornée près de la frontière de l'ensemble quantique, empêchant de remplacer universellement les hiérarchies standards pour les tâches de certification exacte.