Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

Getting almost all the bits from a quantum random access code

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A single quantum measurement can recover nearly every bit of any quantum random access code.

desk verdict A clean, correct result: no QRAC is Hamming-obfuscated; the constants inherit a standard external PGM bound and a few minor repairs are needed. read the letter →

arxiv 2506.01903 v1 pith:CUT3BE63 submitted 2025-06-02 quant-ph cs.IR

Han-Hsuan Lin (National Tsing Hua University , Taiwan) , Ronald de Wolf (QuSoft , CWI , University of Amsterdam) This is my paper
classification quant-phcs.IR MSC 81P4581P5094A17 PACS 03.67.-a03.67.Hk
keywords quantumrandomaccesscodesprettygoodmeasurementstatediscriminationHammingdistanceminimaxtheoreminformationtheorymessagecompression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether a quantum random access code (QRAC), which packs n classical bits into m qubits so that any chosen bit can be recovered with probability at least p, can be obfuscated so that reading one bit destroys all the others. It proves this cannot happen: from one copy of the encoded state, a single measurement returns a string whose expected Hamming distance from the original bit string is at most 2p(1-p)n, even for the worst-case input string. The proof first establishes an average-case guarantee for the Pretty Good Measurement, then lifts it to a worst-case guarantee through the minimax theorem of game theory. The result matters because it shows QRACs leak almost all their information in one shot, settles a natural question about their hiding power, and yields both a new qubit lower bound and a conversion from quantum to classical random access codes.

What carries the argument

The central object is the Pretty Good Measurement (PGM), defined for an ensemble {(P_x, rho_x)} by Q_y = P_y $rho^{{-1/2}}$ rho_y $rho^{{-1/2}}$, a simple explicit POVM that is nearly as good as the optimal measurement for identifying which state was prepared. The paper shows that the coordinate marginals of this PGM are exactly the PGMs for the two-state ensembles that decide single bits, which is what transfers the QRAC's per-bit success p into per-bit success $p^{2}$+(1-p)^2. The decisive quantitative input is the improved PGM bound for binary ensembles, p_PGM >= $p_max^{2}$ + (1-p_max)^2, and the worst-case extension is carried by the minimax theorem applied to the linear function f(P,Q) = E_{x~P, y~Tr(Q_y rho_x)}[d_H(x,y)] over distributions P and POVMs Q.

What would settle it

A direct numerical search for small parameters, for example n=4, m=2 with fixed p, could compute the best POVM's worst-case expected Hamming distance over all x and compare it with 2p(1-p)n; any instance exceeding that value would refute Theorem 3. A more targeted check is to test Eq. (1) on a concrete binary ensemble: if the PGM's success probability on two equiprobable non-orthogonal states fell below $p_max^{2}$ + (1-p_max)^2, the stated constants in Theorems 2 through 5 would not follow.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3: for every (n,m,p)-QRAC mapping x to rho_x, there exists a 2^n-outcome POVM such that for every x, the expected Hamming distance between x and the measurement outcome y is at most 2p(1-p)n. No matter how the encoding is designed, some single measurement extracts almost the whole string simultaneously. The engine is per-coordinate: for each bit i, the marginals of the Pretty Good Measurement form the Pretty Good Measurement for a two-state ensemble, and the QRAC guarantee implies the optimal success probability for that bit is at least p; the improved PGM bound then gives per-bit success at least $p^{2}$+(1-p)^2, so each coordinate is wrong with probability at most 2p(1-p). Linearity of expectation bounds the total Hamming distance, and the minimax theorem converts this average-case statement into a worst-case one. The same estimates yield a qubit lower bound m >= (1-H(2p(1-p)))n - log(n+1) and, via max-information message compression, a classical random access code with error 2p(1-p)+eta and message length m+O(log n + log(1/eta)).

Load-bearing premise

The entire quantitative chain rests on the borrowed, unproved-in-this-paper fact that the Pretty Good Measurement identifies one of two states with success probability at least $p_max^{2}$ + (1-p_max)^2; if that bound were false or weaker, the constants 2p(1-p) in the main theorems would change, though the qualitative claim that most bits are recoverable might survive.

