Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2105.03932 · Physical Review A

Mutually unbiased balanced functions and generalized random access codes

M Vaisakh, Ram Krishna Patra, Mukta Janpandit, Samrat Sen, Manik Banik, Anubhav Chaturvedi

Published Jul 21, 2021• 15 citations
arXivHTMLPDF

Abstract

Quantum resources and protocols are known to outperform their classical counterparts in a variety of communication and information processing tasks. Random access codes (RACs) are one such cryptographically significant family of bipartite communication tasks, wherein the sender encodes a data set (typically a string of input bits) onto a physical system of bounded dimension and transmits it to the receiver, who then attempts to guess a randomly chosen part of the sender's data set (typically one of the sender's input bits). In this work, we introduce a generalization of this task wherein the receiver, in addition to the individual input bits, aims to retrieve randomly chosen functions of the sender's input string. Specifically, we employ sets of mutually unbiased balanced functions, such that perfect knowledge of any one of the constituent functions yields no knowledge about the others. We investigate and bound the performance of (i) classical, (ii) quantum prepare and measure, and (iii) entanglement assisted classical communication (EACC) protocols for the resultant generalized RACs (GRACs). Finally, we detail the case of GRACs with three input bits and find maximal success probabilities for classical, quantum, and EACC protocols, along with the effect of noisy quantum channels on the performance of quantum protocols. Moreover, with the help of this case study, we reveal several characteristic properties of the GRACs which deviate from the standard RACs.

DOI
10.1103/physreva.104.012420

Related papers

Biased random access codes

Gabriel Pereira Alves, N. Gigena, Jędrzej Kaniewski

A random access code (RAC) is a communication task in which the sender encodes a random message into a shorter one to be decoded by the receiver so that a randomly chosen character of the original message is recovered with some probability. Both the message and the character to be recovered are assumed to be uniformly distributed. In this paper, we extend this protocol by allowing more general distributions of these inputs, which alters the encoding and decoding strategies optimizing the protocol performance, with either classical or quantum resources. We approach the problem of optimizing the performance of these biased RACs with both numerical and analytical tools. On the numerical front, we present algorithms that allow a numerical evaluation of the optimal performance over both classical and quantum strategies and provide a Python package designed to implement them, called RAC-tools. We then use this numerical tool to investigate single-parameter families of biased RACs in the ${n}^{2}\ensuremath{\mapsto}1$ and ${2}^{d}\ensuremath{\mapsto}1$ scenarios. For RACs in the ${n}^{2}\ensuremath{\mapsto}1$ scenario, we derive a general upper bound for the cases in which the inputs are not correlated, which coincides with the quantum value for $n=2$ and in some cases for $n=3$. Moreover, it is shown that attaining this upper bound self-tests pairs or triples of rank-1 projective measurements, respectively. An analogous upper bound is derived for the value of RACs in the ${2}^{d}\ensuremath{\mapsto}1$ scenario, which is shown to be always attainable using mutually unbiased measurements if the distribution of input strings is unbiased.

arXiv:2302.08494•Physical Review A•Oct 13, 2023•6 citations

Two instances of random access code in the quantum regime

Nitica Sakharwade, Michał Studziński, Michał Eckstein +1 more

Abstract We consider two classes of quantum generalisations of random access code (RAC) and study the bounds for probabilities of success for such tasks. It provides a useful framework for the study of certain information processing tasks with constrained resources. The first class is based on a RAC with quantum inputs and output known as the no-signalling quantum RAC (NS-QRAC) box (Grudka et al 2015 Phys. Rev. A 92 052312), where unbounded entanglement and constrained classical communication are allowed. We show that it can be seen as quantum teleportation with constrained classical communication and provide a lower quantum bound for the success probability. We consider two modifications to the NS-QRAC scenario: the first, where unbounded entanglement and constrained quantum communication is allowed and the second, where bounded entanglement and unconstrained classical communication is allowed. We find a monogamy relation for the transmission fidelities, which—in contrast to the usual communication schemes—involves multiple senders and a single receiver. We provide an upper bounds for the latter and a lower one for the former. The second class is based on a RAC with a quantum channel and shared entanglement (Tavakoli et al 2021 PRX Quantum 2 040357). We study the set of tasks where two inputs made of two digits of d-base are encoded over a qudit and a maximally entangled state. We show that such tasks can be seen as quantum dense-coding with constrained quantum communication and explicit protocols, which give lower quantum bounds for the tasks’ efficiency, in dimensions d = 2 , 3 , 4 . The employed encoding utilises Gray codes.

