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.

arXiv comment21 pages, 5 figures

References in corpus (39)

• Quantum Cryptography
• The Quantum Internet
• Bell nonlocality
• Ground-to-satellite quantum teleportation
• Non-locality and Communication Complexity
• Bounding the set of quantum correlations
• Substituting Quantum Entanglement for Communication
• A limit on nonlocality in any world in which communication complexity is not trivial
• Bell-type inequalities to detect true n-body non-separability
• Violation of Bell's inequality: criterion for quantum communication complexity advantage
• Guess your neighbour's input: a multipartite non-local game with no quantum advantage
• Device-independent entanglement quantification and related applications
• Quantum communication complexity protocol with two entangled qutrits
• Genuine quantum nonlocality in the triangle network
• Detecting genuine multipartite quantum non-locality -- a simple approach and generalization to arbitrary dimension
• Quantum Entanglement and Communication Complexity
• Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity
• Quantifying multipartite nonlocality
• Entanglement assisted random access codes
• Pure down-conversion photons through sub-coherence length domain engineering
• Quantum violation of an instrumental test
• Causal hierarchy of multipartite Bell nonlocality
• Statistical properties of the quantum internet
• Quantum communication complexity advantage implies violation of a Bell inequality
• Single-qubit optical quantum fingerprinting
• Experimental quantum communication complexity
• The Extent of Multi-particle Quantum Non-locality
• Device-Independent Secret Sharing and a Stronger Form of Bell Nonlocality
• High-dimensional quantum communication complexity beyond strategies based on Bell's theorem
• Correlations in entanglement-assisted prepare-and-measure scenarios
• Bell scenarios with communication
• Semi-device-independent certification of entanglement in superdense coding
• Experimental demonstration of quantum advantage for one-way communication complexity
• Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?
• Higher dimensional communication complexity problems: classical protocols vs quantum ones based on Bell's Theorem or prepare-transmit-measure schemes
• Enhanced Multi-Qubit Phase Estimation in Noisy Environments by Local Encoding
• Experimental quantum "Guess my Number" protocol using multiphoton entanglement
• Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise
• 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