On relating one-way classical and quantum communication complexities
- URL: http://arxiv.org/abs/2107.11623v5
- Date: Fri, 12 May 2023 05:32:21 GMT
- Title: On relating one-way classical and quantum communication complexities
- Authors: Naresh Goud Boddu, Rahul Jain and Han-Hsuan Lin
- Abstract summary: Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties.
A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities.
- Score: 6.316693022958221
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Communication complexity is the amount of communication needed to compute a
function when the function inputs are distributed over multiple parties. In its
simplest form, one-way communication complexity, Alice and Bob compute a
function $f(x,y)$, where $x$ is given to Alice and $y$ is given to Bob, and
only one message from Alice to Bob is allowed. A fundamental question in
quantum information is the relationship between one-way quantum and classical
communication complexities, i.e., how much shorter the message can be if Alice
is sending a quantum state instead of bit strings? We make some progress
towards this question with the following results.
Let $f: \mathcal{X} \times \mathcal{Y} \rightarrow \mathcal{Z} \cup \{\bot\}$
be a partial function and $\mu$ be a distribution with support contained in
$f^{-1}(\mathcal{Z})$. Denote $d=|\mathcal{Z}|$. Let
$\mathsf{R}^{1,\mu}_\epsilon(f)$ be the classical one-way communication
complexity of $f$; $\mathsf{Q}^{1,\mu}_\epsilon(f)$ be the quantum one-way
communication complexity of $f$ and $\mathsf{Q}^{1,\mu, *}_\epsilon(f)$ be the
entanglement-assisted quantum one-way communication complexity of $f$, each
with distributional error (average error over $\mu$) at most $\epsilon$. We
show:
1) If $\mu$ is a product distribution, $\eta > 0$ and $0 \leq \epsilon \leq
1-1/d$, then,
$$\mathsf{R}^{1,\mu}_{2\epsilon -d\epsilon^2/(d-1)+ \eta}(f) \leq
2\mathsf{Q}^{1,\mu, *}_{\epsilon}(f) + O(\log\log (1/\eta))\enspace.$$
2)If $\mu$ is a non-product distribution and $\mathcal{Z}=\{ 0,1\}$, then
$\forall \epsilon, \eta > 0$ such that $\epsilon/\eta + \eta < 0.5$,
$$\mathsf{R}^{1,\mu}_{3\eta}(f) = O(\mathsf{Q}^{1,\mu}_{{\epsilon}}(f) \cdot
\mathsf{CS}(f)/\eta^3)\enspace,$$
where
\[\mathsf{CS}(f) = \max_{y} \min_{z\in\{0,1\}} \vert \{x~|~f(x,y)=z\} \vert
\enspace.\]
Related papers
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization.
Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires.
We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
arXiv Detail & Related papers (2024-06-07T08:26:31Z) - Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions [22.847963422230155]
We consider the problem of computing a function of $n$ variables using noisy queries.
We show that an expected number of queries of [ (1 pm o(1)) fracnlog frac1deltaD_mathsfKL(p | 1-p) ] is both sufficient and necessary to compute both functions.
arXiv Detail & Related papers (2023-09-07T19:37:52Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model.
For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits.
For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
arXiv Detail & Related papers (2023-07-11T08:51:53Z) - Matching upper bounds on symmetric predicates in quantum communication
complexity [0.0]
We focus on the quantum communication complexity of functions of the form $f circ G = f(G)mathrmQCC_mathrmE(G)) when the parties are allowed to use shared entanglement.
We show that the same statement holds emphwithout shared entanglement, which generalizes their result.
arXiv Detail & Related papers (2023-01-01T08:30:35Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
arXiv Detail & Related papers (2022-03-17T23:52:08Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
arXiv Detail & Related papers (2021-09-21T13:19:04Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals.
Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
arXiv Detail & Related papers (2021-08-19T16:16:48Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph.
We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
arXiv Detail & Related papers (2021-03-17T00:59:33Z) - A Direct Product Theorem for One-Way Quantum Communication [6.891238879512672]
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $fsubseteqmathcalXtimesmathcalYtimesmathcalZ$.
As far as we are aware, this is the first direct product theorem for quantum communication.
arXiv Detail & Related papers (2020-08-20T13:31:41Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model.
Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
arXiv Detail & Related papers (2020-02-09T03:39:46Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.