(4,1)-Quantum random access coding does not exist - one qubit is not enough to recover one of four bits

An (n, 1, p)-quantum random access (QRA) coding, introduced by Ambainis et al ( 1999 ACM Symp. Theory of Computing p 376), is the following communication system: the sender which has n-bit information encodes his/her information into one qubit, which is sent to the receiver. The receiver can recover any one bit of the original n bits correctly with probability at least p, through a certain decoding process based on positive operator-valued measures. Actually, Ambainis et al shows the existence of a ( 2,1,0.85)-QRA coding and also proves the impossibility of its classical counterpart. Chuang immediately extends it to a (3, 1, 0.79)-QRA coding and whether or not a (4, 1, p)-QRA coding such that p > 1/2 exists has been open since then. This paper gives a negative answer to this open question. Moreover, we generalize its negative answer for one-qubit encoding to the case of multiple-qubit encoding.