Editorial extensions

If this is right

  • For any QRAC with success probability p, a single measurement on one copy of the encoded state returns a string differing from the true n-bit input in at most 2p(1-p)n positions on average, and this holds for the worst-case input.
  • When p is close to 1, the recovered string is almost exactly x with high probability, so QRACs cannot serve as strong single-copy obfuscation.
  • The per-coordinate estimate yields the qubit lower bound m >= (1-H(2p(1-p)))n - log(n+1), which is weaker than the known optimal bound and quadratically worse when p is near 1/2.
  • Every (n,m,p)-QRAC can be converted into a classical random access code with success probability at least 1-2p(1-p)-eta and message length m+O(log n + log(1/eta)), without shared randomness.
  • The coordinates of the PGM outcome are individually correct with probability at least p^2+(1-p)^2 under any input distribution, which is the engine behind all the stated results.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the constant 2p(1-p) is inherited from the binary PGM bound, any future improvement of that bound would immediately tighten all the paper's constants, while the qualitative claim that most bits are recoverable would survive unchanged.
  • The result suggests a general no-obfuscation principle: any single-copy quantum encoding that allows bitwise recovery with an advantage over random guessing must also allow simultaneous recovery of almost the whole string, so QRAC-based hiding is weak at best.
  • For p = 1/2 + beta, the expected error fraction is about 1/2 - 2*beta^2, so even a barely nontrivial QRAC leaks roughly half the bits in Hamming distance; cryptographic settings should not rely on QRACs alone for hiding.
  • The proof technique of taking coordinate marginals of the PGM and then applying minimax may transfer to other state-discrimination problems where one wants worst-case guarantees from average-case measurements, such as identifying a function of the encoded message.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proves a structural result about quantum random access codes (QRACs): for every (n,m,p)-QRAC x -> ρ_x, there exists a single 2^n-outcome POVM such that, for every encoded string x, the expected Hamming distance between x and the measurement outcome y is at most 2p(1-p)n (Theorem 3). The proof uses the pretty good measurement (PGM) for the full ensemble, shows that its restriction to the i-th bit is exactly the PGM for the coarse-grained two-state ensemble, applies a known lower bound on the binary PGM success probability (Eq. (1)), and then uses Sion's minimax theorem to pass from average-case to worst-case. The paper also derives a new lower bound m ≥ (1-H(2p(1-p)))n - log(n+1) on the number of qubits of a QRAC (Theorem 4), and a conversion of any QRAC into a classical random access code with message length m + O(log n + log(1/η)) and success probability 1-2p(1-p)-η (Theorem 5).

Significance. If the results hold, they resolve a natural question left open by the well-known 2-to-1 QRAC example, where the measurements for the two bits destroy each other's information. The main theorem shows that no QRAC can be 'Hamming-obfuscated': one copy of the state suffices to recover a string close to x in Hamming distance, even in the worst case. The proof is elegant, combining the pretty good measurement with a linearity-of-expectation argument and the minimax theorem, and the quantitative bound is explicit and essentially tight. The derived lower bound and the QRAC-to-RAC conversion, while quantitatively weaker than Nayak's bound, are new and may be useful in other contexts. The paper is clearly written and self-contained except for a few external results. The main theorem is likely to be of interest to the quantum information and communication complexity communities.

major comments (2)
  1. [Section 2.1, Eq. (1); used in Theorem 2] The constant 2p(1-p) appearing in Theorems 2, 3, 4, and 5 is entirely inherited from the quoted bound p_PGM ≥ p_max^2 + (1-p_max)^2 for binary ensembles. The paper cites [Ren17] but does not state the precise hypotheses (in particular, whether arbitrary mixed states and arbitrary priors are allowed) nor provide a proof. Since the coarse-grained ensemble in the proof of Theorem 2 is an arbitrary binary ensemble of mixed states, the authors should either state the lemma in full generality with a self-contained proof (or a precise citation to the exact theorem in [Ren17]) or derive the bound directly. Without this, the numerical constants in the main theorems are not fully justified.
  2. [Section 6, Theorem 5 proof, derandomization step] After applying the compression protocol of Theorem 1, the scheme still uses shared randomness beyond (r,d): the iid copies of Z used for rejection sampling. The subsequent probabilistic method only randomizes over s=(r,d), so the claim 'We do not need shared randomness between encoder and decoder anymore' is not justified as written. The proof should be revised to treat s as the full shared randomness (r,d,Z), or to derandomize the compression step separately. The claimed O(log n + log(1/η)) overhead remains intact under the former fix, since the Chernoff-union-bound argument does not depend on the alphabet size of the shared randomness.
