Quantum Contextuality Provides Communication Complexity Advantage
- 24 February 2023
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 130 (8) , 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.Keywords
All Related Versions
Funding Information
- National Postdoctoral Program for Innovative Talents (PDF/2020/001682)
- Universidad de Sevilla (US-15097)
- Bundesministerium für Forschung, Technologie und Raumfahrt
- QuantERA (SECRET)
- Ministerio de Economía y Competitividad (PCI2019-111885-2)
- Ministerio de Ciencia e Innovación (PID2020–113738GB-I00)
- Department of Science and Technology, Ministry of Science and Technology, India (DST/ICPS/QuEST/2018/98)
This publication has 46 references indexed in Scilit:
- Universality of State-Independent Violation of Correlation Inequalities for Noncontextual TheoriesPhysical Review Letters, 2009
- Preparation Contextuality Powers Parity-Oblivious MultiplexingPhysical Review Letters, 2009
- Experimentally Testable State-Independent Quantum ContextualityPhysical Review Letters, 2008
- Simple Test for Hidden Variables in Spin-1 SystemsPhysical Review Letters, 2008
- Quantum FingerprintingPhysical Review Letters, 2001
- Randomized graph products, chromatic numbers, and the Lov sz ?-functionCombinatorica, 1997
- Quantum cryptography based on Bell’s theoremPhysical Review Letters, 1991
- Two simple proofs of the Kochen-Specker theoremJournal of Physics A: General Physics, 1991
- Forbidden IntersectionsTransactions of the American Mathematical Society, 1987
- On the Problem of Hidden Variables in Quantum MechanicsReviews of Modern Physics, 1966