Random Access Codes 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 a variant called parity-oblivious random acres 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 form the single bits x_i. We provide the optimal quantum parity-oblivious random access codes and show that they are asymptotically better than the optimal classical ones. For this, we relate such encodings to a non-local game and provide tight bounds for the success probability of the non-local game via semi-definite programming. Our results provide a large non-contextuality inequality violation and resolve the main open question in [Spekkens et al., Phys. Review Letters, 2009].
Random Access Codes 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 a variant called parity-oblivious random acres 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 form the single bits x_i. We provide the optimal quantum parity-oblivious random access codes and show that they are asymptotically better than the optimal classical ones. For this, we relate such encodings to a non-local game and provide tight bounds for the success probability of the non-local game via semi-definite programming. Our results provide a large non-contextuality inequality violation and resolve the main open question in [Spekkens et al., Phys. Review Letters, 2009].
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 , such that Bob, when receiving the state , can choose any bit and recover the input bit x i with high probability. Here we study two variants: parity-oblivious random access codes (RACs), 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 RACs, 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 RACs 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 et al (2009 Phys. Rev. Lett. 102 010401 ). Second, we provide the optimal bounds for even-parity-oblivious RACs 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 RACs, the cryptographic property holds also in the device independent model.
A (quantum) random access code ((Q)RAC) is a scheme that encodes n bits into m (qu)bits such that any of the n bits can be recovered with a worst case probability p>21. We generalize (Q)RACs to a scheme encoding nd-levels into m (quantum) d-levels such that any d-level can be recovered with the probability for every wrong outcome value being less than d1. We construct explicit solutions for all $n\ensuremath{\le}\frac{{d}^{2m}\ensuremath{-}1}{d\ensuremath{-}1}$. For d=2, the constructions coincide with those previously known. We show that the (Q)RACs are d-parity oblivious, generalizing ordinary parity obliviousness. We further investigate optimization of the success probabilities. For d=2, we use the measure operators of the previously best-known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal $(n={4}^{m}\ensuremath{-}1,m,p)$ QRACs, $p=\frac{1}{2}{1+{[{(\sqrt{3}+1)}^{m}\ensuremath{-}1]}^{\ensuremath{-}1}}$ is possible, and show that it is an upper bound for the measure operators that we use. We then compare (n,m,pq) QRACs with classical (n,2m,pc) RACs. We can always find ${p}_{q}\ensuremath{\ge}{p}_{c}$, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different (n,2,p) QRACs, we see the same trade-off, as the best p values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.
A (Quantum) Random Access Code ((Q)RAC) is a scheme that encodes n bits into m (qu)bits such that any of the n bits can be recovered with a worst case probability p>21. Such a code is denoted by the triple (n,m,p). It is known that n<4m for all QRACs and n<2m for classical RACs. These bounds are also known to be tight, as explicit constructions exist for n=4m−1 and n=2m−1 for quantum and classical codes respectively. We generalize (Q)RACs to a scheme encoding nd-levels into m (qu)-d-levels such that any d-level can be recovered with the probability for every wrong outcome value being less than d1. We construct explicit solutions for all n≤d−1d2m−1. For d=2, the constructions coincide with those previously known. We show that the (Q)RACs are d-parity-oblivious, generalizing ordinary parity-obliviousness. We further investigate optimization of the success probabilities. For d=2, we use the measure operators of the previously best known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal (n=4m−1,m,p) QRACs, p=21+(3+1)m−11 is possible and show that it is an upper bound for the measure operators that we use. When we compare (n,m,pq) QRACs with classical (n,2m,pc) RACs, we can always find pq≥pc, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different (n,2,p) QRACs, we see the same trade-off, as the best p values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity-obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.
A random access code (RAC) encodes an L-bit string into a k-bit message, L>k, so that any requested bit can be recovered with high probability; a quantum RAC (QRAC) uses k qubits instead. We give a geometric characterization of optimal classical (L,k)-RACs under average and worst-case decoding criteria. The average criterion is reduced to choosing 2k representatives in {0,1}L, while the worst-case criterion is reduced to a minimax problem over 2k points in [0,1]L with a distance-like objective. This framework proves optimality for several parameter families, with many optimal constructions arising from standard infinite families of binary linear codes. It also yields two explicit classical--quantum separations. First, for every L>1, we construct a (L,1)-QRAC whose average decoding success probability strictly exceeds the optimal classical value. Second, for the family (2k−1,k), we prove worst-case optimality of a classical RAC and construct a QRAC with strictly larger worst-case success probability. For the family (L,L−1), the framework identifies a classical RAC that is average-case optimal and, under a stated conjecture, also worst-case optimal. The same viewpoint further recovers explicit (L,L−1)-QRACs attaining a previously conjectured upper-bound value.
The quantum ontological feature of contextuality apart from being central to foundations of quantum theory forms the basis of quantum advantage in a multitude of information processing tasks. In particular, the contextuality of preparation procedures was shown to power a particular two-party information processing task “parity oblivious multiplexing” (Spekkens et al. Phys Rev Lett 102:010401 (2009). Specifically, it was shown that there exists a limit to how well any preparation noncontextual theory can perform in this task. This limit constitutes a noncontextuality inequality. Moreover, the authors demonstrated quantum violation of this inequality along with preparation contextuality associated with the ontic description underlying two-level completely mixed quantum state. In this work, we extend these arguments to apply to arbitrary dimensions by introducing a class of two-party information processing tasks, namely d-level parity oblivious random access codes. We analytically obtain classical (or equivalently preparation noncontextual) bounds on the success probability for these tasks for arbitrary d. For each value of d, this bound constitutes a unique noncontextuality inequality. Remarkably, these bounds are independent of the amount of communication. Furthermore, we find a classical protocol utilizing a dc=d -dimensional classical message which saturates this bound. In order to establish nontriviality of these inequalities, we provide evidence of significant quantum violations. Specifically, by numerical techniques, we show that for d=3,…,10 , the noncontextuality bound is violated by quantum theory. (1) We provide explicit quantum protocols which violate the associated noncontextuality inequality for d=3,4,5 employing dq=d -leveled quantum systems. (2) Using see-saw semi-definite programming (SDP) technique, we find evidence (lower bounds) of significant quantum violation of these inequalities for d=3,…,10 . (3) With the help of state-of-the-art (NPA-hierarchy like) SDP technique, we provide upper bounds (independent of the dimension of the involved quantum systems) on quantum violation for d=3,…,10 . The introduced class of information tasks, thus, provides for operational depiction of preparation contextuality of the ontic description underlying mixed higher dimensional quantum systems.
Abstract The parity-oblivious random-access-code (PORAC) is a class of communication games involving a sender (Alice) and a receiver (Bob). In such games, Alice’s amount of communication to Bob is constraint by the parity-oblivious (PO) conditions, so that the parity information of her inputs remains oblivious to Bob. The PO condition in an operational theory is equivalently represented in an ontological model that satisfies the preparation noncontextuality. In this paper, we provide a nontrivial generalization of the existing two-level PORAC and derive the winning probability of the game in the preparation noncontextual ontological model. We demonstrate that the quantum theory outperforms the preparation noncontextual model by predicting higher winning probability in our generalized PORAC.