Quantum contextuality provides communication complexity advantage

Abstract

Despite the conceptual importance of contextuality in quantum mechanics, there is a hitherto limited number of applications requiring contextuality but not entanglement. Here, we show that for any quantum state and observables of sufficiently small dimensions producing contextuality, there exists a communication task with quantum advantage. Conversely, any quantum advantage in this task admits a proof of contextuality whenever an additional condition holds. We further show that given any set of observables allowing for quantum state-independent contextuality, there exists a class of communication tasks wherein the difference between classical and quantum communication complexities increases as the number of inputs grows. Finally, we show how to convert each of these communication tasks into a semi-device-independent protocol for quantum key distribution.

6+9 pages. Close to the published version

References in corpus (6)

• A simple test for hidden variables in spin-1 system
• Experimentally testable state-independent quantum contextuality
• Semi-device-independent security of one-way quantum key distribution
• Preparation contextuality powers parity-oblivious multiplexing
• Universality of state-independent violation of correlation inequalities for noncontextual theories
• Necessary and sufficient condition for quantum state-independent contextuality

Cited by in corpus (26)

• Semi-definite programming and quantum information
• Quantum cryptography beyond key distribution: theory and experiment
• Certifying sets of quantum observables with any full-rank state
• Optimal and tight Bell inequalities for state-independent contextuality sets
• Unbounded quantum advantage in communication complexity measured by distinguishability
• Semi-device-independent certification of quantum non-Markovianity using sequential Random Access Codes
• Generalised Kochen-Specker Theorem for Finite Non-Deterministic Outcome Assignments
• Optimal Measurement Structures for Contextuality Applications
• Lifting noncontextuality inequalities
• Efficient Computation of Generalized Noncontextual Polytopes and Quantum violation of their Facet Inequalities
• Harvesting Contextuality from the Vacuum
• Secure One-Sided Device-Independent Quantum Key Distribution Under Collective Attacks with Enhanced Robustness
• Robust certification of quantum instruments through a sequential communication game
• Contextuality of Quantum Error-Correcting Codes
• Single and entangled atomic systems in thermal bath and the Fulling-Davies-Unruh effect
• A new heuristic approach for contextuality degree estimates and its four- to six-qubit portrayals
• Convexity of noncontextual wirings and how they order the set of correlations
• Classifying Measurement Incompatibility under Classical Pre- and Post-Processing Operations
• Probe of Generic Quantum Contextuality and Nonlocal Resources for Qubits
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• Limits of Classical correlations and Quantum advantages under (Anti-)Distinguishability constraints in Multipartite Communication
• Noncontextual Pauli Hamiltonians
• Quantum Advantage in Identifying the Parity of Permutations with Certainty
• Certified Quantumness via Single-Shot Temporal Measurements
• Contextuality from the vacuum
• Quantum advantage in zero-error function computation with side information