Higher dimensional communication complexity problems: classical protocols vs quantum ones based on Bell's Theorem or prepare-transmit-measure schemes
arXiv:1611.00977 · doi:10.1103/PhysRevA.95.042305
Abstract
Communication complexity problems (CCPs) are tasks in which separated parties attempt to compute a function whose inputs are distributed among the parties. Their communication is limited so that not all inputs can be sent. We show that broad classes of Bell inequalities can be mapped to CCPs and that a quantum violation of a Bell inequality is a necessary and sufficient condition for an enhancement of the related CCP beyond its classical limitation. However, one can implement CCPs by transmitting a quantum system, encoding no more information than is allowed in the CCP, and extract information by performing measurements. We show that for a large class of Bell inequalities, the improvement of the CCP associated to a quantum violation of a Bell inequality can be no greater than the improvement obtained from quantum prepare-transmit-measure strategies.
References in corpus (23)
- Random Numbers Certified by Bell's Theorem
- Bell inequalities for arbitrarily high dimensional systems
- From Bell's Theorem to Secure Quantum Key Distribution
- Non-locality and Communication Complexity
- A Relevant Two Qubit Bell Inequality Inequivalent to the CHSH Inequality
- Testing the Hilbert space dimension
- Device-independent tests of classical and quantum dimensions
- Semi-device-independent security of one-way quantum key distribution
- Violation of Bell's inequality: criterion for quantum communication complexity advantage
- Maximally Non-Local and Monogamous Quantum Correlations
- Quantum communication complexity protocol with two entangled qutrits
- Bell nonlocality and Bayesian game theory
- Multiparty Quantum Communication Complexity
- Semi-device independent random number expansion protocol with n to 1 quantum random access codes
- Entanglement assisted random access codes
- Quantum communication complexity advantage implies violation of a Bell inequality
- Experimental quantum communication complexity
- Spatial versus Sequential Correlations for Random Access Coding
- A feasible quantum communication complexity protocol
- Hyperbits: the information quasiparticles
- The Magical Number Seven: An Unexpected Dimensional Threshold in Quantum Communication Complexity
- Increased Certification of Semi-device Independent Random Numbers using Many Inputs and More Postprocessing
- Maximal Non-Classicality in Multi-Setting Bell Inequalities
Cited by in corpus (14)
- Sequential random access codes and self-testing of quantum measurement instruments
- High-dimensional quantum communication complexity beyond strategies based on Bell's theorem
- Correlations in entanglement-assisted prepare-and-measure scenarios
- Multi-dimensional entanglement generation with multi-core optical fibers
- Informationally restricted quantum correlations
- Informationally restricted correlations: a general framework for classical and quantum systems
- Entanglement in prepare-and-measure scenarios: many questions, a few answers
- Quantum communication complexity beyond Bell nonlocality
- Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?
- Complexity of causal order structure in distributed quantum information processing and its trade-off with entanglement
- Adaptive advantage in entanglement-assisted communications
- Quantum Blackjack or Can MIT Bring Down the House Again?
- Weak entanglement improves quantum communication using only product measurements
- Quantum inputs in the prepare-and-measure scenario and stochastic teleportation