Quantum communication complexity beyond Bell nonlocality

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 nonlocality provides an information-theoretic insights into fundamental quantum mechanics. Here we connect quantum CCPs with a generalised nonlocality framework -- beyond the paradigmatic Bell's theorem -- by incorporating the underlying causal structure, which governs the distributed task, into a so-called nonlocal hidden variable model. We prove that a new class of communication complexity tasks can be associated to 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.

21 pages, 5 figures

References in corpus (9)

• The Quantum Internet
• Ground-to-satellite quantum teleportation
• Bounding the set of quantum correlations
• Quantifying multipartite nonlocality
• Correlations in entanglement-assisted prepare-and-measure scenarios
• Bell scenarios with communication
• Semi-device-independent certification of entanglement in superdense coding
• Experimental quantum "Guess my Number" protocol using multiphoton entanglement
• Multistage games and Bell scenarios with communication

Cited by in corpus (7)

• A Variational Approach to the Quantum Separability Problem
• The future of secure communications: device independence in quantum key distribution
• The power of qutrits for non-adaptive measurement-based quantum computing
• The sum of entanglement and subsystem coherence is invariant under quantum reference frame transformations
• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement
• Robust and bright polarization-entangled photon sources exploiting non-critical phase matching without periodic poling
• Experimental Efficient Source-Independent Quantum Conference Key Agreement