Dmitry Kravchenko

In a recent work [Phys. Rev. Lett. 114, 170502 (2015)], Tavakoli et al. derived interesting results by studying classical and quantum random access codes (RACs) in which the parties communicate higher-dimensional systems. They construct quantum RACs with a greater advantage over classical RACs compared to previously considered RACs with binary alphabets. However, these results crucially hinge upon an unproven assertion that the classical strategy "majority-encoding-identity-decoding" leads to the maximum average success probability achievable for classical RACs; in this work we provide a proof of this intuition. We characterize all optimal classical RACs and show that indeed ``majority-encoding-identity-decoding" is one among the several optimal strategies. Along with strengthening the results in Tavakoli et al., our result provides a firm basis for future research on this topic.