Pith. sign in

REVIEW 2 minor 45 references

The optimal decoding probability of quantum random access codes is fixed by the largest eigenvalue of sums of noncommuting decoding measurements, yielding bounds stricter than Nayak's and optimal constructions via mutually unbiased projecto

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-27 09:16 UTC pith:MAAG4RHT

load-bearing objection The spectral reformulation turns QRAC decoding into an exact eigenvalue average, which simplifies Nayak's bound and tightens it for finite sizes while supporting explicit constructions that hit the conjectured optimum.

arxiv 2606.12700 v1 pith:MAAG4RHT submitted 2026-06-10 quant-ph math-phmath.MP

Measurement Geometry for Quantum Random Access Codes: Beyond Nayak Bound and Toward Optimality

Seiseki Akibue , Rudy Raymond , Suguru Tamaki , Kosei Teramoto This is my paper
classification quant-ph math-phmath.MP
keywords quantum random access codesNayak boundmutually unbiased measurementsprojector-valued measurementsspectral boundsnoncommuting operatorsquantum encoding
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Quantum random access codes encode N classical bits into M qubits so that any one chosen bit can be recovered with high probability. The paper recasts the search for the highest possible success probability as a spectral optimization problem over sets of noncommuting measurements. This reformulation supplies both an elementary proof of the Nayak bound and a family of refined upper bounds that are strictly stronger for every finite N and M. Equality holds precisely when the measurements form mutually unbiased projector-valued measurements, a structure that the authors use to build explicit codes attaining the conjectured optimum for the (M+2, M) family.

Core claim

Expressing the QRAC success probability through the spectra of the decoding measurements reduces the design problem to a noncommuting-operator eigenvalue question. The equality cases of the resulting bounds define mutually unbiased projector-valued measurements, any such set assisted by one ancillary qubit achieves the optimal scaling of success probability with N, and an explicit MUPVM construction realizes the conjectured bound for the (M+2, M) family.

What carries the argument

Mutually unbiased projector-valued measurements (MUPVMs), sets of projector-valued measurements whose projectors from distinct sets have constant overlap, which saturate the spectral bounds and enable optimal N-scaling when one ancilla is added.

Load-bearing premise

The highest decoding probability equals the largest eigenvalue obtained from the chosen set of decoding measurements.

What would settle it

A numerical or experimental QRAC for M=2 qubits and N=4 bits whose average success probability exceeds the refined spectral upper bound would falsify the claim.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Upper bounds on decoding probability that are strictly tighter than the Nayak bound hold for every finite N and M.
  • Any MUPVM assisted by one ancillary qubit yields a QRAC whose success probability scales optimally with N.
  • An explicit MUPVM construction realizes the conjectured optimal bound for the entire (M+2, M) family of QRACs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same spectral reduction may extend to other multi-recovery quantum coding problems whose optimality conditions involve overlapping measurements.
  • MUPVMs supply a geometric criterion that could guide numerical searches for optimal measurements in small-qubit regimes.
  • The two-qubit optimality result suggests that MUPVM structures might characterize all optimal finite-size QRACs.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 2 minor

Summary. The paper reformulates the optimal decoding probability for quantum random access codes (QRACs) as the average of the maximum eigenvalues of operators B_x constructed from the decoding measurements. It provides an elementary proof of the Nayak bound by simplifying the Chernoff-bound argument, refines the argument to obtain upper bounds improving over Nayak in the entire finite-size regime, introduces mutually unbiased projector-valued measurements (MUPVMs) justified by the equality cases, shows that any MUPVM assisted by one ancillary qubit yields a QRAC with optimal N-scaling decoding probability, and proposes a new MUPVM-based construction for the (M+2,M)-QRAC family attaining the conjectured bound.

