Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability

Résumé Technique : Algorithmes en Temps Polynomial pour les Normes de Tenseurs Nucléaires et la Séparabilité Multipartite

Énoncé du Problème
L'article traite de deux problèmes de calcul fondamentaux en optimisation de haute dimension et en théorie de l'information quantique :

1. Appartenance Faible à la Norme Nucléaire : Étant donné un tenseur $M \in (\mathbb{R}^d)^{\otimes k}$, décider si sa norme nucléaire est au plus égale à 1, ou si sa distance à la boule unité de la norme nucléaire est au moins $\epsilon$. La norme nucléaire est définie comme l'infimum de la somme des coefficients absolus dans une décomposition de rang un.
2. Séparabilité Quantique Multipartite : Étant donné un état quantique $k$-partite $\rho$ (soit via une description classique explicite, soit via des copies d'un état inconnu), décider si $\rho$ est séparable (c'est-à-dire une combinaison convexe d'états produits) ou si sa distance à l'ensemble des états séparables $\text{Sep}(d,k)$ est au moins $\epsilon$ dans la norme de Frobenius.

Ces deux problèmes sont connus pour être NP-difficiles lorsque la précision $\epsilon$ dépend de la dimension $d$ ou lorsque le nombre de parties $k$ fait partie de l'entrée dans des régimes spécifiques. Bien que des travaux précédents aient fourni des algorithmes quasi-polynomials ou des solutions en temps polynomial uniquement pour un $k$ fixé ou pour le cas bipartite ($k=2$), un algorithme général en temps polynomial pour des $k$ et $d$ arbitraires avec une précision additive constante est resté ouvert.

Méthodologie
Les auteurs développent deux cadres algorithmiques distincts : un approche classique déterministe pour les tenseurs donnés explicitement et une approche quantique pour les états donnés sous forme de copies.

1. Algorithmes Classiques (Déterministes)
Le cœur de l'approche classique est une technique de compression spectrale récursive qui considère le problème d'optimisation multilinéaire comme un jeu de multiprovaleurs coopératif.

• Compression Spectrale : Au lieu de discrétiser l'espace des stratégies de chacune des $k$ parties de manière indépendante (ce qui conduit à une explosion exponentielle), les auteurs compressent l'interaction entre les $j$ premières parties et les $k-j$ parties restantes dans un espace de « message » unique de faible dimension $V_j$.
• Compression de Préfixe Récursive : En appliquant une troncature spectrale (en ne conservant que les valeurs singulières supérieures à un seuil $\eta$) à travers les coupures entre $V_{j-1} \otimes H_j$ et les systèmes restants, ils maintiennent un message $p_j$ de dimension $O(\eta^{-2})$.
• Argument d'Énergie : Une innovation technique cruciale est un « argument d'énergie » qui borne l'erreur cumulative. En montrant que les carrés des normes des composantes rejetées forment une suite télescopique dont la somme est bornée par une quantité finie (la norme initiale), l'erreur totale est bornée par $O(\eta\sqrt{k})$ plutôt que par le $O(\eta k)$ habituel. Cela permet de fixer le seuil $\eta$ à $\Theta(\epsilon/\sqrt{k})$, maintenant ainsi la dimension des espaces de messages polynomiale en $k$.
• Méta-Algorithme : L'algorithme construit de manière itérative une couverture $\delta$ des messages atteignables. Pour de petits $k$ ($k \le d^2$), il utilise l'optimisation convexe sur des ensembles locaux. Pour de grands $k$ ($k > d^2$), il groupe les sites en blocs et effectue une recherche exhaustive au sein des blocs, en exploitant le fait que les dimensions locales sont petites par rapport à $k$.
• Réduction à l'Appartenance Faible : En utilisant l'algorithme de Frank-Wolfe, la solution du problème d'optimisation dual (maximisant $\langle M, \rho_1 \otimes \dots \otimes \rho_k \rangle$) est convertie en un test d'appartenance faible pour la norme nucléaire et la séparabilité.

2. Algorithmes Quantiques (Test de Propriété)
Pour le cas où l'entrée est un état inconnu $\rho$ fourni sous forme de copies, les auteurs proposent un protocole de réduction de dimension qui évite d'apprendre la base explicite de l'état.

• Optimisation de Produits Signés : L'algorithme étend l'apprentissageur de produits d'états de Bakshi et al. aux qudits et aux objectifs signés (maximisant $\text{Tr}((\rho - \sigma)\pi)$). Il construit une petite « couverture de produit de recouvrement » en utilisant une procédure de recherche locale qui identifie les états produits ayant un fort recouvrement avec la cible, en utilisant la tomographie de sous-espace et l'optimisation polynomiale.
• Réduction de Dimension par Filtrage : L'algorithme définit des opérateurs de « masse de Frobenius » locaux $A_j = \text{Tr}_{-j}(\rho^2)$. Il applique un canal quantique qui filtre les valeurs propres de $A_j$ inférieures à un seuil, effectuant ainsi une projection de l'état sur un sous-espace de faible dimension de dimension $q = O(k^2/\epsilon^4)$.
• Dualité de Schur-Weyl : Pour implémenter cette projection sans apprendre explicitement la base (ce qui prendrait un temps $\text{poly}(d)$), les auteurs utilisent la dualité de Schur-Weyl. En appliquant la transformée de Schur à $N$ copies de l'état, ils isolent le registre de permutation du registre de représentation unitaire, ce qui permet de rejeter le registre unitaire (qui contient l'information sur la base inconnue) et de le remplacer par un espace standard de faible dimension, effectuant ainsi une moyenne de Haar sur les unités locales. Cela préserve la distance par rapport à l'ensemble des états séparables tout en réduisant la dimension locale à $q$.
• Résultat : L'état réduit est ensuite injecté dans le testeur de faible dimension, atteignant un temps d'exécution et une complexité d'échantillonnage qui sont polynomiales en $k$ et $\log d$, mais indépendants de $d$.

