4
$\begingroup$

The quantity $Q_1(\Phi) = max_{\rho} I_C(\rho, \Phi)$, is called one-letter capacity of channel $\Phi$. I want to know, what is meant by the term "single-letter" capacity here, often used in information theory? The term can be found for example in this article (with free access).

$\endgroup$
2
  • 1
    $\begingroup$ Hi, can you (1) edit your question to point to the abstract instead of the PDF, to help people with limited bandwidth, and (2) edit to explain how the term is used in the paper, and what you think it might mean? $\endgroup$
    – Mark S
    Nov 19, 2021 at 2:28
  • 1
    $\begingroup$ There doesn't seem to be much quantum in this question given that, as recognised in the question, this is also an issue for classical channels. Second result on my google search give this answer: crypto.stackexchange.com/questions/71740/… $\endgroup$
    – DaftWullie
    Nov 19, 2021 at 9:59

2 Answers 2

5
$\begingroup$

In a series of individual works, Lloyd, Shor, and then Devetak developed what is known as the "LSD Theorem," which gives a formula for the quantum capacity of a quantum channel. The result states that the quantum capacity $Q$ of a channel $\Phi$ is the regularization of the coherent information, written $$Q(\Phi)=\frac{\lim_{n\rightarrow \infty}}{n}\max_\rho\{ I_C(\rho,\Phi^{\otimes n})\}=\frac{\lim_{n\rightarrow\infty}}{n}Q_n(\Phi)$$

The LSD formula is satisfying because it is analogous to Shannon's description of the classical capacity of a classical channel as the regularization of the mutual information. However, unlike in the classical case, there doesn't seem to be a way of simplifying the limit in the LSD formula, making the task of computing the capacity of a quantum channel untractable (e.g. we don't even know the quantum capacity of the qubit depolarizing channel in practical noise regimes).

Rather than altogether abandoning the study of quantum channel capacities, researchers looked for examples or classes of channels where the formula for $Q$ does simplify (for instance, this happens for the class of degradable quantum channels). Of particular note are quantum channels, which have a single-letter formula for their quantum capacity.

A "single-letter" (aka "one-shot" or "single-shot") formula is said to hold for the class of quantum channels for which to compute the full quantum capacity one only needs a single use of the channel, i.e. the channels $\Phi$ for which $Q_1(\Phi)=Q(\Phi)$, rather than needing to regularize over an unbounded number of channel uses i.e. $\Phi^{\otimes n}$ for larger and larger $n>0$.

One reason why, in general, $Q(\Phi)\neq Q_1(\Phi)$, and more broadly the issue with simplifying the regularization of the coherent information appears to stem from the fact that the quantum capacity, unlike the classical capacity, is not additive. For example, it is known that there exists a quantum channel $\Psi$ for which $$Q_2(\Psi)>0,\text{ and } Q_1(\Psi)=0,$$ demonstrating that the inequality $$Q_2(\Psi)>Q_1(\Psi)+Q_1(\Psi),$$ is strict. This surprising phenomenon, called superactivation, was discovered by Smith and Yard.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks @Condo for that detailed explanation. Why is it called as "single-letter" formula? $\endgroup$
    – User101
    Nov 29, 2021 at 13:29
  • $\begingroup$ @Micheal the term "single-letter" refers to the fact that the capacity can be calculated over a single use of the channel. The language comes from classical information theory, e.g. a "single-letter" expression for the mutual information is $I(X,Y)$ while a "multi-letter" expression is $I(X^n,Y^n)$ for $n>1$. $\endgroup$
    – Condo
    Nov 29, 2021 at 15:48
0
$\begingroup$

I think we have here superposition of double meaning of 'single-letter' term:

  1. Single-letter in mathematical notation is just ‘single-letter symbol’ used for mathematical quantities in equations and expressions or as a formula name, with subscript or superscript indices or labels, if necessary. There are already discussions whether is a pain or gain here: https://math.stackexchange.com/questions/24241/why-do-mathematicians-use-single-letter-variables

  2. For this specific 'single-letter formula related to channel capacity' the source paper is Shannon's work:

    C. E. Shannon, “A mathematical theory on communication,” Bell System Technical Journal, no. 27, pp. 379–423, October 1948

    which is mentioned in already existing answer: https://math.stackexchange.com/questions/164088/meaning-of-the-term-single-letter-formula

    Shannon in his paper showed that the capacity of Discrete Memoryless Channels (DMCs) $$ \{{\mathbb{A}},{\mathbb{B}},\{\textbf{P}\underset{B|A}(b|a):(a,b)\in {}{\mathbb{A}}\times {\mathbb{B}}\}\} $$ is characterized by single letter formulae $C=max\underset{P\underset{A}{}}{}I(A;B)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.