Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error
165
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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
rate research
Read More
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 quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of $O(1)$ vs. $sqrt{N}$ between quantum and randomized query complexities remain the state-of-the-art (where $N$ is the input length), leaving open the question of whether $O(1)$ vs. $N^{1/2+Omega(1)}$ separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis $k$-fold Forrelation problem. We show that our variant: (1) Can be solved by a quantum algorithm making $2^{O(k)}$ queries to the inputs. (2) Requires at least $tilde{Omega}(N^{2(k-1)/(3k-1)})$ queries for any randomized algorithm. For any constant $varepsilon>0$, this gives a $O(1)$ vs. $N^{2/3-varepsilon}$ separation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal $O(1)$ vs. $N^{1-varepsilon}$ separations between the quantum and randomized query complexities of partial Boolean functions.
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 to their inputs. More precisely, we give an explicit partial Boolean function that can be computed in the quantum-simultaneous-with-entanglement model of communication, however, every interactive randomized protocol is of exponentially larger cost. Furthermore, all the parties in the quantum protocol can be implemented by quantum circuits of small size with blackbox access to the inputs. Our result qualitatively matches the strongest known separation between quantum and classical communication complexity and is obtained using a quantum protocol where all parties are efficient.
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 problems. The 3-shift-sum problem is as follows: given a table of $3times n$ elements, is it possible to circularly shift its rows so that the sum of the elements in each column becomes zero? It is promised that, if this is not the case, then no 3 elements in the table sum up to zero. The 3-matching-sum problem is defined similarly, but it is allowed to arbitrarily permute elements within each row. For these problems, we prove lower bounds of $Omega(n^{1/3})$ and $Omega(sqrt n)$, respectively. The second lower bound is tight. The lower bounds are proven by a novel application of the dual learning graph framework and by using representation-theoretic tools.
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 error probability, the size of the search space, and the number of solutions in this space. Using this, we deduce new lower and upper bounds for quant
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 a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2. Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain honest-but-curious model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3. Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