arXiv:2208.14422•New Journal of Physics•May 1, 2023•2 citations

Certified quantum advantage in entanglement-assisted prepare-measure random-access-code

Rajdeep Paul, Prabuddha Roy, A. K. Pan

Abstract We develop a family of semi-device-independent (SDI) entanglement-assisted prepare-measure (PM) communication games involving two parties, within the n → l random-access code (RAC) framework where the sender Alice holds a n -bit string and communicates l < n bits or qubits to the receiver Bob. In contrast to the standard quantum PMRAC, here the parties share a prior entanglement, and Alice applies quantum operations on her sub-system to encode her inputs and sends to Bob. We first consider the 4 → l entanglement-assisted PMRAC with l = 1 and 2 and derive the optimal quantum success probabilities using an elegant analytical technique. We demonstrate quantum supremacy over both classical RACs and conventional quantum PMRACs. Moreover, we exhibit that the optimal quantum advantage allows one to certify Alice’s unitary operations. We then derive an upper bound on the quantum success probabilities for 5 → l entanglement-assisted PMRAC with l = 1 , 2 and 3 . Further, we extend the demonstration of quantum advantage for n → n − 2 case where n is arbitrary.

New Journal of Physics•Sep 21, 2026•0 citations

Certified quantum supremacy in entanglement-assisted prepare-measure random-access-code

Rajdeep Paul, Prabuddha Roy, A. K. Pan

We develop a family of semi-device-independent (SDI) entanglement-assisted prepare-measure (PM) communication games involving two parties, within the $n\rightarrow l$ random-access code (RAC) framework where the sender Alice holds a n-bit string and communicates $l<n$ bits or qubits to the receiver Bob. In contrast to the standard quantum PMRAC, here the parties share a prior entanglement, and Alice applies quantum operations on her sub-system to encode her inputs and sends to Bob. We first consider the $4\rightarrow l$ entanglement-assisted PMRAC with $l=1$ and $2$ and derive the optimal quantum success probabilities using an elegant analytical technique. We demonstrate quantum supremacy over both classical RACs and conventional quantum PMRACs. Moreover, we exhibit that the optimal quantum advantage allows one to certify Alice's unitary operations. We then derive an upper bound on the quantum success probabilities for $5\rightarrow l$ entanglement-assisted PMRAC with $l=1,2$ and $3$. Further, we extend the demonstration of quantum advantage for $n\rightarrow n-2$ case where n is arbitrary.

quant-pharXiv:2607.10273•Jul 14, 2026•0 citations

Quantum Random Access Codes for Boolean Functions

João Fernando Doriguello, Ashley Montanaro

An n↦pm 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.

arXiv:2011.06535•Quantum•Mar 7, 2021•16 citations

Complementarity between entanglement-assisted and quantum distributed random access code

Alley Hameedi, Debashis Saha, Piotr Mironowicz +2 more

