論文の概要: A Direct Product Theorem for One-Way Quantum Communication
- arxiv url: http://arxiv.org/abs/2008.08963v1
- Date: Thu, 20 Aug 2020 13:31:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 12:27:56.409094
- Title: A Direct Product Theorem for One-Way Quantum Communication
- Title（参考訳）: ワンウェイ量子通信のための直接製品理論
- Authors: Rahul Jain and Srijita Kundu
- Abstract要約: 一般関係 $fsubseteqmathcalXtimesmathcalYtimesmathcalZ$ の一方交絡支援量子通信複雑性に対する直積定理を証明する。
私たちが知っている限りでは、これは量子通信に対する最初の直接積定理である。
- 参考スコア（独自算出の注目度）: 6.891238879512672
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove a direct product theorem for the one-way entanglement-assisted
quantum communication complexity of a general relation
$f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any
$\varepsilon, \zeta > 0$ and any $k\geq1$, we show that \[
\mathrm{Q}^1_{1-(1-\varepsilon)^{\Omega(\zeta^6k/\log|\mathcal{Z}|)}}(f^k) =
\Omega\left(k\left(\zeta^5\cdot\mathrm{Q}^1_{\varepsilon + 12\zeta}(f) -
\log\log(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}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B},
\mathsf{V})$ where $q$ is a distribution on $\mathcal{X}\times\mathcal{Y}$
anchored on any one side with anchoring probability $\zeta$, then \[
\omega^*(G^k) = \left(1 - (1-\omega^*(G))^5\right)^{\Omega\left(\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.
- Abstract（参考訳）: 一般関係 $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$ の一方交絡支援量子通信複雑性に対する直積定理を証明する。
任意の$\varepsilon, \zeta > 0$ および任意の$k\geq1$ に対して、 \[ \mathrm{q}^1_{1-(1-\varepsilon)^{\omega(\zeta^6k/\log|\mathcal{z}|)}}(f^k) = \omega\left(k\left(\zeta^5\cdot\mathrm{q}^1_{\varepsilon + 12\zeta}(f)\log\log(1/\zeta)\right)\right),\] ここで$\mathrm{q}^1_{\varepsilon}(f)$は、最悪のケースエラーで$f$の1方向エンタングルメント支援の量子通信の複雑さを表し、$k$k$の並列インスタンスを示す。
私たちが知る限り、これは量子通信に対する最初の直接積定理である。
本手法は,jain,pereszl\'{e}nyi,yaoによる製品分布,bavarian,vidick,yuenによるアンカー分布,jain,radhakrishnan,senによる量子プロトコルのメッセージ圧縮といった2プレイヤー非ローカルゲームのエンタングル値に対する並列反復定理に着想を得たものである。
特に、任意のゲーム$G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})$に対して、$q$は$\mathcal{X}\times\mathcal{Y}$の分布であり、アンカリング確率$\zeta$の任意の面にアンカリングされた場合、 \[ \omega^*(G^k) = \left(1 - (1-\omega^*(G)^5\right)^{\Omega\left(\frac {\zeta^2 k}{\log(|\mathcal{A}||\cdot|\mathcal{B}|\right)$である。
これはバイエルン、ヴィディック、ユアンの結果の一般化であり、彼は両側に固定されたゲームに対して平行反復定理を証明し、その証明を単純化する可能性がある。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Learning junta distributions and quantum junta states, and QAC$^0$ circuits [0.0]
本稿では,量子ジャンタ分布の学習問題,量子カウンター部,量子ジャンタ状態,QAC$0$回路について考察する。
誤差$varepsilon$を全変動距離で学習できることが示される。
また、$Omega(4k+log (n)/varepsilon2)$コピーの低い境界も証明します。
論文 参考訳（メタデータ） (2024-10-21T09:39:20Z) - The complexity of approximate (coarse) correlated equilibrium for incomplete information games [16.96984593866157]
不完全情報ゲームにおける近似平衡の分散学習の複雑さについて検討する。
我々の下限は、$epsilon$-approximate $mathitco$ correlation equilibriumというより簡単な解の概念にも当てはまる。
論文 参考訳（メタデータ） (2024-06-04T14:35:27Z) - Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳（メタデータ） (2024-02-23T12:22:03Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Matrix concentration inequalities and efficiency of random universal
sets of quantum gates [0.0]
ランダム集合 $mathcalS の部分集合 U(d)$ に対して、$mathcalS$ が $delta$-approximate $t$-design となる確率の有界性を与える。
正確な$t$-designから引き出された$mathcalS$に対して、$delta$-approximate $t$-designが不等式$mathbbPleft(delta geq x right)leq 2D_tを満たす確率を示す。
論文 参考訳（メタデータ） (2022-02-10T23:44:09Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳（メタデータ） (2021-12-14T16:29:53Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - On relating one-way classical and quantum communication complexities [6.316693022958221]
通信複雑性とは、関数入力が複数のパーティに分散されるときに、関数を計算するのに必要な通信量である。
量子情報の基本的な問題は、一方通行の量子と古典的な通信の複雑さの関係である。
論文 参考訳（メタデータ） (2021-07-24T14:35:09Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。