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:1403.1295 · Physical Review A

Nonsignaling quantum random access-code boxes

Andrzej Grudka, Michał Horodecki, Ryszard Horodecki, Antoni Wójcik

Published Nov 10, 2015• 9 citations
arXivHTMLPDF

Abstract

A well-known cryptographic primitive is the so-called random access code. Namely, Alice is to send to Bob one of two bits, so that Bob has the choice of which bit he wants to learn about. However, at any time, Alice should not learn Bob's choice, and Bob should learn only the bit of his choice. The task is impossible to accomplish by means of either classical or quantum communication. On the other hand, a concept of correlations stronger than quantum ones, exhibited by the so-called Popescu-Rohrlich box, was introduced and widely studied. In particular, it is known that the Popescu-Rohrlich box enables simulation of the random access code with the support of one bit of communication. Here, we propose a quantum analog of this phenomenon. Namely, we define an analog of a random access code, where instead of classical bits, one encodes qubits. We provide a quantum nonsignaling box that if supported with two classical bits, allows one to simulate a quantum version of a random access code. We point out that two bits are necessary. We also show that a quantum random access code cannot be fully quantum: when Bob inputs the superposition of two choices, the output will be in a mixed state rather than in a superposition of required states.

DOI
10.1103/physreva.92.052312

Related papers

When Are Popescu-Rohrlich Boxes and Random Access Codes Equivalent?

Andrzej Grudka, Karol Horodecki, Michał Horodecki +2 more

We study a problem of interconvertibility of two supraquantum resources: one is the so-called Popescu-Rohrlich (PR) box, which violates Clauser-Horne-Shimony-Holt inequality up to the maximal algebraic bound, and the second is the so-called random access code (RAC). The latter is a functionality that enables Bob (receiver) to choose one of two bits of Alice. It is known that a PR box supplemented with one bit of communication can be used to simulate a RAC. We ask the converse question: to what extent can a RAC can simulate a PR box? To this end, we introduce a "racbox": a box such that when it is supplemented with one bit of communication it offers a RAC. As said, a PR box can simulate a racbox. The question we raise is whether any racbox can simulate a PR box. We show that a nonsignaling racbox, indeed, can simulate a PR box; hence, these two resources are equivalent. We also provide an example of a signaling racbox that cannot simulate a PR box. We give a resource inequality between racboxes and PR boxes and show that it is saturated.

arXiv:1307.7904•Physical Review Letters•Sep 2, 2014•29 citations

Quantum Random Access Codes with Shared Randomness

Andris Ambainis, Debbie Leung, Laura Mancinska +1 more

We consider a communication method, where the sender encodes n classical bits into 1 qubit and sends it to the receiver who performs a certain measurement depending on which of the initial bits must be recovered. This procedure is called (n,1,p) quantum random access code (QRAC) where p > 1/2 is its success probability. It is known that (2,1,0.85) and (3,1,0.79) QRACs (with no classical counterparts) exist and that (4,1,p) QRAC with p > 1/2 is not possible. We extend this model with shared randomness (SR) that is accessible to both parties. Then (n,1,p) QRAC with SR and p > 1/2 exists for any n > 0. We give an upper bound on its success probability (the known (2,1,0.85) and (3,1,0.79) QRACs match this upper bound). We discuss some particular constructions for several small values of n. We also study the classical counterpart of this model where n bits are encoded into 1 bit instead of 1 qubit and SR is used. We give an optimal construction for such codes and find their success probability exactly--it is less than in the quantum case. Interactive 3D quantum random access codes are available on-line at http://home.lanet.lv/~sd20008/racs .

arXiv:0810.2937•Oct 16, 2008•48 citations

Optimal Bounds for Parity-Oblivious Random Access Codes with Applications

André Chailloux, Iordanis Kerenidis, Srijita Kundu +1 more

