Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn relating one-way classical and quantum communication complexities
79
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $f: X times Y rightarrow {0,1,bot }$ be a partial function and $mu$ be a distribution with support contained in $f^{-1}(0) cup f^{-1}(1)$. Let $mathsf{D}^{1,mu}_epsilon(f)$ be the classical one-way communication complexity of $f$ with average error under $mu$ at most $epsilon$, $mathsf{Q}^{1,mu}_epsilon(f)$ be the quantum one-way communication complexity of $f$ with average error under $mu$ at most $epsilon$ and $mathsf{Q}^{1,mu, *}_epsilon(f)$ be the entanglement assisted one-way communication complexity of $f$ with average error under $mu$ at most $epsilon$. We show: 1. If $mu$ is a product distribution, then $forall epsilon, eta > 0$, $$mathsf{D}^{1,mu}_{2epsilon + eta}(f) leq mathsf{Q}^{1,mu, *}_{epsilon}(f) /eta+Obigl(log(mathsf{Q}^{1,mu, *}_{epsilon}(f))/etabigr).$$ 2. If $mu$ is a non-product distribution, then $forall epsilon, eta > 0$ such that $epsilon/eta + eta < 0.5$, $$mathsf{D}^{1,mu}_{3eta}(f) = O(mathsf{Q}^{1,mu}_{{epsilon}}(f) cdot mathsf{CS}(f)/eta^4)enspace,$$ where [mathsf{CS}(f) = max_{y} min_{zin{0,1}} { vert {x~|~f(x,y)=z} vert} enspace.]
rate research
Read More
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $fsubseteqmathcal{X}timesmathcal{Y}timesmathcal{Z}$. For any $varepsilon, zeta > 0$ and any $kgeq1$, we show that [ mathrm{Q}^1_{1-(1-varepsilon)^{Omega(zeta^6k/log|mathcal{Z}|)}}(f^k) = Omegaleft(kleft(zeta^5cdotmathrm{Q}^1_{varepsilon + 12zeta}(f) - loglog(1/zeta)right)right),] where $mathrm{Q}^1_{varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $varepsilon$ and $f^k$ denotes $k$ parallel instances of $f$. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszl{e}nyi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game $G = (q, mathcal{X}timesmathcal{Y}, mathcal{A}timesmathcal{B}, mathsf{V})$ where $q$ is a distribution on $mathcal{X}timesmathcal{Y}$ anchored on any one side with anchoring probability $zeta$, then [ omega^*(G^k) = left(1 - (1-omega^*(G))^5right)^{Omegaleft(frac{zeta^2 k}{log(|mathcal{A}|cdot|mathcal{B}|)}right)}] where $omega^*(G)$ represents the entangled value of the game $G$. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.
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 communication layouts: two-way interactive communication; one-way communication; simultaneous message passing (SMP). We demonstrate a functional problem, whose communication complexity is $O((log n)^2)$ in the quantum version of SMP and $tildeOmega(sqrt n)$ in the classical (randomised) version of SMP. Second, this work contributes to understanding the power of the weakest commonly studied regime of quantum communication $-$ SMP with quantum messages and without shared randomness (the latter restriction can be viewed as a somewhat artificial way of making the quantum model as weak as possible). Our function has an efficient solution in this regime as well, which means that even lacking shared randomness, quantum SMP can be exponentially stronger than its classical counterpart with shared randomness.
A relational bipartite communication problem is presented that has an efficient quantum simultaneous-messages protocol, but no efficient classical two-way protocol.
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on $2b$ bits. 1) If $f$ is a total Boolean function that depends on all of its inputs, the bounded-error one-way quantum communication complexity of $f circ IP$ equals $Omega(n(b-1))$. 2) If $f$ is a partial Boolean function, the deterministic one-way communication complexity of $f circ IP$ is at least $Omega(b cdot D_{dt}^{rightarrow}(f))$, where $D_{dt}^{rightarrow}(f)$ denotes the non-adaptive decision tree complexity of $f$. For our quantum lower bound, we show a lower bound on the VC-dimension of $f circ IP$, and then appeal to a result of Klauck [STOC00]. Our deterministic lower bound relies on a combinatorial result due to Frankl and Tokushige [Comb.99]. It is known due to a result of Montanaro and Osborne [arXiv09] that the deterministic one-way communication complexity of $f circ XOR_2$ equals the non-adaptive parity decision tree complexity of $f$. In contrast, we show the following with the gadget $AND_2$. 1) There exists a function for which even the randomized non-adaptive AND decision tree complexity of $f$ is exponentially large in the deterministic one-way communication complexity of $f circ AND_2$. 2) For symmetric functions $f$, the non-adaptive AND decision tree complexity of $f$ is at most quadratic in the (even two-way) communication complexity of $f circ AND_2$. In view of the first point, a lower bound on non-adaptive AND decision tree complexity of $f$ does not lift to a lower bound on one-way communication complexity of $f circ AND_2$. The proof of the first point above uses the well-studied Odd-Max-Bit function.
In 1999 Raz demonstrated a partial function that had an efficient quantum two-way communication protocol but no efficient classical two-way protocol and asked, whether there existed a function with an efficient quantum one-way protocol, but still no efficient classical two-way protocol. In 2010 Klartag and Regev demonstrated such a function and asked, whether there existed a function with an efficient quantum simultaneous-messages protocol, but still no efficient classical two-way protocol. In this work we answer the latter question affirmatively and present a partial function Shape, which can be computed by a protocol sending entangled simultaneous messages of poly-logarithmic size, and whose classical two-way complexity is lower bounded by a polynomial.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
