  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.