Random Access Codes is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an n-bit string x, and wishes to encode x into a quantum state rho_x, such that Bob, when receiving the state rho_x, can choose any bit i in [n] and recover the input bit x_i with high probability. Here we study a variant called parity-oblivious random acres codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input, apart form the single bits x_i. We provide the optimal quantum parity-oblivious random access codes and show that they are asymptotically better than the optimal classical ones. For this, we relate such encodings to a non-local game and provide tight bounds for the success probability of the non-local game via semi-definite programming. Our results provide a large non-contextuality inequality violation and resolve the main open question in [Spekkens et al., Phys. Review Letters, 2009].

Leibniz international proceedings in informatics•Jan 1, 2014•0 citations

Entanglement-assisted random access codes

Marcin Pawłowski, Marek Żukowski

An $(n,m,p)$ random access code (RAC) makes it possible to encode $n$ bits in an $m$-bit message in such a way that a receiver of the message can guess any of the original $n$ bits with probability $p$ greater than $\frac{1}{2}$. In quantum RACs (QRACs), one transmits $n$ qubits. The full set of primitive entanglement-assisted random access codes (EARACs) is introduced, in which parties are allowed to share a two-qubit singlet. It is shown that via a concatenation of these, one can build for any $n$ an $(n,1,p)$ EARAC. QRACs for $n>3$ exist only if parties also share classical randomness. We show that EARACs outperform the best of known QRACs not only in the success probabilities but also in the amount of communication needed in the preparatory stage of the protocol. Upper bounds on the performance of EARACs are given and shown to limit also QRACs.

arXiv:0906.0524•Physical Review A•Apr 27, 2010•97 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

Finite Nonsignalling Resources Suffice to Simulate Entangled Qubits

Ziao Tang, Xin Wang, Ge Bai

A longstanding question in Bell nonlocality is whether finite-alphabet nonsignalling resources can reproduce the continuum of measurement correlations of partially entangled qubits. Here we resolve this problem by showing that every fixed pure two-qubit state admits an exact simulation of all local projective-measurement statistics using shared randomness and finitely many Popescu-Rohrlich (PR) boxes, without communication or postselection. The boxes operate in parallel, with a worst-case bound independent of the measurement settings: at most $128\cot^4θ$ calls for the Schmidt state $\cosθ|00\rangle+\sinθ|11\rangle$, $0<θ<π/4$. The key is an exact finite-selection method that reduces input-dependent continuous sampling to a choice from a fixed-length shared random list, implemented through a finite PR-box network. The construction extends to arbitrary mixed two-qubit states and local binary-outcome POVMs. This reveals a fundamental separation between the continuity of quantum measurement correlations and the alphabet size of the resources needed to simulate them, shedding light on the resource-theoretic structure of Bell nonlocality.