Contributions Clés et Résultats

• Théorème 1.1 (Norme Nucléaire) : L'article présente le premier algorithme déterministe en temps polynomial pour l'appartenance faible dans la boule unité de la norme nucléaire de tenseurs d'ordre élevé avec une précision additive constante. Le temps d'exécution est $d^{O_\epsilon(k)}$.
• Théorème 1.2 (Séparabilité Quantique) : Les auteurs fournissent le premier algorithme déterministe en temps polynomial pour le problème d'appartenance faible multipartite dans la norme de Frobenius pour des $k$ et $d$ généraux, améliorant les résultats récents limités au cas bipartite. Le temps d'exécution est $d^{O_\epsilon(k)}$.
• Théorème 1.3 (Séparabilité à partir de Copies) : Un algorithme quantique est fourni qui distingue les états séparables des états distants d'au moins $\epsilon$ en norme de Frobenius en utilisant $k^{O_\epsilon(1)}$ copies et un temps de $k^{O_\epsilon(1)} \cdot \text{polylog}(d)$. Il s'agit du premier test de dimension indépendante pour l'appartenance faible dans l'ensemble des états séparables.
• Nouveauté Technique : Ce travail introduit un mécanisme de compression spectrale récursive qui atteint une borne d'erreur de $O(\eta\sqrt{k})$, contrastant avec les bornes $O(\eta k)$ précédentes qui limitaient les algorithmes au temps quasi-polynomial. Il démontre également comment la théorie des représentations (dualité de Schur-Weyl) peut être utilisée pour contourner le besoin de descriptions classiques explicites de sous-espaces de haute dimension dans les tests de propriétés quantiques.

Signification
L'article affirme résoudre le problème ouvert de la recherche d'algorithmes en temps polynomial pour la séparabilité multipartite et l'évaluation de la norme nucléaire dans le régime de précision constante. En combinant les perspectives de la théorie des jeux coopératifs avec la compression spectrale, les auteurs comblent le fossé entre le temps quasi-polynomial et le temps polynomial pour ces problèmes. Dans le cadre quantique, la capacité de tester la séparabilité avec un nombre de copies et un temps indépendant de la dimension locale $d$ (hormis un facteur polylogarithmique) représente une avancée significative par rapport aux limites connues et aux algorithmes dépendants de la dimension. Ce travail souligne que des mesures cohérentes à travers les copies sont nécessaires pour contourner les limites connues de la séparabilité en norme de trace, offrant une nouvelle voie pour le test de propriétés quantiques efficace.