An n↦pm random access code (RAC) is an encoding of n bits into m bits such that any initial bit can be recovered with probability at least p , while in a quantum RAC (QRAC), the n bits are encoded into m qubits. Since its proposal, the idea of RACs was generalized in many different ways, e.g. allowing the use of shared entanglement (called entanglement-assisted random access code, or simply EARAC) or recovering multiple bits instead of one. In this paper we generalize the idea of RACs to recovering the value of a given Boolean function f on any subset of fixed size of the initial bits, which we call f -random access codes. We study and give protocols for f -random access codes with classical ( f -RAC) and quantum ( f -QRAC) encoding, together with many different resources, e.g. private or shared randomness, shared entanglement ( f -EARAC) and Popescu-Rohrlich boxes ( f -PRRAC). The success probability of our protocols is characterized by the noise stability of the Boolean function f . Moreover, we give an upper bound on the success probability of any f -QRAC with shared randomness that matches its success probability up to a multiplicative constant (and f -RACs by extension), meaning that quantum protocols can only achieve a limited advantage over their classical counterparts.
An n↦pm random access code (RAC) is an encoding of n bits into m bits such that any initial bit can be recovered with probability at least p , while in a quantum RAC (QRAC), the n bits are encoded into m qubits. Since its proposal, the idea of RACs was generalized in many different ways, e.g. allowing the use of shared entanglement (called entanglement-assisted random access code, or simply EARAC) or recovering multiple bits instead of one. In this paper we generalize the idea of RACs to recovering the value of a given Boolean function f on any subset of fixed size of the initial bits, which we call f -random access codes. We study and give protocols for f -random access codes with classical ( f -RAC) and quantum ( f -QRAC) encoding, together with many different resources, e.g. private or shared randomness, shared entanglement ( f -EARAC) and Popescu-Rohrlich boxes ( f -PRRAC). The success probability of our protocols is characterized by the noise stability of the Boolean function f . Moreover, we give an upper bound on the success probability of any f -QRAC with shared randomness that matches its success probability up to a multiplicative constant (and f -RACs by extension), meaning that quantum protocols can only achieve a limited advantage over their classical counterparts.
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 (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 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.
$n\ensuremath{\rightarrow}m$ random access code (RAC) is an information task to encode an n-bit random message into a shorter m-bit string. Resulting from the compression loss from n to m bits, there exists success probabilities for the string receiver to recover any bits of the initial message. It has been shown that success probabilities of bit recovery can be enhanced by employing quantum resources. Here we present experimental realizations of $2\ensuremath{\rightarrow}1$ and $3\ensuremath{\rightarrow}1$ distributed entanglement-assisted random access codes (EARACs) with a two-photon entangled source. The average success probabilities obtained in our experiment are 0.8491(41) for a $2\ensuremath{\rightarrow}1$ EARAC and 0.7724(34) for a $3\ensuremath{\rightarrow}1$ EARAC, exceeding the classical counterparts, respectively. Moreover, through the existing experimental data, success probabilities for n varying from 4 to 10 (m=1) are estimated.
Collaborative communication tasks such as random access codes (RACs) employing quantum resources have manifested great potential in enhancing information processing capabilities beyond the classical limitations. The two quantum variants of RACs, namely, quantum random access code (QRAC) and the entanglement-assisted random access code (EARAC), have demonstrated equal prowess for a number of tasks. However, there do exist specific cases where one outperforms the other. In this article, we study a family of $3\ensuremath{\rightarrow}1$ distributed RACs [J. Bowles, N. Brunner, and M. Paw\l{}owski, Phys. Rev. A 92, 022351 (2015)] and present its general construction of both the QRAC and the EARAC. We demonstrate that, depending on the function of inputs that is sought, if QRAC achieves the maximal success probability then EARAC fails to do so and vice versa. Moreover, a tripartite Bell-type inequality associated with the EARAC variants reveals the genuine multipartite nonlocality exhibited by our protocol. We conclude with an experimental realization of the $3\ensuremath{\rightarrow}1$ distributed QRAC that achieves higher success probabilities than the maximum possible with EARACs for a number of tasks.
Abstract We consider two classes of quantum generalisations of random access code (RAC) and study the bounds for probabilities of success for such tasks. It provides a useful framework for the study of certain information processing tasks with constrained resources. The first class is based on a RAC with quantum inputs and output known as the no-signalling quantum RAC (NS-QRAC) box (Grudka et al 2015 Phys. Rev. A 92 052312), where unbounded entanglement and constrained classical communication are allowed. We show that it can be seen as quantum teleportation with constrained classical communication and provide a lower quantum bound for the success probability. We consider two modifications to the NS-QRAC scenario: the first, where unbounded entanglement and constrained quantum communication is allowed and the second, where bounded entanglement and unconstrained classical communication is allowed. We find a monogamy relation for the transmission fidelities, which—in contrast to the usual communication schemes—involves multiple senders and a single receiver. We provide an upper bounds for the latter and a lower one for the former. The second class is based on a RAC with a quantum channel and shared entanglement (Tavakoli et al 2021 PRX Quantum 2 040357). We study the set of tasks where two inputs made of two digits of d-base are encoded over a qudit and a maximally entangled state. We show that such tasks can be seen as quantum dense-coding with constrained quantum communication and explicit protocols, which give lower quantum bounds for the tasks’ efficiency, in dimensions d = 2 , 3 , 4 . The employed encoding utilises Gray codes.