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.]
تحميل البحث