Quantum Random Access Codes for Boolean Functions

Abstract

An $n\stackrel{p}{\mapsto }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 \emph{noise stability} of the Boolean function $f$. Moreover, we give an \emph{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.

arXiv commentFinal version to appear in Quantum. Small improvements to Theorem 23

References in corpus (24)

• Information Causality as a Physical Principle
• Semi-device-independent security of one-way quantum key distribution
• Preparation contextuality powers parity-oblivious multiplexing
• A lower bound on the dimension of a quantum system given measured data
• Quantum Network Coding
• Quantum Random Access Codes using Single $d$-level Systems
• Semi-device independent random number expansion without entanglement
• Entanglement assisted random access codes
• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
• Self-testing mutually unbiased bases in the prepare-and-measure scenario
• (4,1)-Quantum Random Access Coding Does Not Exist
• Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval
• Experimental Tests of Classical and Quantum Dimensions
• Experimental Demonstration of Sequential Quantum Random Access Codes
• Certifying an irreducible 1024-dimensional photonic state using refined dimension witnesses
• Spatial versus Sequential Correlations for Random Access Coding
• Extrema of discrete Wigner functions and applications
• When Are Popescu-Rohrlich Boxes and Random Access Codes Equivalent?
• Complementarity between entanglement-assisted and quantum distributed random access code
• Improved Classical and Quantum Random Access Codes
• Unbounded-error One-way Classical and Quantum Communication Complexity
• Self-testing mutually unbiased bases in higher dimensions with space-division multiplexing optical fiber technology
• Nonsignaling quantum random access code boxes
• Multiparty quantum random access codes

Cited by in corpus (11)

• Quantum Advantage in Information Retrieval
• Mutually Unbiased Balanced Functions & Generalized Random Access Codes
• Expressivity of Variational Quantum Machine Learning on the Boolean Cube
• Certification of qubits in the prepare-and-measure scenario with large input alphabet and connections with the Grothendieck constant
• Quantum Advantages in (n,d)->1 Random Access Codes
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Simple and general bounds on quantum random access codes
• Biased Random Access Codes
• Random access test as an identifier of nonclassicality
• Two instances of random access code in the quantum regime
• The Interplay between Quantum Contextuality and Wigner Negativity