Getting almost all the bits from a quantum random access code

Han-Hsuan Lin, Ronald de Wolf · 2025

Read Getting almost all the bits from a quantum random access code by Han-Hsuan Lin, Ronald de Wolf (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01903.txt.

Introduction

Squeezing a long bit string into a few quantum bits sounds like a hiding trick, and a 2025 paper by Han-Hsuan Lin and Ronald de Wolf shows the trick cannot hide much. A quantum random access code stores an n-bit string in a short quantum state so that any single bit can be read back with decent odds.

Reading one bit usually wrecks the rest, and a famous small code gets just one of two bits out. The authors prove this does not scale: for every such code, some single measurement recovers nearly the whole string at once, up to a small number of wrong bits. The result holds even for the hardest strings, and it limits how obfuscated these codes can ever be.

Catalog record

CREATORHan-Hsuan Lin, Ronald de Wolf
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01903

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Getting almost all the bits from a quantum random access code Han-Hsuan Lin, Ronald de Wolf Abstract A quantum random access code (QRAC) is a map x ↦ ρ x x\mapsto\rho_{x} that encodes n n -bit strings x x into m m -qubit quantum states ρ x \rho_{x} , in a way that allows us to recover any one bit of x x with success probability ≥ p \geq p . The measurement on ρ x \rho_{x} that is used to recover, say, x 1 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 n=2 bits into m = 1 m=1 qubits. Does this generalize to large n 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 n -bit string x x up to small Hamming distance, even for the worst-case x x . 1 Introduction 1.1 Quantum Random Access Codes Quantum states of m qubits are described by 2^{m} complex amplitudes, and it is tempting to try to use this exponential “space” to encode a lot of classical information in a quantum state. Holevo’s theorem [ Hol73 ] says that in general we cannot use this exponential space: if we encode some classical random variable X in an m -qubit quantum state \rho_{X} (via a map x\mapsto\rho_{x} ), and then do a measurement on \rho_{X} to produce a classical random variable Y , then the mutual information between X and Y is at most m . So we cannot cram more than m bits of information into m qubits. Quantum random access codes, first introduced in [ ANTV99 ] , address a more subtle situation where we demand less from the decoding: here x\in\{0,1\}^{n} and we only want to be able to recover the bit x_{i} of x from \rho_{x} with success probability p>1/2 , for any i\in[n] of our choice. Note that this is different from recovering all bits of x , since the measurement that recovers x_{1} can change the m -qubit state, making it harder (or even impossible) to recover other bits of x . More formally: Definition 1 An (n,m,p) -quantum random access code (QRAC) is a map x\mapsto\rho_{x} from the set of n -bit strings to the set of m -qubit mixed states, such that for each i\in[n] there exists a 2-outcome POVM \{M_{0},M_{1}\} such that for each x\in\{0,1\}^{n} and b\in\{0,1\} we have \mbox{\rm Tr}(M_{b}\rho_{x})\geq p if x_{i}=b . For example, we can encode n=2 classical bits into m=1 qubits by mapping (for b\in\{0,1\} ) the 2-bit string x=0b to the qubit \cos(\pi/8)|0\rangle+(-1)^{b}\sin(\pi/8)|1\rangle , and mapping x=1b to (-1)^{b}\sin(\pi/8)|0\rangle+\cos(\pi/8)|1\rangle . See Figure 1 for illustration. A measurement in the computational basis recovers the first bit x_{1} with success probability \cos(\pi/8)^{2}\approx 0.85 , and a measurement in the Hadamard basis recovers x_{2} with the same success probability. Figure 1: The 4 pure states of the standard 2-to-1 QRAC We know almost exactly how many qubits are required for an (n,m,p) -QRAC: Ambainis et al. [ ANTV99 ] showed that m\leq(1-H(p))n+O(\log n) qubits are sufficient , even just using classical random variables (i.e., diagonal density matrices \rho_{x} ), and Nayak [ Nay99 ] proved that m\geq(1-H(p))n qubits are necessary , improving an \Omega(n/\log n) lower bound from [ ANTV99 ] . 1 1 1 Here H(p)=-p\log_{2}(p)-(1-p)\log_{2}(1-p) denotes the binary entropy. The information-theoretic intuition behind Nayak’s m\geq(1-H(p))n lower bound is quite clear: \rho_{x} allows us to predict x_{i} with success probability \geq p , which reduces the entropy of x_{i} from 1 bit to at most H(p) bits, so gives at least 1-H(p) bits of information; this is true for all n bits of x simultaneously. The two papers [ ANTV99 ] and [ Nay99 ] were later combined in the journal version [ ANTV02 ] . QRACs have a number of applications in quantum information, such as lower bounding the size of 1-way quantum finite automata [ ANTV99 , Nay99 , ANTV02 ] , 1-way quantum communication complexity [ BW01 , Kla00 , GKRW09 , BRW08 ] , and the length of classical locally decodable error-correcting codes [ KW04 , BRW08 ] . They have also been used to show upper bounds, for instance that n -qubit density matrices can be learned (in a weak sense) from O(n) measurement results [ Aar07 ] . They have been generalized to the setting of two parties (one holding x , the other holding i ) who share randomness [ ALMO08 ] , and to computing more general functions of up to k of the bits of x [ BRW08 , DM21 ] rather than just recovering one bit x_{i} . We refer to [ DM21 , page 1–2] for many more references to applications of QRACs and even experimental implementations. 1.2 Our results: getting most of the bits of x from \rho_{x} In a quantum random access code, the measurement needed to recover x_{1} may significantly change the state, reducing the information we have about the other bits. This is what happens for instance in the above 2-to-1 example (Figure 1 ): if we measure in the computational basis to recover x_{1} and get the correct answer, then the state will have collapsed to |x_{1}\rangle , and all information about x_{2} is lost; and if we got the wrong answer, then the post-measurement state |1-x_{1}\rangle also has no information about x_{2} . Similarly, doing the Hadamard-basis measurement to recover x_{2} will destroy all information about x_{1} . Can this “obfuscating” behavior be generalized? Maybe there are quantum random access codes that are so obfuscated that they allow to recover any one x_{i} of our choice, but not many more bits? Such QRACs would be undesirable if one cares about extracting a lot of information about the whole x (rather than just one bit x_{i} ), but could be very desirable if one cares about hiding information for cryptographic purposes. Our main result in this paper is a negative answer to this question: we show that every QRAC admits a measurement that recovers most of the bits of x correctly from one copy of \rho_{x} , in the sense of being able to obtain an n -bit string y that has small Hamming distance with the encoded x . We prove this first in an average-case setting (Section 3 ), where we have some probability distribution \{P_{x}\} on x\in\{0,1\}^{n} , and then (in Section 4 ) use the minimax theorem of game theory to extend the result to a worst-case setting, i.e., we obtain a measurement that works for every x . The measurement that proves our result in the average-case setting is simple and well-known: it is the so-called Pretty Good Measurement (PGM) for identifying x from \rho_{x} . The PGM measures one copy of \rho_{x} and produces a measurement outcome y\in\{0,1\}^{n} . The PGM cannot actually be very good at the task of identifying the whole n -bit x exactly: another bound due

Read the complete text