Quantum Random Access Codes for Boolean Functions

An n ->(p) m 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.

Automated summary

This paper generalizes the concept of random access codes to f-random access codes for recovering the value of a Boolean function on a subset of initial bits, providing protocols for classical and quantum encoding, as well as various resources. The success probability of the protocols is characterized by the noise stability of the Boolean function, and an upper bound on the success probability of quantum protocols with shared randomness is given, showing limited advantage over classical counterparts.