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:1703.01996

Strong supremacy of quantum systems as communication resource

Maria Quadeer, Manik Banik, Andris Ambainis, Ashutosh Rai

Published Mar 6, 2017• 4 citations
arXivHTMLPDF

Abstract

We investigate the task of $d$-level random access codes ($d$-RACs) and consider the possibility of encoding classical strings of $d$-level symbols (dits) into a quantum system of dimension $d'$ strictly less than $d$. We show that the average success probability of recovering one (randomly chosen) dit from the encoded string can be larger than that obtained in the best classical protocol for the task. Our result is intriguing as we know from Holevo's theorem (and more recently from Frenkel-Weiner's result [Commun. Math. Phys. 340, 563 (2015)]) that there exist communication scenarios wherein quantum resources prove to be of no advantage over classical resources. A distinguishing feature of our protocol is that it establishes a stronger quantum advantage in contrast to the existing quantum $d$-RACs where $d$-level quantum systems are shown to be advantageous over their classical $d$-level counterparts.

DOI
10.48550/arxiv.1703.01996

Related papers

Quantum advantages in (n,d) ↦ 1 random access codes

Andris Ambainis, Dmitry Kravchenko, Sk Sazim +2 more

Abstract A random access code (RAC), corresponding to a communication primitive with various applications in quantum information theory, is an instance of a preparation-and-measurement scenario. In this work, we consider (n, d)-RACs constituting an n-length string, constructed from a d size set of letters, and send an encoding of the string in a single d-level physical system and present their quantum advantages. We first characterize optimal classical RACs and prove that a known classical strategy, called majority-encoding-identity-decoding, is optimal. We then construct a quantum protocol by exploiting only two incompatible measurements (the minimal requirement) and show the advantages beyond the classical one. We also discuss the generality of our results and whether quantum advantages are valid for all types of ( n , d ) ↦ 1 RACs.

arXiv:1510.03045•New Journal of Physics•Dec 1, 2024•18 citations

Sufficient conditions for quantum advantage in random access code protocols with two-qubit states

Som Kanjilal, Chellasamy Jebarathinam, Tomasz Paterek +1 more

A random access code (RAC) is an important communication protocol to obtain information about a randomly specified substring of an $n$-bit string, while only having limited information about the $n$-bit string. Quantum RACs usually utilize either communication of quantum bits or a shared-in-advance quantum state used in conjunction with classical communication. Here we consider the latter version of the quantum protocols under the constraint of single-bit communication and with a shared arbitrary state of two qubits. Taking the worst-case success probability as the figure of merit, we demonstrate that any state with an invertible correlation matrix can be used to outperform the best classical RAC for $n=3$. We derive an additional condition sufficient to beat the best classical performance in the case of $n=2$. In particular, separable states turn out to be a useful resource behind the quantum advantage for $n=2,3$. For $n\ensuremath{\ge}4$, RACs assisted with a single copy of a quantum state do not outperform the classical RACs.

arXiv:1912.09900•Physical Review A•Jul 19, 2023•8 citations

Communication Supremacy of a Qubit in Holevo Frenkel Weiner Scenario

Partha Patra, Sumit Mukherjee, A. K. Pan

The prevailing wisdom asserts that in the Holevo Frenkel Weiner (HFW) framework of communication tasks, a qubit offers no advantage over a c bit unless additional quantum resources are supplied or the classical shared randomness (SR) is restricted. In contrast, we establish the supremacy of qubit communication in the HFW framework when additional quantum resources, such as entanglement or measurement incompatibility are not injected and SR is a free resource. We consider a prepare-measure scenario where the sender, Alice, prepares six states subject to a specific cryptographic constraint, and the receiver, Bob, performs a three-outcome measurement. Such a constraint on preparation impacts the power of qubit communication quite differently than that of c-bit communication, ultimately giving rise to the quantum advantage. We introduce a witness capable of distinguishing quantum strategies that lie beyond the set of possible classical strategies and demonstrate the optimal quantum advantage. {As an application, we demonstrate the generation of certified randomness without requiring any seed randomness, since Bob has no input.} We further analyse the robustness of the witness and show that the advantage persists in noisy situations, making it suitable for experimental realisation. Finally, we demonstrate that Bob's three outcome qubit positive operator valued-measure (POVMs) has a distinct capability of detecting coherence, which can be regarded as the non-classical feature responsible for showcasing the quantum advantage.

arXiv:2611.16940•Nov 12, 2026•0 citations

Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps

Ruho Kondo, Yuki Sato, Hiroshi Yano +3 more

A random access code (RAC) encodes an $L$-bit string into a $k$-bit message, $L>k$, so that any requested bit can be recovered with high probability; a quantum RAC (QRAC) uses $k$ qubits instead. We give a geometric characterization of optimal classical $(L,k)$-RACs under average and worst-case decoding criteria. The average criterion is reduced to choosing $2^k$ representatives in $\{0,1\}^L$, while the worst-case criterion is reduced to a minimax problem over $2^k$ points in $[0,1]^L$ with a distance-like objective. This framework proves optimality for several parameter families, with many optimal constructions arising from standard infinite families of binary linear codes. It also yields two explicit classical--quantum separations. First, for every $L>1$, we construct a $(L,1)$-QRAC whose average decoding success probability strictly exceeds the optimal classical value. Second, for the family $(2^k-1,k)$, we prove worst-case optimality of a classical RAC and construct a QRAC with strictly larger worst-case success probability. For the family $(L,L-1)$, the framework identifies a classical RAC that is average-case optimal and, under a stated conjecture, also worst-case optimal. The same viewpoint further recovers explicit $(L,L-1)$-QRACs attaining a previously conjectured upper-bound value.

quant-pharXiv:2604.21274•Apr 24, 2026•4 citations

Single Photon Sources and Single Quantum System enabled Communication

Muhammad Alley Hameedi

Quantum information is a highly interesting and fast emerging field that involves processing information encoded into quantum systems and their subsequent use in various information tasks. The use of quantum resources such as superposition and entanglement have shown to enhance information processing capabilities beyond classical means in a number of communication, information and computation tasks. In this thesis, we have used single photons to study the advantage of d-level quantum systems (qudits) for a communication task commonly known as random access codes (RACs). A successful experimental demonstration of quantum random access codes (QRACs) with four dimensions is realized to demonstrate that the higher dimensional QRACs not only outperform the classical RACs but also provide an advantage over their quantum bit (qubit) counterparts. QRACs are also studied in regards to two specific applications: certification of true randomness and for testing the non-classicality of quantum systems. A method for increased certification of generated randomness is realized for the former and a successful experimental demonstration of a test of non-classicality with arbitrarily low detection efficiency is provided for the latter. This is followed by an implementation of a QRAC in a one-path communication network consisting of preparation, transformation and measurement devices. We have shown that the distributed QRAC provides optimal success probabilities for a number of tasks. Moreover, a novel quantum protocol for the solution to the problem of dining cryptographers and anonymous veto voting is also presented. This single photon transmission based protocol provides an efficient solution, which is experimentally demonstrated for a 3-party description. Lastly, Nitrogen-Vacancy (NV) center in diamond is studied as a potential resource for single photon emission and two methods to enhance the photon collection efficiency are successfully explored. Due to this enhancement, single photons from an NV center may also be used in similar single quantum system based communication experiments.

•Jan 1, 2017•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•New Journal of Physics•Jul 14, 2026•0 citations
We investigate the task of ddd-level random access codes (ddd-RACs) and consider the possibility of encoding classical strings of ddd-level symbols (dits) into a quantum system of dimension d′d'd′ strictly less than ddd. We show that the average success probability of recovering one (randomly chosen) dit from the encoded string can be larger than that obtained in the best classical protocol for the task. Our result is intriguing as we know from Holevo's theorem (and more recently from Frenkel-Weiner's result [Commun. Math. Phys. 340, 563 (2015)]) that there exist communication scenarios wherein quantum resources prove to be of no advantage over classical resources. A distinguishing feature of our protocol is that it establishes a stronger quantum advantage in contrast to the existing quantum ddd-RACs where ddd-level quantum systems are shown to be advantageous over their classical ddd-level counterparts.
Abstract A random access code (RAC), corresponding to a communication primitive with various applications in quantum information theory, is an instance of a preparation-and-measurement scenario. In this work, we consider (n, d)-RACs constituting an n-length string, constructed from a d size set of letters, and send an encoding of the string in a single d-level physical system and present their quantum advantages. We first characterize optimal classical RACs and prove that a known classical strategy, called majority-encoding-identity-decoding, is optimal. We then construct a quantum protocol by exploiting only two incompatible measurements (the minimal requirement) and show the advantages beyond the classical one. We also discuss the generality of our results and whether quantum advantages are valid for all types of ( n , d ) ↦ 1 RACs.
A random access code (RAC) is an important communication protocol to obtain information about a randomly specified substring of an nnn-bit string, while only having limited information about the nnn-bit string. Quantum RACs usually utilize either communication of quantum bits or a shared-in-advance quantum state used in conjunction with classical communication. Here we consider the latter version of the quantum protocols under the constraint of single-bit communication and with a shared arbitrary state of two qubits. Taking the worst-case success probability as the figure of merit, we demonstrate that any state with an invertible correlation matrix can be used to outperform the best classical RAC for n=3n=3n=3. We derive an additional condition sufficient to beat the best classical performance in the case of n=2n=2n=2. In particular, separable states turn out to be a useful resource behind the quantum advantage for n=2,3n=2,3n=2,3. For $n\ensuremath{\ge}4$, RACs assisted with a single copy of a quantum state do not outperform the classical RACs.
The prevailing wisdom asserts that in the Holevo Frenkel Weiner (HFW) framework of communication tasks, a qubit offers no advantage over a c bit unless additional quantum resources are supplied or the classical shared randomness (SR) is restricted. In contrast, we establish the supremacy of qubit communication in the HFW framework when additional quantum resources, such as entanglement or measurement incompatibility are not injected and SR is a free resource. We consider a prepare-measure scenario where the sender, Alice, prepares six states subject to a specific cryptographic constraint, and the receiver, Bob, performs a three-outcome measurement. Such a constraint on preparation impacts the power of qubit communication quite differently than that of c-bit communication, ultimately giving rise to the quantum advantage. We introduce a witness capable of distinguishing quantum strategies that lie beyond the set of possible classical strategies and demonstrate the optimal quantum advantage. {As an application, we demonstrate the generation of certified randomness without requiring any seed randomness, since Bob has no input.} We further analyse the robustness of the witness and show that the advantage persists in noisy situations, making it suitable for experimental realisation. Finally, we demonstrate that Bob's three outcome qubit positive operator valued-measure (POVMs) has a distinct capability of detecting coherence, which can be regarded as the non-classical feature responsible for showcasing the quantum advantage.
A random access code (RAC) encodes an LLL-bit string into a kkk-bit message, L>kL>kL>k, so that any requested bit can be recovered with high probability; a quantum RAC (QRAC) uses kkk qubits instead. We give a geometric characterization of optimal classical (L,k)(L,k)(L,k)-RACs under average and worst-case decoding criteria. The average criterion is reduced to choosing 2k2^k2k representatives in {0,1}L\{0,1\}^L{0,1}L, while the worst-case criterion is reduced to a minimax problem over 2k2^k2k points in [0,1]L[0,1]^L[0,1]L with a distance-like objective. This framework proves optimality for several parameter families, with many optimal constructions arising from standard infinite families of binary linear codes. It also yields two explicit classical--quantum separations. First, for every L>1L>1L>1, we construct a (L,1)(L,1)(L,1)-QRAC whose average decoding success probability strictly exceeds the optimal classical value. Second, for the family (2k−1,k)(2^k-1,k)(2k−1,k), we prove worst-case optimality of a classical RAC and construct a QRAC with strictly larger worst-case success probability. For the family (L,L−1)(L,L-1)(L,L−1), the framework identifies a classical RAC that is average-case optimal and, under a stated conjecture, also worst-case optimal. The same viewpoint further recovers explicit (L,L−1)(L,L-1)(L,L−1)-QRACs attaining a previously conjectured upper-bound value.
Quantum information is a highly interesting and fast emerging field that involves processing information encoded into quantum systems and their subsequent use in various information tasks. The use of quantum resources such as superposition and entanglement have shown to enhance information processing capabilities beyond classical means in a number of communication, information and computation tasks. In this thesis, we have used single photons to study the advantage of d-level quantum systems (qudits) for a communication task commonly known as random access codes (RACs). A successful experimental demonstration of quantum random access codes (QRACs) with four dimensions is realized to demonstrate that the higher dimensional QRACs not only outperform the classical RACs but also provide an advantage over their quantum bit (qubit) counterparts. QRACs are also studied in regards to two specific applications: certification of true randomness and for testing the non-classicality of quantum systems. A method for increased certification of generated randomness is realized for the former and a successful experimental demonstration of a test of non-classicality with arbitrarily low detection efficiency is provided for the latter. This is followed by an implementation of a QRAC in a one-path communication network consisting of preparation, transformation and measurement devices. We have shown that the distributed QRAC provides optimal success probabilities for a number of tasks. Moreover, a novel quantum protocol for the solution to the problem of dining cryptographers and anonymous veto voting is also presented. This single photon transmission based protocol provides an efficient solution, which is experimentally demonstrated for a 3-party description. Lastly, Nitrogen-Vacancy (NV) center in diamond is studied as a potential resource for single photon emission and two methods to enhance the photon collection efficiency are successfully explored. Due to this enhancement, single photons from an NV center may also be used in similar single quantum system based communication experiments.
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.