Quantum communication complexity advantage implies violation of a Bell inequality

Abstract

We obtain a general connection between a quantum advantage in communication complexity and non-locality. We show that given any protocol offering a (sufficiently large) quantum advantage in communication complexity, there exists a way of obtaining measurement statistics which violate some Bell inequality. Our main tool is port-based teleportation. If the gap between quantum and classical communication complexity can grow arbitrarily large, the ratio of the quantum value to the classical value of the Bell quantity becomes unbounded with the increase in the number of inputs and outputs.

main text did not change. Modified the acknowledgements section

References in corpus (5)

• Advances in Quantum Teleportation
• Asymptotic teleportation scheme as a universal programmable quantum processor
• Remote preparation of quantum states
• Quantum teleportation scheme by selecting one of multiple output ports
• Better Non-Local Games from Hidden Matching

Cited by in corpus (36)

• Advances in Quantum Teleportation
• Demonstration of Einstein-Podolsky-Rosen Steering with Enhanced Subchannel Discrimination
• Port-based teleportation in arbitrary dimension
• Preparation contextuality as an essential feature underlying quantum communication advantage
• High-dimensional quantum communication complexity beyond strategies based on Bell's theorem
• Efficient multi port-based teleportation schemes
• Oblivious communication game, self-testing of projective and non-projective measurements and certification of randomness
• Quantum communication complexity beyond Bell nonlocality
• Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?
• Bounds on the power of proofs and advice in general physical theories
• Multiport based teleportation -- transmission of a large amount of quantum information
• The Magical Number Seven: An Unexpected Dimensional Threshold in Quantum Communication Complexity
• Higher dimensional communication complexity problems: classical protocols vs quantum ones based on Bell's Theorem or prepare-transmit-measure schemes
• Complexity of causal order structure in distributed quantum information processing and its trade-off with entanglement
• Quantum cryptography beyond key distribution: theory and experiment
• Optimality of the pretty good measurement for port-based teleportation
• Optimal Multi-port-based Teleportation Schemes
• Quantum advantages of communication complexity from Bell nonlocality
• Adaptive advantage in entanglement-assisted communications
• Robust Bell inequalities from communication complexity
• Bounding the persistency of the nonlocality of W states
• Unbounded quantum advantage in communication complexity measured by distinguishability
• Minimal Port-based Teleportation
• Entangled Rendezvous: A Possible Application of Bell Non-Locality For Mobile Agents on Networks
• The information cost of quantum memoryless protocols
• Semi-device-independent certification of quantum non-Markovianity using sequential Random Access Codes
• Port-based entanglement teleportation via noisy resource states
• Teleportation of Post-Selected Quantum States
• Port-Based State Preparation and Applications
• Port-based telecloning of an unknown quantum state
• From port-based teleportation to Frobenius reciprocity theorem: partially reduced irreducible representations and their applications
• Asymptotic teleportation schemes bridging between standard and port-based teleportation
• A resource theory of asynchronous quantum information processing
• Oracle problems as communication tasks and optimization of quantum algorithms
• On the distinguishability of geometrically uniform quantum states
• Square-root measurements and degradation of the resource state in port-based teleportation scheme