Quantum contextuality provides communication complexity advantage
Authors:
Preprint
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.Keywords
All Related Versions
This publication has 43 references indexed in Scilit:
- Communication Complexity2020
- State independent contextuality advances one-way communicationNew Journal of Physics, 2019
- Quantum cryptography: Public key distribution and coin tossingTheoretical Computer Science, 2014
- Contextuality supplies the ‘magic’ for quantum computationNature, 2014
- Memory cost of quantum contextualityNew Journal of Physics, 2011
- Contextuality for preparations, transformations, and unsharp measurementsPhysical Review A, 2005
- Quantum communication and complexityTheoretical Computer Science, 2002
- Randomized graph products, chromatic numbers, and the Lov sz ?-functionCombinatorica, 1997
- Bell-Kochen-Specker theorem: A proof with 18 vectorsPhysics Letters A, 1996
- Two simple proofs of the Kochen-Specker theoremJournal of Physics A: General Physics, 1991