Significance. If the central reduction and derivations hold, the work is significant for supplying a lossless spectral reformulation of QRAC design that yields both a simplified proof of the standard Nayak bound and strictly tighter finite-size bounds, together with a new geometric framework (MUPVMs) that produces optimal constructions and ancillary-assisted optimality results. The exact mapping from classical strings to principal eigenvectors of the B_x operators and the resulting equality-case analysis are notable strengths that could influence subsequent work on quantum communication bounds.

minor comments (2)
  1. The definition and properties of MUPVMs would benefit from an explicit low-dimensional example (e.g., two-qubit case) immediately after the formal definition to illustrate how they generalize mutually unbiased bases.
  2. A short table or plot comparing the refined bounds against the Nayak bound for representative small values of N and M would make the finite-size improvement concrete and easier to verify.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, the clear summary of its contributions, and the recommendation for minor revision. No specific major comments were provided in the report, so we have no point-by-point responses to address. We will incorporate any minor editorial or clarification changes suggested during the revision process.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper's core chain begins with an exact reformulation of the QRAC success probability as the average of λ_max(B_x) where B_x = (1/N) Σ_i M^i_{x_i} for fixed decoding measurements M. This is lossless because each classical x maps to an independent density operator ρ_x chosen as the principal eigenvector of B_x. From this spectral problem the authors derive an elementary simplification of the Chernoff argument to recover the Nayak bound, then refine the same argument for finite-size improvements. Equality cases of the refined bounds are used only to motivate the definition of MUPVMs; the subsequent claims (two-qubit optimality forces MUPVMs, ancillary-assisted MUPVMs achieve optimal N-scaling, and the new (M+2,M) construction) are direct consequences of the spectral formulation and the MUPVM definition, without any fitted parameters, self-referential definitions, or load-bearing self-citations. All steps remain within the paper's own equations and external mathematical facts (Chernoff bound, spectral theorem). No reduction of a claimed prediction or bound to its own inputs occurs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work rests on the standard Chernoff bound technique and on the assumption that the spectral formulation fully captures optimality; MUPVMs are introduced as a derived concept rather than an independent postulate.

axioms (1)
  • standard math Chernoff bound supplies valid upper bound on decoding probability
    Invoked to prove Nayak bound and its refinements
invented entities (1)
  • mutually unbiased projector-valued measurements (MUPVMs) no independent evidence
    purpose: Generalization of mutually unbiased bases whose equality conditions define optimal decoding measurements
    Defined from the equality cases of the new bounds; no independent existence proof supplied

pith-pipeline@v0.9.1-grok · 5762 in / 1289 out tokens · 25915 ms · 2026-06-27T09:16:06.950764+00:00 · methodology

0 comments
read the original abstract

Quantum random access codes (QRACs) ask how well N classical bits can be encoded into M qubits while allowing any single bit to be recovered. Although the Nayak bound remains the standard general upper bound on the decoding probability, numerical evidence suggests a stronger upper bound in the small-qubit regime. In this work, we formulate the optimal decoding probability in terms of decoding measurements, reformulating QRAC design as a spectral problem for noncommuting measurements. Using this formulation, we give an elementary proof of the Nayak bound by simplifying the Chernoff-bound argument. Moreover, we refine the argument to obtain upper bounds that improve over Nayak's bound in the entire finite-size regime. The equality conditions of our bounds justify defining mutually unbiased projector-valued measurements (MUPVMs), a generalization of mutually unbiased bases. We show that decoding measurement of any two-qubit QRAC attaining the conjectured bound must form MUPVMs. We also show that any MUPVM, assisted by one ancillary qubit, yields a QRAC with optimal N-scaling decoding probability. Finally, we propose a new MUPVM-based construction for the (M+2,M)-QRAC family attaining the conjectured bound.

Figures

Figures reproduced from arXiv: 2606.12700 by Kosei Teramoto, Rudy Raymond, Seiseki Akibue, Suguru Tamaki.

