Quantum Advantages in (n,d)->1 Random Access Codes

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, proving that the well-known classical strategy known as majority-encoding-identity-decoding is indeed 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.

The title changed, and the paper is thoroughly revised and extended with new results (close to the published version)

References in corpus (31)

• Quantum Cryptography
• Quantum cryptography: Public key distribution and coin tossing
• The Security of Practical Quantum Key Distribution
• Secure Quantum Key Distribution
• Information Causality as a Physical Principle
• Non-locality and Communication Complexity
• Quantum algorithms for algebraic problems
• Quantum state discrimination and its applications
• Semi-device-independent security of one-way quantum key distribution
• Quantum Random Access Codes using Single $d$-level Systems
• Semi-device independent random number expansion without entanglement
• Quantum superposition of the order of parties as a communication resource
• Self-testing mutually unbiased bases in the prepare-and-measure scenario
• Structure of minimum-error quantum state discrimination
• (4,1)-Quantum Random Access Coding Does Not Exist
• Classical information storage in an $n$-level quantum system
• Quantum contextuality provides communication complexity advantage
• Entanglement-assisted quantum communication with simple measurements
• Quantum random access codes and incompatibility of measurements
• No-signaling Principle Can Determine Optimal Quantum State Discrimination
• A feasible quantum communication complexity protocol
• When Are Popescu-Rohrlich Boxes and Random Access Codes Equivalent?
• Measurement incompatibility and quantum advantage in communication
• Mutually Unbiased Balanced Functions & Generalized Random Access Codes
• Quantum Random Access Codes for Boolean Functions
• Operational foundations of complementarity and uncertainty relations
• Device independent witness of arbitrary dimensional quantum systems employing binary outcome measurements
• Role of fine-grained uncertainty in determining the limit of preparation contextuality
• Random access test as an identifier of nonclassicality
• The geometry of Bloch space in the context of quantum random access codes
• Role of nonclassical temporal correlation in powering quantum random access codes

Cited by in corpus (6)

• Self-testing mutually unbiased bases in the prepare-and-measure scenario
• Quantum stochastic communication via high-dimensional entanglement
• Simple and general bounds on quantum random access codes
• Robust certification of quantum instruments through a sequential communication game
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• Random Exclusion Codes: Quantum Advantages of Single-Shot Communication