minor comments (4)
  1. [Abstract and Section 1.2] The abstract says 'with high probability recovers the full n-bit string x up to small Hamming distance', but the quantitative statement of Theorem 3 is an expectation bound. Please consider stating the resulting high-probability version explicitly (e.g., via Markov's inequality) or rephrasing to avoid overclaiming for p close to 1/2.
  2. [Section 2.1] The sentence introducing the improved bound says 'In fact the lower bound can be improved to [Ren17, Eq. (12)] p_PGM ≥ p_max^2 + (1-p_max)^2/(|X|-1)'. It would be helpful to also mention that p_PGM ≤ p_max always, and to give the precise theorem or equation number in [Ren17].
  3. [Section 4] There is a minor typo in 'of of Eq. (5)' in the paragraph after Eq. (5).
  4. [Section 6] The phrase 'The RAC has bad encoded length' might be clearer as 'The RAC has poor encoding length' or 'large message length'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems derive from external PGM bounds, minimax, and prior compression results.

full rationale

The paper's derivation chain is anchored to external benchmarks and does not reduce to its own inputs. The central quantitative engine, Eq. (1), is the Renes lower bound p_PGM >= p_max^2 + (1-p_max)^2 for binary ensembles, quoted from [Ren17]. This is a property of the Pretty Good Measurement, not of QRACs, and it is not derived in the paper. Theorem 2 uses only the QRAC definition to note that pmax for the induced binary ensemble is at least p, combines this with Eq. (1), and then applies linearity of expectation. The constant 2p(1-p) is algebraically equal to 1 - (p^2 + (1-p)^2), not a fitted parameter or a renamed input. Theorem 3 obtains the worst-case statement by applying Sion's minimax theorem to the linear expected-Hamming-distance function; this is a standard external result and is not equivalent to the theorem's conclusion. Theorem 4 is an entropy-based consequence of Theorem 3 and standard entropy inequalities, and Theorem 5 uses the external channel-compression theorem of [JRS03, HJMR07]. The self-citations to [BJL23], [BRW08], and [KW04] appear only as background or as references for similar techniques; none is load-bearing for the main claim. The paper does not import a uniqueness theorem from the authors' prior work, does not smuggle an ansatz via citation, and does not rename a known empirical pattern. The only substantive concern is that Eq. (1) is quoted without proof and without a precise statement of its hypotheses, but that is a correctness or verification risk, not circularity. Even substituting the older Barnum-Knill bound would preserve the qualitative theorem, confirming that the result is not forced by the external lemma alone.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the QRAC definition plus standard external theorems: PGM near-optimality, Sion's minimax theorem, max-information compression, entropy inequalities, and the Chernoff/union bound. There are no fitted free parameters and no invented entities; p is an input assumption. The paper's own contributions are the coarse-graining observation, the minimax conversion, and the conversion protocol.

assumptions (6)
  • standard math PGM near-optimality: p_PGM >= p_max^2 for any ensemble; for binary ensembles p_PGM >= p_max^2 + (1 - p_max)^2 (Eq. (1)).
    Quoted from Barnum-Knill 2002, Montanaro 2007, and Renes 2017 (Section 2.1). This is the quantitative engine of Theorem 2; every later constant (2p(1-p), Theorem 4's lower bound, Theorem 5's success probability) inherits this external bound.
  • standard math Sion's minimax theorem: for compact convex P, Q and f linear in each argument, max_P min_Q f = min_Q max_P f.
    Used in Section 4 to upgrade the average-case Theorem 2 into the worst-case Theorem 3. The paper verifies compactness of the POVM set and bilinearity of expected Hamming distance.
  • standard math Max-information channel compression (Theorem 1, from Jain-Radhakrishnan-Sen 2003 and Harsha et al. 2007): channel E is simulable with message length C_max(E) + O(log log(1/eta)) and trace-distance error eta.
    Used in Section 6 to compress the n-bit measurement outcome to m + O(log log(1/eta)) bits. Quoted with a rejection-sampling proof sketch, not reproved from first principles.
  • standard math Standard entropy facts: data processing inequality, chain rule H(X|Y,D) = H(X,D|Y) - H(D|Y), concavity of binary entropy, and C(n,d) <= 2^{H(d/n)n}.
    Used in Theorem 4's proof of m >= (1 - H(2p(1-p)))n - log_2(n+1). Conditioning on the exact distance D = d justifies the C(n,d) count.
  • standard math Chernoff bound and union bound, in the style of Newman's theorem on removing shared randomness.
    Used in Section 6 to fix a seed set S of size O(n/eta^2) so that per-bit error degrades by at most eta/2 for all 2^n n pairs (x, i).
  • domain assumption QRAC definition: for each index i there is a 2-outcome POVM with Tr(M_b rho_x) >= p whenever x_i = b, for every x simultaneously.
    Input hypothesis of all four theorems. It implies the coarse-grained 2-state ensemble has p_max >= p, which feeds Eq. (1) in Theorem 2. p is an assumed property of the object studied, not a fitted value.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Getting almost all the bits from a quantum random access code." pith.science (2026). https://pith.science/paper/CUT3BE63

@misc{pith2026250601903,
  author       = {Pith},
  title        = {Pith review of: Getting almost all the bits from a quantum random access code},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CUT3BE63}},
  note         = {Machine review of arXiv:2506.01903}
}
abstract

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$.

