pith. sign in

arxiv: 2601.09786 · v2 · submitted 2026-01-14 · 🪐 quant-ph · cs.IT· math-ph· math.IT· math.MP

Zero-Error List Decoding for Classical-Quantum Channels

Marco Dalai , Filippo Girardi , Ludovico Lami This is my paper

Pith reviewed 2026-05-16 14:21 UTC · model grok-4.3

classification 🪐 quant-ph cs.ITmath-phmath.ITmath.MP
keywords zero-error capacitylist decodingclassical-quantum channelspositive semi-definite matrixpure-state channelsquantum information theory
0
0 comments X

The pith

For pure-state classical-quantum channels whose state-overlap matrix is positive semi-definite, the zero-error list-decoding achievability bound for list size two equals the converse bound that holds for every fixed list size.

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

This paper studies zero-error list decoding of pure-state classical-quantum channels. It gives an explicit achievability bound that works for lists of size two and a converse bound that applies to any fixed list size. The two bounds are shown to be identical precisely when the matrix whose entries are the absolute overlaps between the channel states is positive semi-definite. The authors also note that, unlike the classical case, the rate at which the sphere-packing bound diverges need not be attainable by zero-error list codes even when the list size is fixed but arbitrarily large.

Core claim

The paper establishes that the zero-error list capacity of a pure-state classical-quantum channel equals the common value of its list-size-two achievability bound and its general-list-size converse bound whenever the matrix of pairwise absolute state overlaps is positive semi-definite; this common value is therefore the exact zero-error list capacity under the stated algebraic condition.

What carries the argument

The matrix of pairwise absolute state overlaps, whose positive semi-definiteness makes the achievability and converse bounds coincide and thereby determines the zero-error list capacity.

If this is right

  • For any such channel the zero-error list capacity with list size two is exactly characterized.
  • The same capacity value serves as an upper bound on the zero-error list capacity for every larger fixed list size.
  • The rate at which the sphere-packing bound diverges is not necessarily achievable by zero-error list codes, even in the limit of large fixed list size.
  • The exact capacity is therefore determined by a simple algebraic test on the channel states rather than by an optimization over codes.

Where Pith is reading between the lines

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

  • The positive semi-definiteness condition may hold for many channels of practical interest, such as those arising in quantum communication with pure states.
  • Checking whether the overlap matrix is positive semi-definite offers a concrete way to decide whether the zero-error list capacity is known exactly for a given channel.
  • The discrepancy with the classical setting suggests that quantum coherence imposes stricter constraints on zero-error list coding that survive even when list size grows.

Load-bearing premise

The channel states are pure and the matrix formed by their absolute pairwise overlaps is positive semi-definite.

What would settle it

A pure-state classical-quantum channel whose overlap matrix is not positive semi-definite yet whose zero-error list capacity still equals the list-size-two achievability bound, or whose capacity falls strictly below that bound even though the matrix is positive semi-definite.

Figures

Figures reproduced from arXiv: 2601.09786 by Filippo Girardi, Ludovico Lami, Marco Dalai.

