REVIEW
Channel capacities of classical and quantum list decoding
Quantum Physics · Submitted 4 Mar 2006 · 18 references
Pith's verdict: Main theorem—list decoding never beats ordinary capacity, even with exponentially growing lists—is correct and important; two local gaps in the proof are patchable.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
A paper proves that for any sequence of list sizes, even exponentially growing, the list-decoding capacity of a classical or classical-quantum channel equals the ordinary channel capacity; lists enlarge the decoder's possible answers but…
The reading
What carries the argument
The load-bearing mechanism is the counting identity for list codes: under the independent output distribution $\sigma$, the success region for an $L_n$-list decoder has probability exactly $L_n/N_n$, because every output belongs to the decoding sets of exactly $L_n$ input labels; in the quantum case the same identity reads $\sum_i Y_i^{(n)} = L_n I$. Combining this with the monotonicity of the relative Rényi entropy $\varphi(s|W\|\sigma)=\max_x \log \mathrm{Tr}\, W_x^{1-s}\sigma^s$ for $s\le 0$ yields the exponential bound $(1-P_e)^{1-s} N_n^{-s}L_n^s \le e^{n\varphi(s|W\|\sigma)}$. That bound drives $1-P_e\to 0$ whenever the rate exceeds $\max_x D(W_x\|\sigma)$, which is exactly the strong-converse step.
Extended reading notes
Core claim
The central claim is Theorem 1: for every sequence of list sizes $\{L_n\}$, the equality $C(W,\{L_n\}) = C^\dagger(W,\{L_n\}) = C(W)$ holds, where $W$ is either a classical channel or a classical-quantum channel. Here $C(W)$ is the ordinary capacity, $C(W,\{L_n\})$ allows the average error probability to vanish, and $C^\dagger(W,\{L_n\})$ is the weaker quantity that only requires the error probability to stay below 1. The proof establishes the converse by showing that any rate above capacity forces the success probability of the $L_n$-list decoder to decay to zero exponentially. The direct part is simple: any ordinary code can be turned into a list code by repeating each codeword $L_n$ times, so the list capacity is at least the ordinary capacity.
Load-bearing premise
The load-bearing premise is that the relative Rényi entropy is monotone under data processing for negative and zero values of the parameter s, so the exponential inequality (9) holds; the paper invokes this monotonicity by citation rather than proving it, and if it fails for s<0 the strong-converse decay argument collapses.
Editorial extensions
If this is right
- Above the ordinary capacity, every family of list codes with any prescribed list size $\{L_n\}$ has average success probability tending to zero, not merely error probability bounded away from zero.
- The strong converse survives the relaxation to list decoding: exactly as in ordinary coding, the maximum reliable rate is the capacity, and no list-size sequence can beat it.
- The theorem applies to classical-quantum channels, so the same equality governs communication rates when the decoder is a quantum measurement and the list is a set of classical hypotheses.
- The same counting identity yields list-decoding capacity formulas under cost constraints and for general sequences of channels, as the paper notes in its concluding remarks.
Reading between the lines
- The author does not go this far, but the proof's reliance on the single identity $L_n/N_n$ suggests the result should be stable under much weaker decoders, for example decoders that output an ordered list or a weighted set; the capacity calculation would likely still coincide with ordinary capacity.
- A numerical experiment on a binary symmetric channel with $L_n = 2^{nR_L}$ could check whether the finite-blocklength success probability decays at the rate predicted by inequality (11); a mismatch would point to the negative-parameter monotonicity step as the culprit.
- Extending the same argument to channels with memory or to entanglement-assisted settings would require replacing the product form $\sigma^{\otimes n}$ with a general output state; the paper's hypothesis-testing framework suggests this as the natural next step, but it is not proven here.
Original abstract
We focus on classical and quantum list decoding. The capacity of list decoding was obtained by Nishimura in the case when the number of list does not increase exponentially. However, the capacity of the exponential-list case is open even in the classical case while its converse part was obtained by Nishimura. We derive the channel capacities in the classical and quantum case with an exponentially increasing list. The converse part of the quantum case is obtained by modifying Nagaoka's simple proof for strong converse theorem for channel capacity. The direct part is derived by a quite simple argument.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
We focus on classical and quantum list decoding. The capacity of list decoding was obtained by Nishimura in the case when the number of list does not increase exponentially. However, the capacity of the exponential-list case is open even in the classical case while its converse part was obtained by Nishimura. We derive the channel capacities in the classical and quantum case with an exponentially increasing list. The converse part of the quantum case is obtained by modifying Nagaoka's simple proof for strong converse theorem for channel capacity. The direct part is derived by a quite simple argument.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We focus on classical and quantum list decoding. | background 0.79 | 0.25 | 0.03 | asserted 0.76 |
| s1 | The capacity of list decoding was obtained by Nishimura in the case when the number of list does not increase exponentially. | background 1.00 | 0.03 | 0.04 | asserted 1.00 |
| s2 | However, the capacity of the exponential-list case is open even in the classical case while its converse part was obtained by Nishimura. | gap 0.99 | 0.04 | 0.05 | asserted 1.00 |
| s3 | We derive the channel capacities in the classical and quantum case with an exponentially increasing list. | contribution 0.68 | 0.97 | 0.88 | asserted 1.00 |
| s4 | The converse part of the quantum case is obtained by modifying Nagaoka's simple proof for strong converse theorem for channel capacity. | method 0.92 | 0.89 | 0.07 | asserted 1.00 |
| s5 | The direct part is derived by a quite simple argument. | method 0.96 | 0.92 | 0.05 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
How the literature uses it
3 arXiv papers cite this in 9 sentences
Papers citing it · 4 sentences without a confident label
Uses its method or tool 2 papers
-
The key point of the second part is the meta converse for list decoding [ref] .
Secure list decoding · Proof of Converse Theorem · 0.97
-
The meta converse for list decoding [ref] shows that $ϵ_Q ≤|(ϕ_n,D_n)|_2/|(ϕ_n,D_n)|_1$ and $ϵ_P≤ϵ_A(ϕ_n,D_n)$.
Secure list decoding and its application to bit-string commitment · Proof of Converse Theorem · 0.87
Cites it as background 1 paper
-
Extensions to the quantum setting have been rare, with only few results available in the literature; see, for example, Ref. [ref] .
Zero-Error List Decoding for Classical-Quantum Channels · Introduction · 0.97
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.