Figure 1
Figure 1. Figure 1: Comparison of upper bounds on the decoding probability [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of upper bounds on the average-case decoding probability [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Quantum circuit for the decoding measurement in Proposition 4. The first qubit [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 1 canonical work pages

  1. [1]

    Aguilar, Jakub J

    Edgar A. Aguilar, Jakub J. Borkała, Piotr Mironowicz, and Marcin Pawłowski. Con- nections between mutually unbiased bases and quantum random access codes. Phys. Rev. Lett., 121:050501, Jul 2018

    2018

  2. [2]

    Ahlswede and A

    R. Ahlswede and A. Winter. Strong converse for identification via quantum channels. IEEE Transactions on Information Theory, 48(3):569–579, 2002

    2002

  3. [3]

    Harrow, and Matthew B

    Andris Ambainis, Aram W. Harrow, and Matthew B. Hastings. Random tensor theory: Extending random matrix theory to mixtures of random product states. Communications in Mathematical Physics, 310(1):25–74, 2012

    2012

  4. [4]

    Quantum random access codes with shared randomness, 2009

    Andris Ambainis, Debbie Leung, Laura Mančinska, and Maris Ozols. Quantum random access codes with shared randomness, 2009

    2009

  5. [5]

    Dense quan- tum coding and a lower bound for 1-way quantum automata

    Andris Ambainis, Ashwin Nayak, Ammon Ta-Shma, and Umesh Vazirani. Dense quan- tum coding and a lower bound for 1-way quantum automata. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99, page 376– 383, New York, NY, USA, 1999. Association for Computing Machinery

    1999

  6. [6]

    Resolving matrix spencer conjecture up to poly-logarithmic rank

    Nikhil Bansal, Haotian Jiang, and Raghu Meka. Resolving matrix spencer conjecture up to poly-logarithmic rank. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1814–1819, New York, NY, USA, 2023. Association for Computing Machinery. 27

    2023

  7. [7]

    Fernando G. S. L. Brandão and Aram W. Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342(1):47–80, 2016

    2016

  8. [8]

    Quantum random access codes and incompatibility of measurements

    Carmeli, Claudio, Heinosaari, Teiko, and Toigo, Alessandro. Quantum random access codes and incompatibility of measurements. EPL, 130(5):50001, 2020

    2020

  9. [9]

    A new framework for matrix discrep- ancy: partial coloring bounds via mirror descent

    Daniel Dadush, Haotian Jiang, and Victor Reis. A new framework for matrix discrep- ancy: partial coloring bounds via mirror descent. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 649–658, New York, NY, USA, 2022. Association for Computing Machinery

    2022

  10. [10]

    A general bound for the dimension of quantum behaviours in the prepare-and-measure scenario

    Julio I de Vicente. A general bound for the dimension of quantum behaviours in the prepare-and-measure scenario. Journal of Physics A: Mathematical and Theoretical, 52(9):095304, feb 2019

    2019

  11. [11]

    Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Benoît Vermersch, and Peter Zoller

    Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Benoît Vermersch, and Peter Zoller. The randomized measurement toolbox. Nature Reviews Physics, 5(1):9–24, 2023

    2023

  12. [12]

    Self-testing mutually unbiased bases in the prepare-and-measure scenario

    Máté Farkas and Je￿ drzej Kaniewski. Self-testing mutually unbiased bases in the prepare-and-measure scenario. Phys. Rev. A, 99:032316, Mar 2019

    2019

  13. [13]

    Mutually unbiased measurements, hadamard matrices, and superdense coding

    Mate Farkas, Jedrzej Kaniewski, and Ashwin Nayak. Mutually unbiased measurements, hadamard matrices, and superdense coding. IEEE Transactions on Information Theory, 69(6):3814–3824, 2023

    2023

  14. [14]

    Simple and general bounds on quantum random access codes

    Máté Farkas, Nikolai Miklin, and Armin Tavakoli. Simple and general bounds on quantum random access codes. Quantum, 9:1643, February 2025

    2025

  15. [15]

    Glick, Takashi Imamichi, Toshinari Itoko, Richard J

    Bryce Fuller, Charles Hadfield, Jennifer R. Glick, Takashi Imamichi, Toshinari Itoko, Richard J. Thompson, Yang Jiao, Marna M. Kagele, Adriana W. Blom-Schieber, Rudy Raymond, and Antonio Mezzacapo. Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quantum Engineering, 5:1–15, 2024

    2024

  16. [16]

    Ernesto F. Galvao. Foundations of quantum theory and quantum information appli- cations, 2002

    2002

  17. [17]

    Quantum network coding

    Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Shigeru Yamashita. Quantum network coding. In Wolfgang Thomas and Pascal Weil, editors, STACS 2007, pages 610–621, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg

    2007

  18. [18]

    Black holes as mirrors: quantum information in random subsystems

    Patrick Hayden and John Preskill. Black holes as mirrors: quantum information in random subsystems. Journal of High Energy Physics, 2007(09):120, sep 2007

    2007

  19. [19]

    Hopkins, Prasad Raghavendra, and Abhishek Shetty

    Samuel B. Hopkins, Prasad Raghavendra, and Abhishek Shetty. Matrix discrepancy from quantum communication. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 637–648, New York, NY, USA, 2022. Association for Computing Machinery. 28

    2022

  20. [20]

    Predicting many properties of a quantum system from very few measurements

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020

    2020

  21. [21]

    Certifying almost all quan- tum states with few single-qubit measurements

    Hsin-Yuan Huang, John Preskill, and Mehdi Soleimanifar. Certifying almost all quan- tum states with few single-qubit measurements. Nature Physics, 21(11):1834–1841, 2025

    2025

  22. [22]

    Constructions of quantum ran- dom access codes

    Takashi Imamichi and Rudy Raymond. Constructions of quantum ran- dom access codes. In Asian Quantum Information Symposium (AQIS), vol- ume 66, 2018. Retrieved from https://research.ibm.com/publications/ constructions-of-quantum-random-access-codes

    2018

  23. [23]

    Geometrical description of quantal state determination

    I D Ivonovic. Geometrical description of quantal state determination. Journal of Physics A: Mathematical and General, 14(12):3241, dec 1981

    1981

  24. [24]

    Unbounded-error one-way classical and quantum communication complexity

    Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Shigeru Yamashita. Unbounded-error one-way classical and quantum communication complexity. In Lars Arge, Christian Cachin, Tomasz Jurdziński, and Andrzej Tarlecki, editors, Automata, Languages and Programming, pages 110–121, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg

    2007

  25. [25]

    Mutually unbiased measurements in finite dimensions

    Amir Kalev and Gilad Gour. Mutually unbiased measurements in finite dimensions. New Journal of Physics, 16(5):053038, may 2014

    2014

  26. [26]

    The complexity of the local hamiltonian problem

    Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. SIAM Journal on Computing, 35(5):1070–1097, 2006

    2006

  27. [27]

    Recursive Quantum Relaxation for Combinatorial Optimization Problems

    Ruho Kondo, Yuki Sato, Rudy Raymond, and Naoki Yamamoto. Recursive Quantum Relaxation for Combinatorial Optimization Problems. Quantum, 9:1594, January 2025

    2025

  28. [28]

    Many-body quantum chaos: Analytic connection to random matrix theory

    Pavel Kos, Marko Ljubotina, and Toma ž Prosen. Many-body quantum chaos: Analytic connection to random matrix theory. Phys. Rev. X, 8:021062, Jun 2018

    2018

  29. [29]

    Laura Mančinska and Sigurd A. L. Storgaard. The geometry of bloch space in the context of quantum random access codes. Quantum Information Processing, 21(4):143, 2022

    2022

  30. [30]

    Mehta and M

    M.L. Mehta and M. Gaudin. On the density of eigenvalues of a random matrix. Nuclear Physics, 18:420–427, 1960

    1960

  31. [31]

    On the distinguishability of random quantum states

    Ashley Montanaro. On the distinguishability of random quantum states. Communications in Mathematical Physics, 273(3):619–636, 2007

    2007

  32. [32]

    Optimal lower bounds for quantum automata and random access codes

    Ashwin Nayak. Optimal lower bounds for quantum automata and random access codes. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, page 369, USA, 1999. IEEE Computer Society. 29

    1999

  33. [33]

    Semi-device-independent security of one-way quantum key distribution

    Marcin Pawłowski and Nicolas Brunner. Semi-device-independent security of one-way quantum key distribution. Phys. Rev. A, 84:010302(R), Jul 2011

    2011

  34. [34]

    Information causality as a physical principle

    Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter, and Marek Żukowski. Information causality as a physical principle. Nature, 461(7267):1101–1104, 2009

    2009

  35. [35]

    Gapless spin-fluid ground state in a random quantum heisenberg magnet

    Subir Sachdev and Jinwu Ye. Gapless spin-fluid ground state in a random quantum heisenberg magnet. Phys. Rev. Lett., 70:3339–3342, May 1993

    1993

  36. [36]

    Spekkens, D

    Robert W. Spekkens, D. H. Buzacott, A. J. Keehn, Ben Toner, and G. J. Pryde. Preparation contextuality powers parity-oblivious multiplexing. Phys. Rev. Lett., 102:010401, Jan 2009

    2009

  37. [37]

    Analytical construction of (n, n − 1) quantum random access codes saturating the conjectured bound, 2026

    Takayuki Suzuki. Analytical construction of (n, n − 1) quantum random access codes saturating the conjectured bound, 2026

    2026

  38. [38]

    Quantum random access codes using single d-level systems

    Armin Tavakoli, Alley Hameedi, Breno Marques, and Mohamed Bourennane. Quantum random access codes using single d-level systems. Phys. Rev. Lett., 114:170502, Apr 2015

    2015

  39. [39]

    Self-testing nonprojective quantum measurements in prepare-and- measure experiments

    Armin Tavakoli, Massimiliano Smania, Tamás Vértesi, Nicolas Brunner, and Mo- hamed Bourennane. Self-testing nonprojective quantum measurements in prepare-and- measure experiments. Science Advances, 6(16):eaaw6664, 2020

    2020

  40. [40]

    The role of entanglement in quantum-relaxation based optimization algorithms

    Kosei Teramoto, Rudy Raymond, and Hiroshi Imai. The role of entanglement in quantum-relaxation based optimization algorithms. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 01, pages 543– 553, 2023

    2023

  41. [41]

    Quantum- Relaxation Based Optimization Algorithms: Theoretical Extensions

    Kosei Teramoto, Rudy Raymond, Eyuri Wakakuwa, and Hiroshi Imai. Quantum- Relaxation Based Optimization Algorithms: Theoretical Extensions. arXiv preprint arXiv:2302.09481, 2023

    work page arXiv 2023

  42. [42]

    Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012

    2012

  43. [43]

    The Theory of Quantum Information

    John Watrous. The Theory of Quantum Information. Cambridge University Press, Cambridge, 2018

    2018

  44. [44]

    Stephanie Wehner, Matthias Christandl, and Andrew C. Doherty. Lower bound on the dimension of a quantum system given measured data. Phys. Rev. A, 78:062112, Dec 2008

    2008

  45. [45]

    Optimal state-determination by mutually unbiased measurements

    William K Wootters and Brian D Fields. Optimal state-determination by mutually unbiased measurements. Annals of Physics, 191(2):363–381, 1989. 30 QRAC Success probability p Decoder class Verification (5, 2) 0.81182 MUPVM symbolic (7, 2) 0.73798 MUPVM symbolic (8, 2) 0.70711 MUPVM symbolic (9, 2) 0.63060 MUPVM symbolic (10, 2) 0.57265 MUPVM symbolic (11, 2...

    1989