ECCC-Report TR17-152https://eccc.weizmann.ac.il/report/2017/152Comments and Revisions published for TR17-152en-usTue, 12 Dec 2017 12:43:14 +0200
Comment 1
| One-way quantum communication complexity with inner product gadget |
Srijita Kundu
https://eccc.weizmann.ac.il/report/2017/152#comment1This note is prepared based on the article titled ``One-way Communication and Non-adaptive Decision Tree" (TR17-152) by Swagato Sanyal. We show that the technique developed in the aforementioned paper to lower bound one-way randomized communication complexity can be be extended to prove one-way quantum communication complexity with shared entanglement of any total query function $f : \{0,1\}^n \to \{0,1\}$ that depends on all its input bits, composed with the inner product gadget $\mathrm{IP}_m$ of size $m \geq 2$, is $\Omega(nm)$.Tue, 12 Dec 2017 12:43:14 +0200https://eccc.weizmann.ac.il/report/2017/152#comment1
Paper TR17-152
| One-way Communication and Non-adaptive Decision Tree |
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2017/152Let $f$ be a Boolean function on $n$-bits, and $\mathsf{IP}$ the inner-product function on $2b$ bits. Let $f^{\mathsf{IP}}:=f \circ \mathsf{IP}^n$ be the two party function obtained by composing $f$ with $\mathsf{IP}$. In this work we bound the one-way communication complexity of $f^{\IP}$ in terms of the non-adaptive query complexity of $f$, from below. Similar results are known for general communication protocols and adaptive decision trees, when the arity of the inner function (inner-product in our case) is at least logarithmic in $n$. We prove analogous results for one-way communication as long as $b$ is a large enough constant. Let $\sR_{\cc, \epsilon}^{\rightarrow}(\cdot)$ and $\sD_{\cc}^\rightarrow(\cdot)$ denote the randomized $\epsilon$-error and deterministic one-way communication complexity respectively. Let $\sD_{\dt}^\rightarrow(\cdot)$ denote the deterministic non-adaptive query complexity. Let $\rH_{\bin}(\cdot)$ denote the binary entropy function. We prove that
\begin{itemize}
\item If $f$ is a \emph{total} Boolean function and $b \geq 2$, then $\sR^{\rightarrow}_{\cc, \epsilon}(f^{\mathsf{IP}}) \geq (1-\rH_{\bin}(\epsilon))n(b-1)$.
\item If $f$ is a partial Boolean function and $b \geq 4$, then $\sD_{\cc}^\rightarrow(f^{\mathsf{IP}})=\Omega(b \cdot \sD_{\dt}^\rightarrow(f))$.
\end{itemize}Wed, 11 Oct 2017 19:20:02 +0300https://eccc.weizmann.ac.il/report/2017/152