Bornes quantiques pour les jeux XOR compilés et les jeux CHSH à $d$-résultats

Informations fondamentales

• ID de l'article : 2403.05502
• Titre : Quantum bounds for compiled XOR games and $d$-outcome CHSH games
• Auteurs : Matilde Baroni, Quoc-Huy Vu, Boris Bourdoncle, Eleni Diamanti, Damian Markham, Ivan Šupić
• Classification : quant-ph (physique quantique)
• Date de publication/Conférence : Accepté dans Quantum 2025-08-08
• Lien de l'article : https://arxiv.org/abs/2403.05502

Résumé

Les jeux non-locaux jouent un rôle crucial dans la théorie de l'information quantique, avec de nombreuses applications dans les protocoles d'authentification et de cryptographie. Kalai et al. (STOC 2023) ont introduit une procédure utilisant un schéma de chiffrement homomorphe quantique pour compiler les jeux non-locaux en preuves interactives à un seul prouveur, et ont démontré que leur méthode de compilation préserve les bornes classiques du jeu. Natarajan et Zhang (FOCS 2023) ont ensuite prouvé que pour le cas spécifique des jeux CHSH, les bornes quantiques sont préservées. Cet article étend les techniques de preuve de Natarajan et Zhang, démontrant que la procédure de compilation de Kalai et al. préserve les bornes quantiques pour deux classes de jeux : les jeux XOR et les jeux CHSH à $d$-résultats. Nous établissons également qu'il existe un jeu XOR pour toute paire de mesures de qubits, tel que sa probabilité de gain optimale peut servir d'auto-test pour cette paire de mesures spécifique.

Contexte et motivation de la recherche

Problème fondamental

Le problème fondamental que cette recherche vise à résoudre est : Comment convertir les outils d'authentification de non-localité de Bell, qui nécessitent plusieurs appareils spatialement séparés, en un cadre à appareil unique, tout en préservant l'avantage quantique ?

Importance du problème

1. Besoins pratiques : Bien que la non-localité de Bell fournisse théoriquement des garanties de sécurité informationnelle, elle nécessite au moins deux parties non-communicantes spatialement séparées, ce qui est extrêmement difficile expérimentalement
2. Compatibilité des plateformes de calcul : Les scénarios de type Bell existants sont incompatibles avec les plateformes de calcul quantique, car il est impossible d'imposer une séparation spatiale et une interdiction de communication sur un appareil intégré
3. Généralisation des outils d'authentification : La conversion des outils d'authentification de configurations multi-appareils à mono-appareil augmenterait considérablement leur applicabilité

Limitations des approches existantes

1. Exigence de séparation spatiale : La non-localité de Bell traditionnelle nécessite une séparation spatiale physique, limitant les scénarios d'application
2. Résultats théoriques limités : La méthode de compilation de Kalai et al. ne prouve que la préservation des bornes classiques, manquant de bornes supérieures quantiques
3. Restrictions aux jeux spécifiques : Les résultats de Natarajan et Zhang s'appliquent uniquement aux jeux CHSH, manquant de généralité

Motivation de la recherche

Utiliser le chiffrement homomorphe quantique (QHE) pour simuler la séparation spatiale en masquant les informations d'entrée complètes, afin de compiler les jeux non-locaux en preuves interactives à un seul prouveur, et prouver que cette compilation préserve les bornes quantiques.

Contributions principales

1. Extension du théorème de préservation des bornes quantiques : Preuve que la procédure de compilation de Kalai et al. préserve les bornes quantiques pour les jeux XOR et les jeux CHSH à $d$-résultats, avec une erreur qui est une fonction négligeable du paramètre de sécurité
2. Établissement du cadre de décomposition SOS cryptographique : Développement, basé sur les techniques de Natarajan et Zhang, d'une méthode de décomposition en somme de carrés (SOS) cryptographique applicable à une classe plus large de jeux
3. Réalisation d'auto-tests computationnels :
   • Auto-test pour toute paire de mesures de qubits
   • Auto-test pour trois observables de Pauli anti-commutantes
4. Fourniture de nouveaux outils théoriques : Introduction d'une application de pseudo-espérance (pseudo-expectation map) qui mappe les polynômes d'observables non-locales aux corrélations observées dans le jeu compilé

Détails de la méthode

Définition de la tâche

Entrée : Jeu non-local G, schéma de chiffrement homomorphe quantique QHE Sortie : Jeu compilé à un seul prouveur G' Contrainte : Préserver la borne quantique du jeu original, avec une erreur qui est une fonction négligeable du paramètre de sécurité κ

Cadre technique fondamental

1. Protocole de compilation (compilation KLVY)

Pour un jeu non-local bipartite :

