ﻻ يوجد ملخص باللغة العربية
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $epsilon$, getting the 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 Newmans theorem [Inf. Proc. Let.91] in the dependence on the error parameter. 2) Using this we obtain a $(log(n/epsilon^2)+4)$-cost private-coin communication protocol that computes the $n$-bit Equality function, to error $epsilon$. This improves upon the $log(n/epsilon^3)+O(1)$ upper bound implied by Newmans theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.09], up to an additive $loglog(1/epsilon)+O(1)$. In the quantum model, 1) we exhibit a one-way protocol of cost $log(n/epsilon)+4$, that uses only pure states and computes the $n$-bit Equality function to error $epsilon$. This bound was implicitly already shown by Nayak [PhD thesis99]. 2) We show that any $epsilon$-error one-way protocol for $n$-bit Equality that uses only pure states communicates at least $log(n/epsilon)-loglog(1/epsilon)-O(1)$ qubits. 3) We exhibit a one-way protocol of cost $log(sqrt{n}/epsilon)+3$, that uses mixed states and computes the $n$-bit Equality function to error $epsilon$. This is also tight up to an additive $loglog(1/epsilon)+O(1)$, which follows from Alons result. Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix. This also implies improved upper bounds on these measures for the distributed SINK function, which was recently used to refute the randomized and quant
The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantu
We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access
In this paper, we study quantum query complexity of the following rather natural tripartite generalisations (in the spirit of the 3-sum problem) of the hidden shift and the set equality problems, which we call the 3-shift-sum and the 3-matching-sum p
We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-offs between the number of queries of quantum search algorithms, their
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1. We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with