论文标题
单向量子通信的直接产品定理
A Direct Product Theorem for One-Way Quantum Communication
论文作者
论文摘要
我们证明了一个直接的产品定理，用于单向纠缠辅助量子通信的复杂性$ f \ subseteq \ Mathcal {x} \ times \ times \ Mathcal {y} \ times \ times \ times \ Mathcal {Z} $。对于任何$ \ varepsilon，ζ> 0 $和任何$ k \ geq1 $ ω\ left（k \ left（ζ^5 \ cdot \ mathrm {q}^1 _ {\ varepsilon +12ζ}}（f） - \ log \ log \ log \ log \ log \ log \ log \ log \ log \ right） $ f $的纠缠辅助量子通信复杂性具有最差的案例错误$ \ varepsilon $和$ f^k $表示$ k $平行实例$ f $。 据我们所知，这是量子通信的第一个直接产品定理。我们的技术的灵感来自于双玩家非本地游戏的纠缠价值的平行重复定理，由于Jain，Pereszlényi和Yao的产品分布，以及由于巴伐利亚，Vidick和Yuen的锚定分布，以及由于尼斯兰的Quantum Protocts而引起的，以及由于Janakrishnan和radhakrishnan和Sears-compressions而言。 我们的技术还适用于纠缠的非本地游戏，这些游戏的输入分布锚定在任何一侧。特别是，我们表明，对于任何游戏，$ g =（q，\ nathcal {x} \ times \ mathcal {y}，\ Mathcal {a} \ times \ times \ mathcal {b}，\ mathsf {v} $在$ \ mathcal n pancal in y Mathcal and} $ {x pant y Maths \ n pancal in} $ {概率$ $ζ$，然后\ [ω^*（g^k）= \ left（1-（1-ω^*（g））^5 \ right）^{ω\ left（\ frac {ζ^2 k} {\ log（| $ω^*（g）$表示游戏$ g $的纠缠值。这是对巴伐利亚，维迪克和尤恩的结果的概括，他们证明了双方锚定的游戏的平行重复定理，并且有可能简化其证明。
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, ζ> 0$ and any $k\geq1$, we show that \[ \mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\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é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 $ζ$, then \[ ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}\] where $ω^*(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.
