标题： 量子纠缠与通信复杂性 显示英文标题

标题： Quantum Entanglement and Communication Complexity

摘要： 我们考虑一种多方通信复杂性场景的变体，其中各方被提供了一个额外的资源：处于纠缠量子态的粒子。 我们表明，尽管先验的量子纠缠不能用于模拟通信信道，但在某些情况下它可以减少函数的通信复杂性。 具体来说，我们表明，在三个方之间的某个特定函数（每个方拥有该函数输入的一部分）中，先验的量子纠缠使他们能够仅通过三方之间的三个比特通信来了解该函数的值，而没有量子纠缠时则需要四个比特的通信。 我们还表明，在一个特定的两方概率通信复杂性问题中，量子纠缠比仅使用经典随机相关性（而不是量子纠缠）所需的通信量更少。 这些结果与一个众所周知的事实形成鲜明对比，即量子纠缠不能用于实际模拟远距离各方之间的通信。 显示英文摘要

摘要： We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a prior quantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions in some cases. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables them to learn the value of the function with only three bits of communication occurring among the parties, whereas, without quantum entanglement, four bits of communication are necessary. We also show that, for a particular two-party probabilistic communication complexity problem, quantum entanglement results in less communication than is required with only classical random correlations (instead of quantum entanglement). These results are a noteworthy contrast to the well-known fact that quantum entanglement cannot be used to actually simulate communication among remote parties.