Figure 1
Figure 1. Figure 1: Trine channel. All the vectors lie in a plane; [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
read the original abstract

The aim of this work is to study the zero-error capacity of pure-state classical-quantum channels in the setting of list decoding. We provide an achievability bound for list-size two and a converse bound holding for every fixed list size. The two bounds coincide for channels whose pairwise absolute state overlaps form a positive semi-definite matrix. Finally, we discuss a remarkable peculiarity of the classical-quantum case: differently from the fully classical setting, the rate at which the sphere-packing bound diverges might not be achievable by zero-error list codes, even when we take the limit of fixed but arbitrarily large list size.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies zero-error list decoding for pure-state classical-quantum channels. It derives an achievability bound for list size two and a converse bound that holds for any fixed list size. These bounds coincide precisely when the matrix of pairwise absolute state overlaps is positive semi-definite. The paper also identifies a distinction from the classical case: the rate at which the sphere-packing bound diverges need not be achievable by zero-error list codes, even in the limit of fixed but arbitrarily large list size.

Significance. If the derivations hold, the work advances zero-error quantum information theory by isolating an algebraic condition (positive semi-definiteness of the overlap matrix) under which matching bounds are obtained for list decoding. The explicit contrast with classical sphere-packing behavior supplies a concrete, falsifiable distinction between classical and quantum zero-error regimes. The conditional nature of the main result prevents overgeneralization and supplies a clear target for future constructions or counter-examples.

minor comments (3)
  1. The abstract and introduction should explicitly flag that all results are restricted to pure-state CQ channels; a short sentence in the preliminaries would prevent readers from assuming extension to mixed states.
  2. Notation for the absolute overlap matrix (e.g., the definition of its entries) appears in multiple places; a single consolidated definition with an accompanying small example would improve readability.
  3. The sphere-packing peculiarity is stated qualitatively; a brief remark on whether the divergence rate is strictly larger than the zero-error list rate for a concrete channel would strengthen the discussion.

Simulated Author's Rebuttal

4 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and the recommendation for minor revision. We address the points in the referee summary below.

read point-by-point responses

  1. Referee: The manuscript studies zero-error list decoding for pure-state classical-quantum channels.

    Authors: We confirm that this is the central topic of the work. revision: no

  2. Referee: It derives an achievability bound for list size two and a converse bound that holds for any fixed list size.

    Authors: This is accurate: the achievability result is stated for list size two, while the converse holds for every fixed list size. revision: no

  3. Referee: These bounds coincide precisely when the matrix of pairwise absolute state overlaps is positive semi-definite.

    Authors: We agree; this positive semi-definiteness condition is the precise algebraic criterion under which the bounds match. revision: no

  4. Referee: The paper also identifies a distinction from the classical case: the rate at which the sphere-packing bound diverges need not be achievable by zero-error list codes, even in the limit of fixed but arbitrarily large list size.

    Authors: This contrast with the classical sphere-packing behavior is indeed a key observation in the discussion section. revision: no

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained from channel parameters

full rationale

The paper states an achievability bound for list size two and a converse for any fixed list size that coincide precisely when the matrix of pairwise absolute state overlaps is positive semi-definite. These bounds are derived directly from the pure-state classical-quantum channel parameters and the stated algebraic condition without any reduction to fitted inputs, self-definitional loops, or load-bearing self-citations. The result is explicitly conditional on the PSD property and does not rename or smuggle in prior results as new predictions; the sphere-packing distinction from the classical case is presented as an observation rather than a derived claim that collapses to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only input supplies no explicit free parameters, axioms, or invented entities; all such quantities remain unknown.

pith-pipeline@v0.9.0 · 5404 in / 1017 out tokens · 32120 ms · 2026-05-16T14:21:00.597440+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · 1 internal anchor

  1. [1]

    Lower bounds to error probability for coding on discrete memoryless channels. I,

    C. Shannon, R. Gallager, and E. Berlekamp, “Lower bounds to error probability for coding on discrete memoryless channels. I,”Information and Control, vol. 10, no. 1, pp. 65–103, 1967. [Online]. Available: https: //www.sciencedirect.com/science/article/pii/S0019995867900526 1, 2

    work page 1967

  2. [2]

    Exponential error bounds for erasure, list, and decision feedback schemes,

    G. Forney, “Exponential error bounds for erasure, list, and decision feedback schemes,”IEEE Transactions on Information Theory, vol. 14, no. 2, pp. 206–220, 1968. 1

    work page 1968

  3. [3]

    List decoding—random coding exponents and expurgated exponents,

    N. Merhav, “List decoding—random coding exponents and expurgated exponents,”IEEE Transactions on Information Theory, vol. 60, no. 11, pp. 6749–6759, 2014. 1

    work page 2014

  4. [4]

    List decoding of polar codes,

    I. Tal and A. Vardy, “List decoding of polar codes,”IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213–2226, 2015. 1

    work page 2015

  5. [5]

    Upper bound on list-decoding radius of binary codes,

    Y . Polyanskiy, “Upper bound on list-decoding radius of binary codes,” IEEE Transactions on Information Theory, vol. 62, no. 3, pp. 1119– 1128, 2016. 1

    work page 2016

  6. [6]

    Algorithmic results in list decoding,

    V . Guruswami, “Algorithmic results in list decoding,”Found. Trends Theor. Comput. Sci., vol. 2, no. 2, pp. 107–195, Jan. 2007. [Online]. Available: https://doi.org/10.1561/0400000007 1

    work page doi:10.1561/0400000007 2007

  7. [7]

    Channel capacities of classical and quantum list decoding,

    M. Hayashi, “Channel capacities of classical and quantum list decoding,”

    work page

  8. [8]

    Channel capacities of classical and quantum list decoding

    [Online]. Available: https://arxiv.org/abs/quant-ph/0603031 1

    work page internal anchor Pith review Pith/arXiv arXiv

  9. [9]

    List decodable quantum ldpc codes,

    T. Bergamaschi, F. G. Jeronimo, T. Mittal, S. Srivastava, and M. Tulsiani, “List decodable quantum ldpc codes,” 2024. [Online]. Available: https://arxiv.org/abs/2411.04306 1

    work page arXiv 2024

  10. [10]

    Communicating over adversarial quantum channels using quantum list codes,

    D. Leung and G. Smith, “Communicating over adversarial quantum channels using quantum list codes,”IEEE Transactions on Information Theory, vol. 54, no. 2, pp. 883–887, 2008. 1

    work page 2008

  11. [11]

    Zero error capacity under list decoding,

    P. Elias, “Zero error capacity under list decoding,”IEEE Trans. Information Theory, vol. 34, no. 5, pp. 1070–1074, 1988. [Online]. Available: http://dx.doi.org/10.1109/18.21233 1, 2, 5

    work page doi:10.1109/18.21233 1988

  12. [12]

    On the size of separating systems and families of perfect hash functions,

    M. L. Fredman and J. Koml ´os, “On the size of separating systems and families of perfect hash functions,”SIAM Journal on Algebraic Discrete Methods, vol. 5, no. 1, pp. 61–68, 1984. [Online]. Available: https://doi.org/10.1137/0605009 1

    work page doi:10.1137/0605009 1984

  13. [13]

    Fredman–Koml ´os bounds and information theory,

    J. K ¨orner, “Fredman–Koml ´os bounds and information theory,”SIAM Journal on Algebraic Discrete Methods, vol. 7, no. 4, pp. 560–570,

    work page

  14. [14]

    Erasure, list, and detection zero- error capacities for low noise and a relation to identification,

    R. Ahlswede, N. Cai, and Z. ZHang, “Erasure, list, and detection zero- error capacities for low noise and a relation to identification,”IEEE Transactions on Information Theory, vol. 42, no. 1, pp. 55–62, 1996. 1

    work page 1996

  15. [15]

    Improved bounds for (b, k)- hashing,

    S. Della Fiore, S. Costa, and M. Dalai, “Improved bounds for (b, k)- hashing,”IEEE Transactions on Information Theory, vol. 68, no. 8, pp. 4983–4997, 2022. 1

    work page 2022

  16. [16]

    Zero- Error Capacity of Quantum Channels and Noiseless Subsystems,

    R. A. Medeiros, R. Alleaume, G. Cohen, and F. M. De Assis, “Zero- Error Capacity of Quantum Channels and Noiseless Subsystems,” in Proc. Int. Telecomm. Symposium. Fortaleza, Brazil, 2006, pp. 900–

    work page 2006

  17. [17]

    Entanglement-assisted zero-error capacity is upper-bounded by the lov ´aszϑfunction,

    S. Beigi, “Entanglement-assisted zero-error capacity is upper-bounded by the lov ´aszϑfunction,”Phys. Rev. A, vol. 82, p. 010303, Jul

    work page

  18. [18]

    Physical Review A33(5), 2913–2927 (1986)

    [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA. 82.010303 1

    work page doi:10.1103/physreva

  19. [19]

    Zero-error channel capacity and simulation assisted by non-local correlations,

    T. S. Cubitt, D. Leung, W. Matthews, and A. Winter, “Zero-error channel capacity and simulation assisted by non-local correlations,” IEEE Transactions on Information Theory, vol. 57, no. 8, pp. 5509– 5523, 2011. 1

    work page 2011

  20. [20]

    Zero-error communication via quantum channels, noncommutative graphs, and a quantum lov ´asz number,

    R. Duan, S. Severini, and A. Winter, “Zero-error communication via quantum channels, noncommutative graphs, and a quantum lov ´asz number,”IEEE Transactions on Information Theory, vol. 59, no. 2, pp. 1164–1174, 2013. 1

    work page 2013

  21. [21]

    No-signalling-assisted zero-error capacity of quantum channels and an information theoretic interpretation of the lov´asz number,

    R. Duan and A. Winter, “No-signalling-assisted zero-error capacity of quantum channels and an information theoretic interpretation of the lov´asz number,”IEEE Transactions on Information Theory, vol. 62, no. 2, pp. 891–914, 2016. 1

    work page 2016

  22. [22]

    Lower bounds on the probability of error for classical and classical-quantum channels,

    M. Dalai, “Lower bounds on the probability of error for classical and classical-quantum channels,”IEEE Transactions on Information Theory, vol. 59, no. 12, pp. 8027–8056, 2013. 1, 2

    work page 2013

  23. [23]

    On factor width and symmetric h-matrices,

    E. G. Boman, D. Chen, O. Parekh, and S. Toledo, “On factor width and symmetric h-matrices,”Linear Algebra and its Applications, vol. 405, pp. 239–248, 2005. [Online]. Available: https://www.sciencedirect. com/science/article/pii/S0024379505001977 2

    work page 2005

  24. [24]

    Lower bounds on the probability of error for classical and classical-quantum channels,

    M. Dalai, “Lower bounds on the probability of error for classical and classical-quantum channels,”IEEE Transactions on Information Theory, vol. 59, no. 12, pp. 8027–8056, Dec. 2013. [Online]. Available: http://dx.doi.org/10.1109/TIT.2013.2283794 3

    work page doi:10.1109/tit.2013.2283794 2013

  25. [25]

    Coding theorems for quantum channels,

    A. S. Holevo, “Coding theorems for quantum channels,”arXiv:quant- ph/9809023v1, 1998. 4

    work page arXiv 1998

  26. [26]

    Reliability function of general classical-quantum channel,

    A. Holevo, “Reliability function of general classical-quantum channel,” IEEE Transactions on Information Theory, vol. 46, no. 6, pp. 2256– 2261, 2000. 4

    work page 2000

  27. [27]

    Achieving the holevo capacity of a pure state classical-quantum channel via unambiguous state discrimi- nation,

    M. Takeoka, H. Krovi, and S. Guha, “Achieving the holevo capacity of a pure state classical-quantum channel via unambiguous state discrimi- nation,” in2013 IEEE International Symposium on Information Theory, 2013, pp. 166–170. 4

    work page 2013

  28. [28]

    Evaluation of expurgated bound exponents,

    F. Jelinek, “Evaluation of expurgated bound exponents,”IEEE Transac- tions on Information Theory, vol. 14, no. 3, pp. 501–505, 1968. 4

    work page 1968

  29. [29]

    Information-theoretical aspects of quantum measurement,

    A. S. Holevo, “Information-theoretical aspects of quantum measurement,”Problemy Peredachi Informatsii, vol. 9, no. 2, pp. 31–42, 1973. [Online]. Available: https://mathnet.ru/ppi892 5

    work page 1973

  30. [30]

    Optimal detection of quantum information,

    A. Peres and W. K. Wootters, “Optimal detection of quantum information,”Phys. Rev. Lett., vol. 66, pp. 1119–1122, Mar

    work page

  31. [31]

    Physical Review Letters 85(10), 2200–2203 (2000)

    [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett. 66.1119 5

    work page doi:10.1103/physrevlett

  32. [32]

    Improved upper bound for the size of a trifferent code,

    S. Bhandari and A. Khetan, “Improved upper bound for the size of a trifferent code,”Combinatorica, vol. 45, no. 1, p. 2, 2024. [Online]. Available: https://doi.org/10.1007/s00493-024-00130-2 5

    work page doi:10.1007/s00493-024-00130-2 2024