Entanglement-based quantum communication complexity beyond Bell nonlocality

Abstract

Abstract Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks, such as parallel computation and circuit optimisation. Crucially, the communication overhead introduced by the allotment process should be minimised—a key motivation behind the communication complexity problem (CCP). Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. Furthermore, the connection between quantum CCPs and non-locality provides an information-theoretic insight into fundamental quantum mechanics. Here we connect quantum CCPs with a generalised non-locality framework—beyond Bell’s paradigmatic theorem—by incorporating the underlying causal structure, which governs the distributed task, into a so-called non-local hidden-variable model. We prove that a new class of communication complexity tasks can be associated with Bell-like inequalities, whose violation is both necessary and sufficient for a quantum gain. We experimentally implement a multipartite CCP akin to the guess-your-neighbour-input scenario, and demonstrate a quantum advantage when multipartite Greenberger-Horne-Zeilinger (GHZ) states are shared among three users.