Quantum Contextuality Provides Communication Complexity Advantage

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 commu-nication 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.

Automated summary

Despite the importance of contextuality in quantum mechanics, applications requiring contextuality but not entanglement are limited. We demonstrate that any quantum state and observables producing contextuality of sufficiently small dimensions can be used for a communication task with quantum advantage. Conversely, any quantum advantage in this task can prove contextuality under an additional condition. We further show that a set of observables allowing for quantum state-independent contextuality can be used in communication tasks where the difference between classical and quantum communication complexities increases with the number of inputs. Finally, we explain how these communication tasks can be converted into semi-device-independent protocols for quantum key distribution.