论文标题
分配测试的量子通信复杂性
Quantum Communication Complexity of Distribution Testing
论文作者
论文摘要
Andoni，Malkin和Nosatzki（ICALP'19）最近研究了离散分布接近的经典交流复杂性。在这个问题中，两个玩家分别从$ [n] $上的一个发行版中收到$ t $样本，目标是确定他们的两个发行版是相等的，还是在$ l_1 $ distance中分开$ε$ -FAR。在本文中，我们表明，当分布具有低$ L_2 $ -NORM时，此问题的量子通信复杂性为$ \ tilde {o}（n/（tε^2））$ QUBITS，对Andoni，Malkin和Nosatzki获得的经典通信复杂性具有二次改善。我们还使用模式矩阵方法获得了匹配的下限。让我们强调，各方收到的样本都是经典的，只有它们之间的交流才是量子。因此，我们的结果给出了一个设置，其中量子协议克服了纯经典样本的测试问题的经典协议。
The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP'19). In this problem, two players each receive $t$ samples from one distribution over $[n]$, and the goal is to decide whether their two distributions are equal, or are $ε$-far apart in the $l_1$-distance. In the present paper we show that the quantum communication complexity of this problem is $\tilde{O}(n/(tε^2))$ qubits when the distributions have low $l_2$-norm, which gives a quadratic improvement over the classical communication complexity obtained by Andoni, Malkin and Nosatzki. We also obtain a matching lower bound by using the pattern matrix method. Let us stress that the samples received by each of the parties are classical, and it is only communication between them that is quantum. Our results thus give one setting where quantum protocols overcome classical protocols for a testing problem with purely classical samples.