quant-pharXiv:2610.32319•Oct 26, 2026•0 citations
A well-known cryptographic primitive is the so-called random access code. Namely, Alice is to send to Bob one of two bits, so that Bob has the choice of which bit he wants to learn about. However, at any time, Alice should not learn Bob's choice, and Bob should learn only the bit of his choice. The task is impossible to accomplish by means of either classical or quantum communication. On the other hand, a concept of correlations stronger than quantum ones, exhibited by the so-called Popescu-Rohrlich box, was introduced and widely studied. In particular, it is known that the Popescu-Rohrlich box enables simulation of the random access code with the support of one bit of communication. Here, we propose a quantum analog of this phenomenon. Namely, we define an analog of a random access code, where instead of classical bits, one encodes qubits. We provide a quantum nonsignaling box that if supported with two classical bits, allows one to simulate a quantum version of a random access code. We point out that two bits are necessary. We also show that a quantum random access code cannot be fully quantum: when Bob inputs the superposition of two choices, the output will be in a mixed state rather than in a superposition of required states.
We study a problem of interconvertibility of two supraquantum resources: one is the so-called Popescu-Rohrlich (PR) box, which violates Clauser-Horne-Shimony-Holt inequality up to the maximal algebraic bound, and the second is the so-called random access code (RAC). The latter is a functionality that enables Bob (receiver) to choose one of two bits of Alice. It is known that a PR box supplemented with one bit of communication can be used to simulate a RAC. We ask the converse question: to what extent can a RAC can simulate a PR box? To this end, we introduce a "racbox": a box such that when it is supplemented with one bit of communication it offers a RAC. As said, a PR box can simulate a racbox. The question we raise is whether any racbox can simulate a PR box. We show that a nonsignaling racbox, indeed, can simulate a PR box; hence, these two resources are equivalent. We also provide an example of a signaling racbox that cannot simulate a PR box. We give a resource inequality between racboxes and PR boxes and show that it is saturated.
We consider a communication method, where the sender encodes n classical bits into 1 qubit and sends it to the receiver who performs a certain measurement depending on which of the initial bits must be recovered. This procedure is called (n,1,p) quantum random access code (QRAC) where p > 1/2 is its success probability. It is known that (2,1,0.85) and (3,1,0.79) QRACs (with no classical counterparts) exist and that (4,1,p) QRAC with p > 1/2 is not possible. We extend this model with shared randomness (SR) that is accessible to both parties. Then (n,1,p) QRAC with SR and p > 1/2 exists for any n > 0. We give an upper bound on its success probability (the known (2,1,0.85) and (3,1,0.79) QRACs match this upper bound). We discuss some particular constructions for several small values of n. We also study the classical counterpart of this model where n bits are encoded into 1 bit instead of 1 qubit and SR is used. We give an optimal construction for such codes and find their success probability exactly--it is less than in the quantum case. Interactive 3D quantum random access codes are available on-line at http://home.lanet.lv/~sd20008/racs .
Random Access Codes is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an n-bit string x, and wishes to encode x into a quantum state rho_x, such that Bob, when receiving the state rho_x, can choose any bit i in [n] and recover the input bit x_i with high probability. Here we study a variant called parity-oblivious random acres codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input, apart form the single bits x_i. We provide the optimal quantum parity-oblivious random access codes and show that they are asymptotically better than the optimal classical ones. For this, we relate such encodings to a non-local game and provide tight bounds for the success probability of the non-local game via semi-definite programming. Our results provide a large non-contextuality inequality violation and resolve the main open question in [Spekkens et al., Phys. Review Letters, 2009].
An (n,m,p)(n,m,p)(n,m,p) random access code (RAC) makes it possible to encode nnn bits in an mmm-bit message in such a way that a receiver of the message can guess any of the original nnn bits with probability ppp greater than 12\frac{1}{2}21​. In quantum RACs (QRACs), one transmits nnn qubits. The full set of primitive entanglement-assisted random access codes (EARACs) is introduced, in which parties are allowed to share a two-qubit singlet. It is shown that via a concatenation of these, one can build for any nnn an (n,1,p)(n,1,p)(n,1,p) EARAC. QRACs for n>3n>3n>3 exist only if parties also share classical randomness. We show that EARACs outperform the best of known QRACs not only in the success probabilities but also in the amount of communication needed in the preparatory stage of the protocol. Upper bounds on the performance of EARACs are given and shown to limit also QRACs.
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.
A longstanding question in Bell nonlocality is whether finite-alphabet nonsignalling resources can reproduce the continuum of measurement correlations of partially entangled qubits. Here we resolve this problem by showing that every fixed pure two-qubit state admits an exact simulation of all local projective-measurement statistics using shared randomness and finitely many Popescu-Rohrlich (PR) boxes, without communication or postselection. The boxes operate in parallel, with a worst-case bound independent of the measurement settings: at most 128cot⁡4θ128\cot^4θ128cot4θ calls for the Schmidt state cos⁡θ∣00⟩+sin⁡θ∣11⟩\cosθ|00\rangle+\sinθ|11\ranglecosθ∣00⟩+sinθ∣11⟩, 0<θ<π/40<θ<π/40<θ<π/4. The key is an exact finite-selection method that reduces input-dependent continuous sampling to a choice from a fixed-length shared random list, implemented through a finite PR-box network. The construction extends to arbitrary mixed two-qubit states and local binary-outcome POVMs. This reveals a fundamental separation between the continuity of quantum measurement correlations and the alphabet size of the resources needed to simulate them, shedding light on the resource-theoretic structure of Bell nonlocality.