Entanglement-based quantum communication complexity beyond Bell nonlocality

Joseph Ho, George Moreno, Samuraí Brito, Francesco Graffitti, Christopher L. Morrison, Ranieri Nery, Alexander Pickston, Massimiliano Proietti, Rafael Rabelo, Alessandro Fedrizzi, Rafael Chaves*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)
64 Downloads (Pure)


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.

Original languageEnglish
Article number13
Journalnpj Quantum Information
Publication statusPublished - 3 Feb 2022

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Statistical and Nonlinear Physics
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Entanglement-based quantum communication complexity beyond Bell nonlocality'. Together they form a unique fingerprint.

Cite this