• Premier tour : Le vérificateur envoie la question chiffrée $\bar{x} = \text{Enc}(x)$ au prouveur, reçoit la réponse chiffrée $\bar{a} = \text{Enc}(a)$
• Deuxième tour : Le vérificateur envoie la question en clair $y$ au prouveur, reçoit la réponse en clair $b$
• Jugement : Utilise le prédicat $V(\text{Dec}(\bar{a}), b|\text{Dec}(\bar{x}), y)$ pour déterminer le gain

2. Application de pseudo-espérance

Définition de l'opérateur linéaire $\tilde{E}$ qui mappe les polynômes homogènes de degré 2 des observables de mesure aux corrélations observées dans le jeu compilé :

$\tilde{E}[A_x B_y] = C_{x,y}, \quad \tilde{E}[B_y A_x] = C^T_{y,x}$

$\tilde{E}[A_x A_{x'}] = \delta_{x,x'}, \quad \tilde{E}[B_y B_{y'}] = S_{y,y'}$

où la matrice de corrélation est définie comme : $C = \sum_{x,y} \langle A_x, B_y \rangle |x\rangle\langle y|$

3. Décomposition SOS cryptographique

Pour les jeux XOR, utilisation de la décomposition SOS du Théorème 1 :

$\xi_q 1 - B_g = \sum_x \frac{\lambda_x}{2}\left(A_x - \sum_y F_{xy}B_y\right)^2 + P(\{B_y\}_y)$

Application de l'application de pseudo-espérance : $\tilde{E}[\xi_q 1 - B_g] = \sum_x \frac{\lambda_x}{2}\tilde{E}\left[\left(A_x - \sum_y F_{xy}B_y\right)^2\right] + \tilde{E}[P(\{B_y\}_y)]$

Lemmes clés

Lemme 8 : Pour les polynômes de la forme $P_x = A_x - \sum_y F_{xy}B_y$, il existe une fonction négligeable $\delta_{\text{QHE}}(\cdot)$ telle que : $\tilde{E}[P_x^\dagger P_x] \geq -\delta_{\text{QHE}}(\kappa)$

Points d'innovation technique

1. Forme spéciale de la décomposition SOS : Preuve que la décomposition SOS des jeux XOR peut s'écrire de manière à ce que chaque terme ne contienne qu'un seul observable d'Alice
2. Exploitation de la sécurité cryptographique : Utilisation astucieuse de la sécurité IND-CPA du QHE pour borner les valeurs de pseudo-espérance
3. Généralisation en dimension supérieure : Extension de la méthode aux inégalités SATWAP pour mesures à $d$-résultats

Configuration expérimentale

Cadre de vérification théorique

Cet article est principalement un travail théorique, avec vérification par preuve mathématique :

1. Classe des jeux XOR : Vérification de la propriété de préservation des bornes quantiques pour tous les jeux XOR
2. Jeux d-CHSH : Vérification de la préservation des bornes quantiques pour l'inégalité SATWAP
3. Protocoles d'auto-test : Construction de jeux compilés spécifiques réalisant l'auto-test de mesures

Critères d'évaluation

1. Préservation des bornes quantiques : La différence entre la probabilité de gain quantique optimale du jeu compilé et celle du jeu original est seulement $\text{negl}(\kappa)$
2. Robustesse de l'auto-test : Bornes d'erreur d'auto-test sous bruit et paramètre de sécurité fini
3. Efficacité computationnelle : Réalisabilité en temps polynomial quantique de la stratégie du prouveur

Résultats principaux

1. Préservation des bornes quantiques pour les jeux XOR (Théorème 3)

Résultat : Étant donné un jeu XOR avec déviation quantique optimale $\xi_q$, la déviation quantique optimale du jeu XOR compilé est $\xi_q + \delta_{\text{QHE}}(\kappa)$, où $\delta_{\text{QHE}}(\cdot)$ est une fonction négligeable.

2. Inégalité SATWAP de dimension $d$ (Théorème 4)

Résultat : Pour l'inégalité de Bell SATWAP de dimension $d$, si $d$ est polynomial par rapport au paramètre de sécurité κ, alors la borne quantique de l'inégalité SATWAP compilée est $(\beta^{\text{SATWAP}}_d)_q + \theta(\kappa)$, où $\theta(\cdot)$ est une fonction négligeable.

3. Auto-test pour toute paire de mesures de qubits

Résultat : Pour chaque paire d'observables de qubits, il existe un jeu XOR G tel que dans le protocole compilé G', tout prouveur en temps polynomial gagnant avec probabilité au moins $\omega_q(G) - \epsilon$ doit implémenter des opérateurs de mesure dans la plage $O(\sqrt{\epsilon}, \text{negl}(\kappa))$, jusqu'à isométrie locale.

4. Auto-test pour trois observables de Pauli anti-commutantes

Résultat : Le protocole compilé basé sur l'inégalité de Bell élégante peut auto-tester trois mesures de Pauli anti-commutantes $\sigma_x, \sigma_y, \sigma_z$, avec erreur $O(\delta, \text{negl}(\kappa))$.

Travaux connexes

Compilation de jeux non-locaux

1. Kalai et al. (2023) : Première proposition d'utilisation du QHE pour compiler les jeux non-locaux, preuve de la préservation des bornes classiques
2. Natarajan et Zhang (2023) : Preuve de la préservation des bornes quantiques pour les jeux CHSH
3. Brakerski et al. (2023) : Analyse des bornes quantiques pour des jeux CHSH spécifiques

Applications de la non-localité de Bell

1. Distribution quantique de clés sans appareil : Distribution de clés sécurisée basée sur la violation des inégalités de Bell
2. Authentification d'aléatoire : Authentification d'aléa véritable utilisant la non-localité de Bell
3. Auto-test : Authentification des appareils quantiques par violation des inégalités de Bell

Chiffrement homomorphe quantique

1. Mahadev (2018) : Première proposition du concept de chiffrement homomorphe quantique
2. Brakerski (2018) : Schéma QHE amélioré avec tolérance au bruit

Conclusion et discussion

Conclusions principales

1. Extension de la généralité : Extension réussie des résultats de préservation des bornes quantiques d'un unique jeu CHSH à toute la classe des jeux XOR et des jeux CHSH à $d$-résultats
2. Réalisation d'auto-tests : Première réalisation d'auto-tests computationnels pour toute paire de mesures de qubits en cadre à un seul prouveur
3. Outils théoriques : Établissement d'un cadre mathématique général pour analyser les bornes quantiques des jeux compilés

Limitations

1. Restrictions sur la forme de décomposition SOS : La méthode s'applique uniquement aux jeux ayant une forme spécifique de décomposition SOS (chaque terme ne contenant qu'un seul observable d'Alice)
2. Dépendance du paramètre de sécurité : La précision des résultats dépend du paramètre de sécurité du schéma QHE
3. Jeux multipartites : Extension non encore réalisée aux jeux non-locaux avec plus de deux parties

Directions futures

1. Classes de jeux générales : Étude de la question si la procédure de compilation préserve les bornes quantiques pour tous les jeux non-locaux
2. Extension multipartite : Généralisation de la méthode aux jeux non-locaux multipartites
3. Applications pratiques : Implémentation et test du protocole de compilation sur des plateformes quantiques réelles

Évaluation approfondie

Avantages

1. Rigueur théorique : Preuves mathématiques complètes, ligne technique claire
2. Valeur pratique : Résolution d'un problème pratique important dans les applications de la non-localité de Bell
3. Innovation méthodologique : Combinaison astucieuse de la sécurité cryptographique et de la théorie de l'information quantique
4. Complétude des résultats : Non seulement preuve de la préservation des bornes quantiques, mais aussi réalisation de fonctionnalités d'auto-test

Insuffisances

1. Portée d'application : La méthode impose des exigences spéciales sur la forme de la décomposition SOS, limitant la généralité
2. Vérification expérimentale : Absence de vérification expérimentale sur des appareils quantiques réels
3. Analyse d'efficacité : Analyse insuffisante de la complexité computationnelle du protocole compilé

Portée d'impact

1. Contribution théorique : Fourniture de nouveaux outils pour la recherche interdisciplinaire entre cryptographie quantique et théorie de la complexité
2. Perspectives d'application : Ouverture de nouvelles voies pour l'authentification d'appareils sur les plateformes de calcul quantique intégrées
3. Direction de recherche : Promotion de la recherche théorique sur la compilation de protocoles quantiques

Scénarios d'application

1. Authentification d'appareils quantiques : Authentification des performances des appareils quantiques sur les plateformes de calcul quantique intégrées
2. Protocoles de cryptographie quantique : Conception de schémas de cryptographie quantique basés sur des hypothèses computationnelles
3. Vérification d'avantage quantique : Vérification de l'avantage du calcul quantique en environnement mono-appareil

Références

1. Kalai et al. "Quantum advantage from any non-local game." STOC 2023
2. Natarajan and Zhang. "Bounding the quantum value of compiled nonlocal games: From CHSH to BQP verification." FOCS 2023
3. Mahadev. "Classical homomorphic encryption for quantum circuits." FOCS 2018
4. Brakerski. "Quantum FHE (almost) as secure as classical." CRYPTO 2018

Cet article apporte une contribution importante au domaine interdisciplinaire de la théorie de l'information quantique et de la cryptographie. Par des techniques mathématiques astucieuses, il convertit les protocoles quantiques multipartites en protocoles monopartites tout en préservant l'avantage quantique, fournissant une base théorique importante pour les applications pratiques du calcul quantique.