Entanglement-based quantum communication complexity beyond Bell nonlocality

Agradecimentos: We acknowledge the John Templeton Foundation via the Grant Q-CAUSAL No. 61084, the Serrapilheira Institute (Grant No. Serra-1708-15763), the Brazilian National Council for Scientific and Technological Development (CNPq) via the National Institute for Science and Technology on Quantum Information (INCT-IQ), Grants Nos. 307295/2020-6 and 406574/2018-9, the Brazilian agencies MCTIC and MEC, the São Paulo Research Foundation FAPESP (Grant No. 2018/07258-7). This work was supported by the UK Engineering and Physical Sciences Research Council (Grant Nos. EP/N002962/1 and EP/T001011/1). F.G. acknowledges studentship funding from EPSRC under Grant No. EP/L015110/1 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 CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO - CNPQ FUNDAÇÃO DE AMPARO À PESQUISA DO ESTADO DE SÃO PAULO - FAPESP Aberto