(4,1)-Quantum Random Access Coding Does Not Exist

Abstract

An (n,1,p)-Quantum Random Access (QRA) coding, introduced by Ambainis, Nayak, Ta-shma and Vazirani in ACM Symp. on Theory of Computing 1999, is the following communication system: The sender which has n-bit information encodes his/her information into one qubit, which is sent to the receiver. The receiver can recover any one bit of the original n bits correctly with probability at least p, through a certain decoding process based on positive operator-valued measures. Actually, Ambainis et al. shows the existence of a (2,1,0.85)-QRA coding and also proves the impossibility of its classical counterpart. Chuang immediately extends it to a (3,1,0.79)-QRA coding and whether or not a (4,1,p)-QRA coding such that p > 1/2 exists has been open since then. This paper gives a negative answer to this open question.

8pages, 3figures

References in corpus (5)

• Quantum Copying: Beyond the No-Cloning Theorem
• Spin flips and quantum information for anti-parallel spins
• Quantum Network Coding
• Optimal lower bounds for quantum automata and random access codes
• On the Power of Quantum Memory

Cited by in corpus (35)

• Preparation contextuality powers parity-oblivious multiplexing
• Quantum Network Coding
• Semi-device independent random number expansion without entanglement
• Quantum superposition of the order of parties as a communication resource
• Semi-device independent random number expansion protocol with n to 1 quantum random access codes
• Entanglement assisted random access codes
• Semidefinite programming relaxations for quantum correlations
• Quantum random access codes and incompatibility of measurements
• Experimental Demonstration of Sequential Quantum Random Access Codes
• Informationally restricted quantum correlations
• Measurement incompatibility and quantum advantage in communication
• Quantum advantage for probabilistic one-time programs
• Improved Classical and Quantum Random Access Codes
• Unbounded-error One-way Classical and Quantum Communication Complexity
• Quantum Network Coding for General Graphs
• One-out-of-$m$ spacetime-constrained oblivious transfer
• Quantum Random Access Codes for Boolean Functions
• Widening the sharpness modulation region of an entanglement-assisted sequential quantum random access code: Theory, experiment, and application
• General Method for Classicality Certification in the Prepare and Measure Scenario
• Ability of unbounded pairs of observers to achieve quantum advantage in random access codes with a single pair of qubits
• Quantum discord in quantum random access codes and its connection with dimension witness
• Adaptive advantage in entanglement-assisted communications
• 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
• The geometry of Bloch space in the context of quantum random access codes
• Quantum Relaxation for Solving Multiple Knapsack Problems
• Trainable Discrete Feature Embeddings for Variational Quantum Classifier
• Robustness of contextuality under different types of noise as quantifiers for parity-oblivious multiplexing tasks
• Sufficient conditions for quantum advantage in random access code protocols with two-qubit states
• The Learnability of Unknown Quantum Measurements
• Role of nonclassical temporal correlation in powering quantum random access codes
• Semi-device-independent self-testing of unitary operations
• $n$-fold unbiased bases: an extension of the MUB condition
• Quantum advantage in a unified scenario and secure detection of resources