Collaborative communication tasks such as random access codes (RACs) employing quantum resources have manifested great potential in enhancing information processing capabilities beyond the classical limitations. The two quantum variants of RACs, namely, quantum random access code (QRAC) and the entanglement-assisted random access code (EARAC), have demonstrated equal prowess for a number of tasks. However, there do exist specific cases where one outperforms the other. In this article, we study a family of $3\ensuremath{\rightarrow}1$ distributed RACs [J. Bowles, N. Brunner, and M. Paw\l{}owski, Phys. Rev. A 92, 022351 (2015)] and present its general construction of both the QRAC and the EARAC. We demonstrate that, depending on the function of inputs that is sought, if QRAC achieves the maximal success probability then EARAC fails to do so and vice versa. Moreover, a tripartite Bell-type inequality associated with the EARAC variants reveals the genuine multipartite nonlocality exhibited by our protocol. We conclude with an experimental realization of the $3\ensuremath{\rightarrow}1$ distributed QRAC that achieves higher success probabilities than the maximum possible with EARACs for a number of tasks.

arXiv:1701.08713•Physical Review A•May 25, 2017•24 citations
Quantum resources and protocols are known to outperform their classical counterparts in a variety of communication and information processing tasks. Random access codes (RACs) are one such cryptographically significant family of bipartite communication tasks, wherein the sender encodes a data set (typically a string of input bits) onto a physical system of bounded dimension and transmits it to the receiver, who then attempts to guess a randomly chosen part of the sender's data set (typically one of the sender's input bits). In this work, we introduce a generalization of this task wherein the receiver, in addition to the individual input bits, aims to retrieve randomly chosen functions of the sender's input string. Specifically, we employ sets of mutually unbiased balanced functions, such that perfect knowledge of any one of the constituent functions yields no knowledge about the others. We investigate and bound the performance of (i) classical, (ii) quantum prepare and measure, and (iii) entanglement assisted classical communication (EACC) protocols for the resultant generalized RACs (GRACs). Finally, we detail the case of GRACs with three input bits and find maximal success probabilities for classical, quantum, and EACC protocols, along with the effect of noisy quantum channels on the performance of quantum protocols. Moreover, with the help of this case study, we reveal several characteristic properties of the GRACs which deviate from the standard RACs.
A random access code (RAC) is a communication task in which the sender encodes a random message into a shorter one to be decoded by the receiver so that a randomly chosen character of the original message is recovered with some probability. Both the message and the character to be recovered are assumed to be uniformly distributed. In this paper, we extend this protocol by allowing more general distributions of these inputs, which alters the encoding and decoding strategies optimizing the protocol performance, with either classical or quantum resources. We approach the problem of optimizing the performance of these biased RACs with both numerical and analytical tools. On the numerical front, we present algorithms that allow a numerical evaluation of the optimal performance over both classical and quantum strategies and provide a Python package designed to implement them, called RAC-tools. We then use this numerical tool to investigate single-parameter families of biased RACs in the ${n}^{2}\ensuremath{\mapsto}1$ and ${2}^{d}\ensuremath{\mapsto}1$ scenarios. For RACs in the ${n}^{2}\ensuremath{\mapsto}1$ scenario, we derive a general upper bound for the cases in which the inputs are not correlated, which coincides with the quantum value for n=2n=2n=2 and in some cases for n=3n=3n=3. Moreover, it is shown that attaining this upper bound self-tests pairs or triples of rank-1 projective measurements, respectively. An analogous upper bound is derived for the value of RACs in the ${2}^{d}\ensuremath{\mapsto}1$ scenario, which is shown to be always attainable using mutually unbiased measurements if the distribution of input strings is unbiased.
Abstract We consider two classes of quantum generalisations of random access code (RAC) and study the bounds for probabilities of success for such tasks. It provides a useful framework for the study of certain information processing tasks with constrained resources. The first class is based on a RAC with quantum inputs and output known as the no-signalling quantum RAC (NS-QRAC) box (Grudka et al 2015 Phys. Rev. A 92 052312), where unbounded entanglement and constrained classical communication are allowed. We show that it can be seen as quantum teleportation with constrained classical communication and provide a lower quantum bound for the success probability. We consider two modifications to the NS-QRAC scenario: the first, where unbounded entanglement and constrained quantum communication is allowed and the second, where bounded entanglement and unconstrained classical communication is allowed. We find a monogamy relation for the transmission fidelities, which—in contrast to the usual communication schemes—involves multiple senders and a single receiver. We provide an upper bounds for the latter and a lower one for the former. The second class is based on a RAC with a quantum channel and shared entanglement (Tavakoli et al 2021 PRX Quantum 2 040357). We study the set of tasks where two inputs made of two digits of d-base are encoded over a qudit and a maximally entangled state. We show that such tasks can be seen as quantum dense-coding with constrained quantum communication and explicit protocols, which give lower quantum bounds for the tasks’ efficiency, in dimensions d = 2 , 3 , 4 . The employed encoding utilises Gray codes.
Abstract We develop a family of semi-device-independent (SDI) entanglement-assisted prepare-measure (PM) communication games involving two parties, within the n → l random-access code (RAC) framework where the sender Alice holds a n -bit string and communicates l < n bits or qubits to the receiver Bob. In contrast to the standard quantum PMRAC, here the parties share a prior entanglement, and Alice applies quantum operations on her sub-system to encode her inputs and sends to Bob. We first consider the 4 → l entanglement-assisted PMRAC with l = 1 and 2 and derive the optimal quantum success probabilities using an elegant analytical technique. We demonstrate quantum supremacy over both classical RACs and conventional quantum PMRACs. Moreover, we exhibit that the optimal quantum advantage allows one to certify Alice’s unitary operations. We then derive an upper bound on the quantum success probabilities for 5 → l entanglement-assisted PMRAC with l = 1 , 2 and 3 . Further, we extend the demonstration of quantum advantage for n → n − 2 case where n is arbitrary.
We develop a family of semi-device-independent (SDI) entanglement-assisted prepare-measure (PM) communication games involving two parties, within the n→ln\rightarrow ln→l random-access code (RAC) framework where the sender Alice holds a n-bit string and communicates l<nl<nl<n bits or qubits to the receiver Bob. In contrast to the standard quantum PMRAC, here the parties share a prior entanglement, and Alice applies quantum operations on her sub-system to encode her inputs and sends to Bob. We first consider the 4→l4\rightarrow l4→l entanglement-assisted PMRAC with l=1l=1l=1 and 222 and derive the optimal quantum success probabilities using an elegant analytical technique. We demonstrate quantum supremacy over both classical RACs and conventional quantum PMRACs. Moreover, we exhibit that the optimal quantum advantage allows one to certify Alice's unitary operations. We then derive an upper bound on the quantum success probabilities for 5→l5\rightarrow l5→l entanglement-assisted PMRAC with l=1,2l=1,2l=1,2 and 333. Further, we extend the demonstration of quantum advantage for n→n−2n\rightarrow n-2n→n−2 case where n is arbitrary.
An n↦pm 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.
Collaborative communication tasks such as random access codes (RACs) employing quantum resources have manifested great potential in enhancing information processing capabilities beyond the classical limitations. The two quantum variants of RACs, namely, quantum random access code (QRAC) and the entanglement-assisted random access code (EARAC), have demonstrated equal prowess for a number of tasks. However, there do exist specific cases where one outperforms the other. In this article, we study a family of $3\ensuremath{\rightarrow}1$ distributed RACs [J. Bowles, N. Brunner, and M. Paw\l{}owski, Phys. Rev. A 92, 022351 (2015)] and present its general construction of both the QRAC and the EARAC. We demonstrate that, depending on the function of inputs that is sought, if QRAC achieves the maximal success probability then EARAC fails to do so and vice versa. Moreover, a tripartite Bell-type inequality associated with the EARAC variants reveals the genuine multipartite nonlocality exhibited by our protocol. We conclude with an experimental realization of the $3\ensuremath{\rightarrow}1$ distributed QRAC that achieves higher success probabilities than the maximum possible with EARACs for a number of tasks.