Getting almost all the bits from a quantum random access code

Lin, Han-Hsuan; de Wolf, Ronald

doi:10.48550/arXiv.2506.01903

A quantum random access code (QRAC) is a map $x\mapsto\rho_x$ that encodes $n$-bit strings $x$ into $m$-qubit quantum states $\rho_x$, in a way that allows us to recover any one bit of $x$ with success probability $\geq p$. The measurement on $\rho_x$ that is used to recover, say, $x_1$ 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$.

Additional Metadata
Persistent URL	doi.org/10.48550/arXiv.2506.01903
Rights	creativecommons.org/licenses/by/4.0/
Organisation	Algorithms and Complexity
Citation APA APA Style APA-ALL Style AAA Style Cell Style Chicago Style Harvard Style IEEE Style MLA Style Nature Style Vancouver Style American-Institute-of-Physics Style Council-of-Science-Editors Style BibTex Format Endnote Format RIS Format CSL Format DOIs only Format	Lin, H.-H.& de Wolf, R. (2025). Getting almost all the bits from a quantum random access code.https://doi.org/10.48550/arXiv.2506.01903