Résumé - Aspects computatoires du coefficient de contraction de la norme trace

Aspects computatoires du coefficient de contraction de la norme trace

2025-07-22 16:22:07

{"Idris Delsol","Omar Fawzi","Jan Kochanowski","Akshay Ramachandran"}

{quant-ph,cs.CC}

Cet article investigate la complexité computationnelle de l'approximation du coefficient de contraction de la norme trace (TNC) des canaux quantiques. Le TNC est une mesure de la manière dont un canal quantique peut enfreindre l'information, et il joue un rôle crucial pour comprendre les limites de la communication quantique et de la correction des erreurs. **Principales découvertes** : * **NP-hardness of TNC approximation** : L'article prouve que l'approximation du TNC d'un canal quantique à l'intérieur de n'importe quel facteur constant est NP-dure. Cela signifie que trouver une solution approchée à ce problème est inenvisageable en termes de calcul pour de grandes instances. * **Contrairement aux canaux classiques** : Ce résultat contrast avec le cas classique, où le TNC peut être approximé efficacement. * **NP-hardness of perfect encoding** : L'article montre également que déterminer la probabilité de succès optimale pour l'encodage d'un bit dans un système quantique bruité est NP-dure. Cela équivaut à décider si un graphe non commutatif a une cardinalité d'indépendance d'au moins 2, ce qui est également NP-dure. * **Hiérarchie convergente de bornes** : L'article établit une hiérarchie convergente de bornes supérieures par programmation sémi-définie sur le TNC. Cette hiérarchie offre un moyen d'obtenir des approximations de plus en plus précises du TNC de manière efficace. **Signification** : * **Compréhension de la communication quantique** : Les résultats de cet article fournissent des informations sur les limites fondamentales de la communication quantique et de la correction des erreurs. * **Complexité algorithmique** : L'article contribue à la compréhension de la complexité computationnelle des problèmes liés à la théorie de l'information quantique. * **Programmation sémi-définie** : L'article montre la puissance de la programmation sémi-définie pour approximer le TNC. **Points supplémentaires** : * L'article utilise une réduction à partir du Problème de Grothendieck Little pour prouver la NP-hardness de l'approximation du TNC. * L'article discute également du coefficient Doeblin quantique, qui est une autre borne supérieure sur le TNC. L'article montre que le coefficient Doeblin n'est pas toujours borné et fournit un exemple de canal où le coefficient Doeblin échoue à capturer le TNC. * L'article présente des exemples numériques illustrant les performances de la hiérarchie de bornes proposée. Dans l'ensemble, cet article apporte une contribution significative au domaine de la théorie de l'information quantique en étudiant la complexité computationnelle de l'approximation du TNC des canaux quantiques.