2021/07/25 by Olivier Lalonde, Nikhil S. Mande, Lalonde, Olivier +3 · 1 voice · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.2107.11806
arxiv published 2021/07/25 · arxiv updated 2023/10/18
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting optimal constant factors in the leading terms in a number of different models. In the randomized model, 1) we give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error, at a small additive cost. This is an improvement over Newman's theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. 2) Using this we obtain a (log(n/ε2)+4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ε. This improves upon the log(n/ε3)+O(1) upper bound implied by Newman's theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive loglog(1/ε)+O(1). In the quantum model, 1) we exhibit a one-way protocol of cost log(n/ε)+4, that uses only pure states and computes the n-bit Equality function to error ε. This bound was implicitly already shown by Nayak [PhD thesis'99]. 2) We show that any ε-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ε)-loglog(1/ε)-O(1) qubits. 3) We exhibit a one-way protocol of cost log(√(n)/ε)+3, that uses mixed states and computes the n-bit Equality function to error ε. This is also tight up to an additive loglog(1/ε)+O(1), which follows from Alon's result. 4) We study the number of EPR pairs required to be shared in an entanglement-assisted one-way protocol. Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix.