Entanglement-assisted random access codes

An $(n,m,p)$ random access code (RAC) makes it possible to encode $n$ bits in an $m$-bit message in such a way that a receiver of the message can guess any of the original $n$ bits with probability $p$ greater than $\frac{1}{2}$. In quantum RACs (QRACs), one transmits $n$ qubits. The full set of primitive entanglement-assisted random access codes (EARACs) is introduced, in which parties are allowed to share a two-qubit singlet. It is shown that via a concatenation of these, one can build for any $n$ an $(n,1,p)$ EARAC. QRACs for $n>3$ exist only if parties also share classical randomness. We show that EARACs outperform the best of known QRACs not only in the success probabilities but also in the amount of communication needed in the preparatory stage of the protocol. Upper bounds on the performance of EARACs are given and shown to limit also QRACs.

Figure 1

(a) Schematic representation of the two primitives: $(2,1)$ and $(3,1)$ EARAC. (b) Example of concatenation: $(5,1)$ EARAC. The probability of Bob guessing $a_2$ is higher than for $a_3$ since in the first case only $(2,1)$ EARAC primitives are used. These probabilities are, respectively, $P_2=\frac{1}{2}(1+\frac{1}{\sqrt{4}})$ and $P_3=\frac{1}{2}(1+\frac{1}{\sqrt{6}})$. The success probability associated with the whole code is the lower one. (c) One possible permutation of input bits for $(5,1)$ code. The choice of permutation is governed by the data from a shared random string. Having all possible permutations with the same probability results in an averaged version of the protocol with the success probability $p=\frac{2}{5}{P}_2+\frac{3}{5}{P}_3$, which is higher than in the previous case.