Quantum random access coding (QRAC) is one of the basic tools in quantum computing. It uses a quantum state for encoding the sender's bit string so that the receiver can recover any single bit of the bit string with high probability. This article surveys recent developments of QRAC, with some concrete examples of QRAC using one quantum bit, and its applications, focusing on communication complexity and locally decodable codes.
Quantum random access coding (QRAC) is one of the basic tools in quantum computing. It uses a quantum state for encoding the sender's bit string so that the receiver can recover any single bit of the bit string with high probability. This article surveys recent developments of QRAC, with some concrete examples of QRAC using one quantum bit, and its applications, focusing on communication complexity and locally decodable codes.
A quantum random access code (QRAC) is a map x↦ρx that encodes n-bit strings x into m-qubit quantum states ρx, in a way that allows us to recover any one bit of x with success probability ≥p. The measurement on ρx that is used to recover, say, x1 may destroy all the information about the other bits; this is in fact what happens in the well-known QRAC that encodes n=2 bits into m=1 qubits. Does this generalize to large n, i.e., could there exist QRACs that are so "obfuscated" that one cannot get much more than one bit out of them? Here we show that this is not the case: for every QRAC there exists a measurement that (with high probability) recovers the full n-bit string x up to small Hamming distance, even for the worst-case x.
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 .
Quantum random access codes (QRACs) enable multiple classical bits to be encoded into fewer qubits, while allowing only a selected bit to be retrieved with probability greater than the corresponding classical limit. Here, we use 2→1 and 3→1 QRACs for simultaneous transmission of multiple binary images through a single quantum data stream. At the receiver, the measurement choice determines which encoded image is reconstructed, while the remaining image information is disturbed by the measurement process. The inherent correct-bit probabilities of these QRACs are approximately 85.4% and 78.9%, respectively. By applying median and morphological filtering to the decoded binary images, we improve the reconstruction accuracy in an image-dependent manner, reaching 99.17% for 2→1 QRACs and 98.36% for 3→1 QRACs. We also analyze the effect of depolarizing noise on reconstruction quality using accuracy, peak signal-to-noise ratio, and structural similarity index measure. These results demonstrate a selective-access framework for QRAC-based image transmission with potential applications in controlled image/video transmission.
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 2k representatives in {0,1}L, while the worst-case criterion is reduced to a minimax problem over 2k 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 (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), 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.
An ( n ,1, p )-quantum random access (QRA) coding, introduced by Ambainis et al (1999 ACM Symp. Theory of Computing p 376), 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. Moreover, we generalize its negative answer for one-qubit encoding to the case of multiple-qubit encoding
A ${n}^{d}\stackrel{p}{\ensuremath{\rightarrow}}1$ quantum random access code (QRAC) is a communication task where Alice encodes n classical bits into quantum states of dimension d and transmits them to Bob, who performs appropriate measurements to recover the required bit with probability p. In the presence of a noisy environment, the performance of a QRAC is degraded, losing the advantage over classical strategies. We propose a practical technique that enables noise tolerance in such scenarios, recovering the quantum advantage in retrieving the required bit. We perform a photonic implementation of a ${2}^{2}\stackrel{\text{p}}{\ensuremath{\rightarrow}}1$ QRAC using polarization-encoded qubits under an amplitude-damping channel, where simple operations allow for noise robustness showing the revival of the quantum advantage when the noisy channel degrades the performance of the QRAC. This revival can be observed by violating a suitable dimension witness, which is closely related to the average success probability of the QRAC. This technique can be extended to other applications in the so-called prepare-and-measure scenario, enhancing the semi-device-independent protocol implementations.