論文の概要: On relating one-way classical and quantum communication complexities
- arxiv url: http://arxiv.org/abs/2107.11623v4
- Date: Mon, 8 May 2023 20:27:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-10 20:58:34.220006
- Title: On relating one-way classical and quantum communication complexities
- Title（参考訳）: 一方向古典的および量子的通信複雑性に関する考察
- Authors: Naresh Goud Boddu, Rahul Jain and Han-Hsuan Lin
- Abstract要約: 通信複雑性とは、関数入力が複数のパーティに分散されるときに、関数を計算するのに必要な通信量である。
量子情報の基本的な問題は、一方通行の量子と古典的な通信の複雑さの関係である。
- 参考スコア（独自算出の注目度）: 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.\]
- Abstract（参考訳）: コミュニケーションの複雑さは、関数入力が複数のパーティに分散されたときに関数を計算するのに必要な通信量である。
最も単純な形式では、Alice と Bob は関数 $f(x,y)$ を計算し、Alice は$x$ を、Bob は$y$ を与えられ、Alice から Bob へのメッセージは 1 つしか許されない。
量子情報における基本的な問題は、一方通行の量子と古典的通信の複雑さの関係である。つまり、アリスがビット文字列ではなく量子状態を送信する場合、メッセージの長さはどのくらい短くなるのか?
この質問に対して、下記の結果で若干の進展がある。
f: \mathcal{x} \times \mathcal{y} \rightarrow \mathcal{z} \cup \{\bot\}$ を部分関数とし、$\mu$ は$f^{-1}(\mathcal{z})$ に含まれるサポートを持つ分布とする。
d=|\mathcal{z}|$ と書く。
$\mathsf{R}^{1,\mu}_\epsilon(f)$を$f$の古典的一方向通信複雑性、$\mathsf{Q}^{1,\mu}_\epsilon(f)$を$f$の量子一方向通信複雑性、$\mathsf{Q}^{1,\mu, *}_\epsilon(f)$を$fのエンタングルメント支援量子一方向通信複雑性、それぞれが$\epsilon$の分布誤差(平均誤差は$\mu$)を持つ。
1)$\mu$ が積分布であれば、$\eta > 0$ と $0 \leq \epsilon \leq 1-1/d$ であるなら、$$\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\}$, $\forall \epsilon, \eta > 0$ {\displaystyle $\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,$$} ここで \[\mathsf{CS}(f) = \max_{y} \min_{z\in \vert{0,\in \vert{0,\end{x~x\y}=\vert \vert{z} \vert \vert{z} となる。
\]
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Quantum Sabotage Complexity [0.7812210699650152]
ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。
f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
論文 参考訳（メタデータ） (2024-08-22T17:57:58Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions [22.847963422230155]
ノイズの多いクエリを使って$n$変数の関数を計算することの問題を考察する。
我々は, [ (1 pm o(1)) fracnlog frac1deltaD_mathsfKL(p | 1-p) ] のクエリ数が十分であり,両関数の計算に必要であることを示す。
論文 参考訳（メタデータ） (2023-09-07T19:37:52Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Matching upper bounds on symmetric predicates in quantum communication
complexity [0.0]
共役共役が許されるとき、f circ G = f(G)mathrmQCC_mathrmE(G)) という形の関数の量子通信複雑性に焦点を当てる。
我々は,同じ文が共用絡み合いを持たないことを示し,その結果を一般化する。
論文 参考訳（メタデータ） (2023-01-01T08:30:35Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳（メタデータ） (2021-09-21T13:19:04Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - A Direct Product Theorem for One-Way Quantum Communication [6.891238879512672]
一般関係 $fsubseteqmathcalXtimesmathcalYtimesmathcalZ$ の一方交絡支援量子通信複雑性に対する直積定理を証明する。
私たちが知っている限りでは、これは量子通信に対する最初の直接積定理である。
論文 参考訳（メタデータ） (2020-08-20T13:31:41Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。