Communication complexity of functions plays a pivotal role in many computation and communication tasks. In this article we consider communication complexity of relations (CCR), where the receiver outputs one of many correct answers. We show that there exists a class of relations such that there is no advantage when the nature of the communication is quantum. However, a stronger version of the task, where the receiver is required to output all correct answers in different runs, entails quantum advantage. We call this task strong communication complexity of relations (S-CCR). Interestingly one of the examples of such a task imply quantum advantage in communication without contextuality. A randomized version of the task unveils curious ordering of communication and shared resources. Besides foundational importance, this work explores a number of applications of S-CCR such as dimension witnesses, detecting nonclassical resources under information constraints and detection of Mutually Unbiased Bases (MUBs).
Menu
