Quantum contextuality provides communication complexity advantage
arXiv:2205.03308 · doi:10.1103/PhysRevLett.130.080802
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.
arXiv comment6+9 pages. Close to the published version
References in corpus (36)
- Quantum cryptography: Public key distribution and coin tossing
- Quantum fingerprinting
- Contextuality for preparations, transformations, and unsharp measurements
- Non-locality and Communication Complexity
- Contextuality supplies the magic for quantum computation
- A simple test for hidden variables in spin-1 system
- Experimentally testable state-independent quantum contextuality
- Bell-Kochen-Specker theorem: A proof with 18 vectors
- Graph-Theoretic Approach to Quantum Correlations
- Semi-device-independent security of one-way quantum key distribution
- State-independent proof of Kochen-Specker theorem with 13 rays
- Preparation contextuality powers parity-oblivious multiplexing
- A self-testing quantum random number generator
- Kochen-Specker Contextuality
- Improving zero-error classical communication with entanglement
- Contextual advantage for state discrimination
- Universality of state-independent violation of correlation inequalities for noncontextual theories
- Semi-device independent random number expansion protocol with n to 1 quantum random access codes
- Quantifying Contextuality
- Generalized monogamy of contextual inequalities from the no-disturbance principle
- Optimal inequalities for state-independent contextuality
- Memory cost of quantum contextuality
- Fundamental monogamy relation between contextuality and nonlocality
- State independent contextuality advances one-way communication
- Simple method for experimentally testing any form of quantum contextuality
- Robust self-testing of quantum systems via noncontextuality inequalities
- Necessary and sufficient condition for quantum state-independent contextuality
- Optimal quantum preparation contextuality in -bit parity-oblivious multiplexing task
- Converting contextuality into nonlocality
- Optimal classical simulation of state-independent quantum contextuality
- Necessary and sufficient conditions for state-independent measurement contextual scenarios
- Quantum key distribution protocol based on contextuality monogamy
- Quantum Advantage in Information Retrieval
- Sum-of-squares decompositions for a family of noncontextuality inequalities and self-testing of quantum devices
- Activation of monogamy in non-locality using local contextuality
- More randomness from a prepare-and-measure scenario with independent devices
Cited by in corpus (27)
- Semi-definite programming and quantum information
- Quantum cryptography beyond key distribution: theory and experiment
- Certifying sets of quantum observables with any full-rank state
- Quantum Advantages in (n,d)->1 Random Access Codes
- 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
- Lifting noncontextuality inequalities
- Optimal Measurement Structures for Contextuality Applications
- Generalised Kochen-Specker Theorem for Finite Non-Deterministic Outcome Assignments
- 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
- Classifying Measurement Incompatibility under Classical Pre- and Post-Processing Operations
- Convexity of noncontextual wirings and how they order the set of correlations
- 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
- Certified Quantumness via Single-Shot Temporal Measurements
- Quantum Advantage in Identifying the Parity of Permutations with Certainty
- Quantum advantage in zero-error function computation with side information
- Contextuality from the vacuum