Nous étudions les complexités de communication randomisée et quantique de la fonction Égalité bien connue avec une petite probabilité d'erreur ε, en obtenant les facteurs constants optimaux dans les termes dominants dans différents modèles. Voici nos résultats dans le modèle randomisé : - Nous proposons une technique générale pour convertir des protocoles à pièce publique en protocoles à pièce privée en induisant une petite erreur multiplicative à un faible coût additif. C'est une amélioration par rapport au théorème de Newman Inf. Proc. Let.'91 concernant la dépendance au paramètre d'erreur. - En conséquence, nous obtenons un protocole de communication à pièce privée de coût (log(n/ε²) + 4) qui calcule la fonction Égalité sur n bits, avec une erreur ε. Cela améliore la borne supérieure log(n/ε³) + O(1) implicite dans le théorème de Newman, et correspond à la meilleure borne inférieure connue, issue d'Alon Comb. Prob. Comput.'09, à une erreur additive près de log log(1/ε) + O(1). Nos résultats dans différents modèles quantiques sont les suivants : - Nous présentons un protocole à sens unique avec log(n/ε) + 4 qubits de communication pour la fonction Égalité sur n bits, avec erreur ε, utilisant uniquement des états purs. Cette borne avait été implicitement démontrée par Nayak dans sa thèse PhD '99. - Nous donnons une borne inférieure quasi concordante : tout protocole ε-erreur à sens unique pour l'Égalité sur n bits utilisant uniquement des états purs communique au moins log(n/ε) - log log(1/ε) - O(1) qubits. - Nous exhibons un protocole à sens unique utilisant des états mixtes avec log(√n/ε) + 3 qubits de communication. Cette borne est serrée à un terme additif près de log log(1/ε) + O(1), comme le montre le résultat d'Alon. - Nous montrons un protocole à sens unique assisté par intrication réalisant une erreur ε avec ⌈log(1/ε)⌉ + 1 bits classiques de communication et ⌈log(√n/ε)⌉ + 4 paires EPR partagées entre Alice et Bob. Ceci correspond au coût de communication du protocole classique à pièce publique atteignant la même erreur, tout en améliorant la quantité d’intrication préalable nécessaire, qui est ⌈log(n/ε)⌉ + O(1) paires EPR partagées. Nos bornes supérieures impliquent également des bornes supérieures sur le rang approximatif, le rang non négatif approximatif et le rang psd approximatif de la matrice Identité. Par conséquent, nous obtenons également des bornes améliorées pour ces mesures sur une fonction récemment utilisée pour réfuter les versions randomisée et quantique de la conjecture du log-rang (Chattopadhyay, Mande et Sherif J. ACM'20, Sinha et de Wolf FOCS'19, Anshu, Boddu et Touchette FOCS'19).
Lalonde et al. (Fri,) ont étudié cette question.