Optimal bounds for parity-oblivious random access codes

Abstract

Random access coding is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an $n$-bit string $x$, and wishes to encode $x$ into a quantum state ${\rho }_x$, such that Bob, when receiving the state ${\rho }_x$, can choose any bit $i\in [n]$ and recover the input bit $x_i$ with high probability. Here we study two variants: parity-oblivious random access codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input apart from the single bits $x_i$; and even-parity-oblivious random access codes, where Bob cannot infer any information about the parity of any even-size subset of bits of the input. In this paper, we provide the optimal bounds for parity-oblivious quantum random access codes and show that they are asymptotically better than the optimal classical ones. Our results provide a large non-contextuality inequality violation and resolve the main open problem in a work of Spekkens, Buzacott, Keehn, Toner, and Pryde (2009). Second, we provide the optimal bounds for even-parity-oblivious random access codes by proving their equivalence to a non-local game and by providing tight bounds for the success probability of the non-local game via semidefinite programming. In the case of even-parity-oblivious random access codes, the cryptographic property holds also in the device-independent model.

Version 3. Added discussion about device-independent security

Cited by in corpus (38)

• Kochen-Specker Contextuality
• Contextual advantage for state discrimination
• The Characterization of Noncontextuality in the Framework of Generalized Probabilistic Theories
• State independent contextuality advances one-way communication
• Measurement incompatibility and steering are necessary and sufficient for operational contextuality
• All the noncontextuality inequalities for arbitrary prepare-and-measure experiments with respect to any fixed sets of operational equivalences
• Why interference phenomena do not capture the essence of quantum theory
• Uniqueness of noncontextual models for stabilizer subtheories
• Quantum Advantage from Sequential-Transformation Contextuality
• Communication games reveal preparation contextuality
• Optimal quantum preparation contextuality in $n$-bit parity-oblivious multiplexing task
• Aspects of the phenomenology of interference that are genuinely nonclassical
• Noise-robust preparation contextuality shared between any number of observers via unsharp measurements
• Characterising and bounding the set of quantum behaviours in contextuality scenarios
• Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality
• Informationally restricted quantum correlations
• Deriving robust noncontextuality inequalities from algebraic proofs of the Kochen-Specker theorem: the Peres-Mermin square
• Causation does not explain contextuality
• Contextuality without incompatibility
• Contextuality in entanglement-assisted one-shot classical communication
• A structure theorem for generalized-noncontextual ontological models
• Quantum advantage for probabilistic one-time programs
• Quantum Advantage in Information Retrieval
• Mutually Unbiased Balanced Functions & Generalized Random Access Codes
• Improved Classical and Quantum Random Access Codes
• Noncontextuality Inequalities from Antidistinguishability
• Device-independent dimension tests in the prepare-and-measure scenario
• Contextuality as a Precondition for Quantum Entanglement
• A linear program for testing nonclassicality and an open-source implementation
• Contextuality with vanishing coherence and maximal robustness to dephasing
• A review and reformulation of macroscopic realism: resolving its deficiencies using the framework of generalized probabilistic theories
• Hiding Ignorance Using High Dimensions
• Using a resource theoretic perspective to witness and engineer quantum generalized contextuality for prepare-and-measure scenarios
• Role of fine-grained uncertainty in determining the limit of preparation contextuality
• Revealing quantum contextuality using a single measurement device
• Connecting XOR and XOR* games
• Emergence of noncontextuality under quantum Darwinism
• Quantum formalism on the plane: POVM-Toeplitz quantization, Naimark theorem and linear polarisation of the light