Figures

Figures reproduced from arXiv: 2506.01903 by the authors.

Figure 1
Figure 1. The 4 pure states of the standard 2-to-1 QRAC [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal Average Success Probabilities of Binary $(n,n-1)$ and $(n,n-2)$ Quantum Random Access Codes via a Proof of the Corresponding Conjectured Bound

    quant-ph 2026-07 accept novelty 6.5 of 10

    The optimal average success probability of binary (n,n-1) and (n,n-2) QRACs equals exactly 1/2 + 1/2 sqrt(m/n).

  2. Classical codes violate the conjectured square-root bound for quantum random access codes

    quant-ph 2026-07 accept novelty 6.0 of 10

    Classical random access codes with private randomness violate the conjectured (1+sqrt(m/n))/2 quantum random access code bound when embedded as diagonal quantum codes, for a full range of compression rates.

Reference graph

Works this paper leans on

25 extracted references · 21 canonical work pages · cited by 2 Pith papers

  1. [1]

    Aaronson

    S. Aaronson. The learnability of quantum states. Proceedings of the Royal Society of London , A463(2088), 2007. quant-ph/0608142

    arXiv 2007

  2. [2]

    Ambainis, D

    A. Ambainis, D. Leung, L. Mancinska, and M. Ozols. Quantum random access codes with shared randomness. arXiv:0810.2937, 2008

    arXiv 2008

  3. [4]

    Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata

    A. Ambainis, A. Nayak, A. Ta-Shma , and U. V. Vazirani. Dense quantum coding and quantum finite automata. Journal of the ACM , 49(4):496--511, 2002. Earlier version in STOC'99. quant-ph/9804043

    work page Pith review arXiv 2002

  4. [5]

    N. G. Boddu, R. Jain, and H. Lin. On relating one-way classical and quantum communication complexities. Quantum , 7:1010, 2023. arXiv:2107.11623

    work page Pith review arXiv 2023

  5. [6]

    Barnum and E

    H. Barnum and E. Knill. Reversing quantum dynamics with near-optimal quantum and classical fidelity. Journal of Mathematical Physics , 43:2097--2106, 2002. quant-ph/0004088

    arXiv 2002

  6. [7]

    A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs

    A. Ben-Aroya , O. Regev, and R. de Wolf. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDC s. In Proceedings of 49th IEEE FOCS , pages 477--486, 2008. quant-ph/0705.3806

    work page Pith review arXiv 2008

  7. [8]

    Buhrman and R

    H. Buhrman and R. de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of 16th IEEE Conference on Computational Complexity , pages 120--130, 2001. cs.CC/9910010

    work page arXiv 2001

  8. [9]

    N. Datta. Min- and max-relative entropies and a new entanglement monotone. IEEE Transactions on Information Theory , 55(6):2816--2826, 2009

    work page 2009

Show all 25 references
  1. [10]

    Doriguello and A

    J. Doriguello and A. Montanaro. Quantum random access codes for B oolean functions. Quantum , 5:402, 2021. arXiv:2011.06535

    2021 arXiv

  2. [11]

    Gavinsky, J

    D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf. Bounded-error quantum state identification and exponential separations in communication complexity. SIAM Journal on Computing , 39(1):1--24, 2009. Special issue on STOC'06. quant-ph/0511013

    2009 arXiv

  3. [12]

    Harsha, R

    P. Harsha, R. Jain, D. McAllester, and J. Radhakrishnan. The communication complexity of correlation. In Proceedings of the 22nd Annual IEEE Conference on Computational Complexity , pages 10--23, 2007

    2007

  4. [13]

    Hausladen, R

    P. Hausladen, R. Jozsa, B. Schumacher, M. Westmoreland, and W. Wootters. Classical information capacity of a quantum channel. Physical Review A , 54:1869--1876, 1996

    1996

  5. [14]

    A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii , 9(3):3--11, 1973. English translation in Problems of Information Transmission , 9:177--183, 1973

    1973

  6. [15]

    Hausladen and W

    P. Hausladen and W. Wootters. A ``pretty good'' measurement for distinguishing quantum states. Journal of Modern Optics , 41:2385, 1994

    1994

  7. [16]

    R. Jain, J. Radhakrishnan, and P. Sen. A direct sum theorem in communication complexity via message compression. In Proceedings of the 30th international conference on Automata, languages and programming , pages 300--315. Springer-Verlag, 2003

    2003

  8. [17]

    R. Jain, J. Radhakrishnan, and P. Sen. Prior entanglement, message compression and privacy in quantum communication. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity , pages 285--296, 2005

    2005

  9. [18]

    H. Klauck. On quantum and probabilistic communication: Las Vegas and one-way protocols. In Proceedings of 32nd ACM STOC , pages 644--651, 2000

    2000

  10. [19]

    Kushilevitz and N

    E. Kushilevitz and N. Nisan. Communication Complexity . Cambridge University Press, 1997

    1997

  11. [20]

    R. T. K \"o nig and B. M. Terhal. The bounded storage model in the presence of a quantum adversary. IEEE Transactions on Information Theory , 54(2):749--762, 2008. quant-ph/0608101

    2008 arXiv

  12. [21]

    Kerenidis and R

    I. Kerenidis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. Journal of Computer and System Sciences , 69(3):395--420, 2004. Earlier version in STOC'03. quant-ph/0208062

    2004 arXiv

  13. [22]

    Montanaro

    A. Montanaro. On the distinguishability of random quantum states. Communications in Mathematical Physics , 273(3):619--636, 2007. quant-ph/0607011

    2007 arXiv

  14. [23]

    A. Nayak. Optimal lower bounds for quantum automata and random access codes. In Proceedings of 40th IEEE FOCS , pages 369--376, 1999. quant-ph/9904093

    1999 arXiv

  15. [24]

    I. Newman. Private vs. common random bits in communication complexity. Information Processing Letters , 39(2):67--71, 1991

    1991

  16. [25]

    J. M. Renes. Better bounds on optimal measurement and entanglement recovery, with applications to uncertainty and monogamy relations. Physical Review A , 96(4):042328, 2017. quant-ph/1707.01114

    2017 arXiv

  17. [26]

    M. Sion. On general minimax theorems. Pacific Journal of Mathematics , 8(1):171--176, 1958

    1958

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.