A Communication-Efficient Nonlocal Measurement With Application to Communication Complexity and Bipartite Gate Capacities

Two dual questions in quantum information theory are to determine the communication cost of simulating a bipartite unitary gate, and to determine their communication capacities. We present a bipartite unitary gate with two surprising properties: 1) simulating it with the assistance of unlimited EPR pairs requires far more communication than with a better choice of entangled state, and 2) its communication capacity is far lower than its capacity to create entanglement. This suggests that 1) unlimited EPR pairs are not the most general model of entanglement assistance for two-party communication tasks, and 2) the entangling and communicating abilities of a unitary interaction can vary nearly independently. The technical contribution behind these results is a communication-efficient protocol for measuring whether an unknown shared state lies in a specified rank-one subspace or its orthogonal complement.