ﻻ يوجد ملخص باللغة العربية
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.
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 ran
We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an $l$-player predicate $mathsf{V}$. In particular we show that for a distribution $p$ that is product across the input sets of the $l$ pla
The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say that a Bell inequality is normalized if its absolute value does not exceed 1 for any classical
This work addresses two problems in the context of two-party communication complexity of functions. First, it concludes the line of research, which can be viewed as demonstrating qualitative advantage of quantum communication in the three most common
We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the trace, determinant, or rank of a matrix or solving a linear system that