text:
# Exponents of quantum fixed-length pure state source coding

## I Introduction

As was proven by Schumacher , and Jozsa and Schumacher , we can compress the unknown source state into the coding length $`nH(\overline{\rho }_p)`$ with a sufficiently small error when the source state on $`n`$ quantum systems obeys the $`n`$-independent identical distribution (i.i.d.) of the known probability $`p`$, where $`\overline{\rho }_p:=_\rho p(\rho )\rho `$ and $`H(\rho )`$ is the von Neumann entropy $`Tr\rho \mathrm{log}\rho `$. Jozsa and Schumacher’s protocol depends on the mixture state $`\overline{\rho }_p`$, and in this protocol, the coding length is independent for the input. Therefore, this type code is called a quantum fixed length source code.

Concerning the quantum source coding, there are two criteria: One is the blind coding, in which the input is an unknown quantum state. The other is the visible coding, in which the input is classical information that determines the quantum state, i.e., the encoder knows the input quantum state. When a source consists of pure states and depends on an i.i.d. distribution of the probability $`p`$, the bound of the compression rate (i.e. the minimum admissible rate) equals the entropy rate $`H(\overline{\rho }_p)`$. The proof of this statement is divided into two parts: One is the possibility to compress the quantum source into a larger rate than the entropy rate, which is called the direct part. The other is the impossibility to compress the quantum source into a smaller rate than the entropy rate, which is called the converse part. The former is given by Schumacher’s result. The latter was proven by Barnum et al.  only in the blind case, however Horodecki  proved it in both cases by a simpler method. Winter proved that the both settings have the strong converse property, i.e. if we compress into a smaller rate than the entropy rate, the average error goes to $`1`$. Moreover, depending only on the coding length $`nR`$, Jozsa et al.  constructed a code which is independent of the distribution which the input obeys. In their protocol, the average error tends to $`0`$ when $`H(\rho )<R`$. Such a code is called a quantum universal fixed-length source code. Of course, we can consider a quantum variable-length source code, but discuss it in another paper .

However, only with the knowledge of the minimum admissible rate we cannot estimate what a compression rate is available for a given error $`\delta >0`$ and a given integer $`n`$. For such an estimate, we need to discuss the decreasing speed of the average error for a fixed rate $`R`$. In the classical information theory, in order to treat this speed, we focus the exponential rate (exponent) of the error probability, and the optimal exponent is greater than zero when the coding rate $`R`$ is greater than the entropy rate. Conversely, when the rate $`R`$ is smaller than the entropy rate, the correct probability exponentially goes to zero. These optimal exponents have been already calculated by using type method. (see Csiszár and Körner ).

In this paper, we treat only a quantum fixed-length code at both criteria in the case where any source consists of pure states. We optimize the exponents of the average error and the average fidelity in sec. III. Using a group representation theoretical type method introduced in Appendix B, we derive an upper bound of the error of the quantum universal fixed-length source code constructed by Jozsa et al. for any $`n`$ and any $`R`$ as (20), (21) and (22) in sec. IV. This upper bound yields its attainability of the optimal exponents. In sec. VI, non-existence of a code exceeding the exponents is proven, which is called the converse part. In the converse part, an inequality is essential and is proven from Nielsen and Kempe’s lemma  in sec. V.

## II Summary of previous results

Blind and visible codes are mathematically formulated as follows. Assume that a quantum pure state $`\rho _i`$ on $``$ corresponding to label $`i\mathrm{\Xi }`$ is generated with probability $`p_i`$ . We denote the set of quantum states on $``$ by $`𝒮()`$. Therefore, the source is described by $`\{\rho _i,p_i\}_{i\mathrm{\Xi }}`$. In the blind setting, the encoder is described by a CP map $`E`$ from $`𝒮()`$ to $`𝒮(𝒦)`$, and the decoder is described by a CP map $`D`$ from $`𝒮(𝒦)`$ to $`𝒮()`$. The average error is given by $`ϵ(E,D):=_{i\mathrm{\Xi }}p_i(1TrDE(\rho _i)\rho _i)`$, and the average fidelity is given by $`_{i\mathrm{\Xi }}p_iTrDE(\rho _i)\rho _i`$. We call a triple $`(𝒦,E,D)`$ a blind code.

In the visible setting, the encoder is described by a map $`F`$ from $`\mathrm{\Xi }`$ to $`𝒮(𝒦)`$. Then, the average error is given by $`ϵ(F,D):=_{i\mathrm{\Xi }}p_i(1TrDF(i)\rho _i)`$. In this setting, we treat the trade-off between decreasing $`dim𝒦`$ and $`ϵ(F,D)`$. We call a triple $`(𝒦,E,D)`$ a blind code. Similarly, we call a triple $`(𝒦,F,D)`$ a visible code. In the both settings, we treat the trade-off between decreasing $`dim𝒦`$ and $`ϵ(E,D)`$ ($`ϵ(F,D)`$).

A blind code $`(𝒦,E,D)`$ can be regarded as a visible code in the case where $`F(i):=E(\rho _i)`$. We have more choices in the visible setting than in the blind setting. A blind code is used for saving memories in quantum computing. A visible code is used for efficient use of quantum channel in quantum cryptography, for example, the B92 protocol , .

In the $`n`$-i.i.d. setting, the quantum state $`\rho _{n,\stackrel{}{i}_n}:=\rho _{i_1}\rho _{i_2}\mathrm{}\rho _{i_n}`$ on the tensored Hilbert space $`^n`$ generates with the probability $`p_{n,\stackrel{}{i}_n}:=p_{i_1}p_{i_2}\mathrm{}p_{i_n}`$, where $`\stackrel{}{i}_n=(i_1,i_2,\mathrm{},i_n)`$. This setting is written by the source $`\{\rho _{n,\stackrel{}{i}_n},p_{n,\stackrel{}{i}_n}\}_{\stackrel{}{i}_n\mathrm{\Xi }^n}`$, which is called a $`n`$-discrete memoryless source (DMS) generated by the source $`\{\rho _i,p_i\}_{i\mathrm{\Xi }}`$. Now, we define the minimum admissible rate $`R_B(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ ($`R_V(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$) and the converse minimum admissible rate $`R_B^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ ($`R_V^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$) of the DMS generated by $`\{\rho _i,p_i\}_{i\mathrm{\Xi }}`$ in the blind setting (in the visible setting) as follows, respectively.

$`R_B(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`inf\{\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}dim𝒦_n|\begin{array}{cc}\{(𝒦_n,E_n,D_n)\},\hfill & \\ ϵ(E_n,D_n)0\hfill & \end{array}\}`$
$`R_V(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`inf\{\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}dim𝒦_n|\begin{array}{cc}\{(𝒦_n,F_n,D_n)\},\hfill & \\ ϵ(F_n,D_n)0\hfill & \end{array}\}`$
$`R_B^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`inf\{\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}dim𝒦_n|\begin{array}{cc}\{(𝒦_n,E_n,D_n)\},\hfill & \\ \overline{\mathrm{lim}}ϵ(E_n,D_n)<1\hfill & \end{array}\}`$
$`R_V^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`inf\{\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}dim𝒦_n|\begin{array}{cc}\{(𝒦_n,F_n,D_n)\},\hfill & \\ \overline{\mathrm{lim}}ϵ(F_n,D_n)<1\hfill & \end{array}\}.`$
The following theorem is a known result.

###### Theorem 1

The equations

$`R_B(\{\rho _i,p_i\}_{i\mathrm{\Xi }})=R_V(\{\rho _i,p_i\}_{i\mathrm{\Xi }})=R_B^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`=R_V^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})=H(\overline{\rho }_p)`$ (1)
hold, where $`\overline{\rho }_p:=_{i\mathrm{\Xi }}p_i\rho _i`$ and $`H(\rho )`$ denotes von Neumann entropy $`Tr\rho \mathrm{log}\rho `$.

Since the following relations

$`R_B(\{\rho _i,p_i\}_{i\mathrm{\Xi }})R_V(\{\rho _i,p_i\}_{i\mathrm{\Xi }}),`$
$`R_B^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})R_V^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }}),`$
$`R_B(\{\rho _i,p_i\}_{i\mathrm{\Xi }})R_B^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }}),`$
$`R_V(\{\rho _i,p_i\}_{i\mathrm{\Xi }})R_V^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
are trivial, it is sufficient for (1) to prove

$`R_B(\{\rho _i,p_i\}_{i\mathrm{\Xi }})H(\rho ),R_V^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})H(\rho ).`$
Schumacher  proved the direct part: $`R_B(\{\rho _i,p_i\}_{i\mathrm{\Xi }})H(\overline{\rho }_p)`$, and Jozsa-Schumacher  simplified it. Barnum et al.  proved the weak converse part: $`R_B(\{\rho _i,p_i\}_{i\mathrm{\Xi }})H(\overline{\rho }_p)`$ of the blind case, and Horodecki  proved the weak converse part: $`R_V(\{\rho _i,p_i\}_{i\mathrm{\Xi }})H(\overline{\rho }_p)`$ of the visible case, which is a stronger argument than the one of the blind case. Winter  obtained the strong converse part: $`R_V^{}(\{\rho _i,p_i\}_{i\mathrm{\Xi }})H(\overline{\rho }_p)`$. Moreover, Petz and Mosonyi  treated the general stationary case, in which there are memory effects.

## III Main results

Next, we define the exponents of the average error (the reliable functions) $`r_{e,B}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ and $`r_{e,V}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$, and the exponents of the average fidelity (the converse reliable functions) $`r_{e,B}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ and $`r_{e,V}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ by

$`r_{e,B}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`sup\left\{\underset{¯}{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}ϵ(E_n,D_n)\right|\begin{array}{c}\{(𝒦_n,E_n,D_n)\},\hfill \\ \overline{\mathrm{lim}}\frac{1}{n}\mathrm{log}dim𝒦_nR\hfill \end{array}\}`$
$`r_{e,V}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`sup\left\{\underset{¯}{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}ϵ(F_n,D_n)\right|\begin{array}{c}\{(𝒦_n,F_n,D_n)\},\hfill \\ \overline{\mathrm{lim}}\frac{1}{n}\mathrm{log}dim𝒦_nR\hfill \end{array}\}`$
$`r_{e,B}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`inf\left\{\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}(1ϵ(E_n,D_n))\right|\begin{array}{c}\{(𝒦_n,E_n,D_n)\},\hfill \\ \overline{\mathrm{lim}}\frac{1}{n}\mathrm{log}dim𝒦_nR\hfill \end{array}\}`$
$`r_{e,V}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`inf\left\{\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}(1ϵ(F_n,D_n))\right|\begin{array}{c}\{(𝒦_n,F_n,D_n)\},\hfill \\ \overline{\mathrm{lim}}\frac{1}{n}\mathrm{log}dim𝒦_nR\hfill \end{array}\}.`$
The following is the main theorem.

###### Theorem 2

Assume that $`0R<\mathrm{log}d`$ and $`d=dim`$. We diagonalize $`\overline{\rho }_p`$ as $`\overline{\rho }_p=_ia_i|e_ie_i|`$ such that $`a_ia_{i+1}`$. Then, $`𝐚:=\{a_i\}`$ is a probability distribution on $`\{1,\mathrm{},d\}`$. The relations

$`r_{e,B}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`=r_{e,V}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`=\underset{0<s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ (2)
$`=\underset{H(\sigma )R}{\mathrm{min}}D(\sigma \overline{\rho }_p)`$ (3)
$`=\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚)`$ (4)
$`r_{e,B}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`r_{e,V}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`=\underset{s1}{sup}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ (5)
$`=\underset{H(\sigma )R}{\mathrm{min}}D(\sigma \overline{\rho }_p)`$ (6)
$`=\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚)`$ (7)
hold, where $`\psi (s)`$ denotes the Rény entropy $`\mathrm{log}Tr\overline{\rho }_p^s`$, $`D(\sigma \rho )`$ denotes the quantum relative entropy $`Tr\sigma (\mathrm{log}\sigma \mathrm{log}\rho )`$, and $`𝐛`$ denotes a probability on $`\{1,\mathrm{},d\}`$.

Our proof of Theorem 2 is outlined as follows. Since any blind code can be demonstrated as a visible code, the relations

$`r_{e,B}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`r_{e,V}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ (8)
$`r_{e,B}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`r_{e,V}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ (9)
are trivial. In sec.IV, we universally construct the optimal quantum fixed-length code with the rate $`R`$. This construction is independent of $`\overline{\rho }_p`$, and depends only on the rate $`R`$. From this construction, we obtain

$`r_{e,B}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚)`$ (10)
$`r_{e,V}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚),`$ (11)
which is called the direct part. In sec. VI, we prove

$`r_{e,V}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`\underset{0<s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ (12)
$`r_{e,V}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`\underset{s1}{sup}{\displaystyle \frac{(1s)R\psi (s)}{s}},`$ (13)
which is called the converse part. The equivalence between RHSs of (10),(12) and (3) ((11),(13) and (6)) is proven in Appendix A, respectively.

###### Remark 1

The inequality $`r_{e,V}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})\mathrm{min}\{D(\sigma \rho )|H(\sigma )R\}`$ was proven by Winter .

###### Remark 2

We can adopt another criteria for error as:

$`ϵ_b(E,D)`$ $`:={\displaystyle \underset{i\mathrm{\Xi }}{}}p_i(1\sqrt{TrDF(\rho _i)\rho _i})`$
$`ϵ_b(F,D)`$ $`:={\displaystyle \underset{i\mathrm{\Xi }}{}}p_i(1\sqrt{TrDF(i)\rho _i}).`$
Note that $`(1\sqrt{TrDF(i)\rho _i})=(1Tr|DF(i)\rho _i|)`$ equals Bures distance. In this case, we can define other reliable functions $`r_{e,B,b}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ and $`r_{e,V,b}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$, and other converse reliable functions $`r_{e,B,b}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ and $`r_{e,V,b}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ by

$`r_{e,B,b}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`sup\left\{\underset{¯}{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}ϵ_b(E_n,D_n)\right|\begin{array}{c}\{(𝒦_n,E_n,D_n)\},\hfill \\ \overline{\mathrm{lim}}\frac{1}{n}\mathrm{log}dim𝒦_nR\hfill \end{array}\}`$
$`r_{e,V,b}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`sup\left\{\underset{¯}{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}ϵ_b(F_n,D_n)\right|\begin{array}{c}\{(𝒦_n,F_n,D_n)\},\hfill \\ \overline{\mathrm{lim}}\frac{1}{n}\mathrm{log}dim𝒦_nR\hfill \end{array}\}`$
$`r_{e,B,b}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`inf\left\{\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}(1ϵ_b(E_n,D_n))\right|\begin{array}{c}\{(𝒦_n,E_n,D_n)\},\hfill \\ \overline{\mathrm{lim}}\frac{1}{n}\mathrm{log}dim𝒦_nR\hfill \end{array}\}`$
$`r_{e,V,b}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`:=`$ $`inf\left\{\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}(1ϵ_b(F_n,D_n))\right|\begin{array}{c}\{(𝒦_n,F_n,D_n)\},\hfill \\ \overline{\mathrm{lim}}\frac{1}{n}\mathrm{log}dim𝒦_nR\hfill \end{array}\}.`$
As proven in Appendix C, the following relations between two criteria

$`r_{e,B,b}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`=r_{e,B}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ (14)
$`r_{e,V,b}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`=r_{e,V}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ (15)
$`r_{e,B}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`r_{e,B,b}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ (16)
$`r_{e,V}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`r_{e,V,b}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ (17)
hold.

## IV Construction of a universal fixed-length source code to achieve the optimal rate

We construct a universal quantum fixed-length source code to achieve the optimal rate in Theorem 2. For any $`r>0`$ and $`R>0`$, the set $`\{\rho 𝒮()|\mathrm{min}_{H(\sigma )R}D(\sigma \rho )=r\}`$ is covariant for the actions of the $`d`$-dimensional special unitary group $`SU(d)`$, and any $`n`$-i.i.d. distribution $`p^n`$ is invariant for the action of the $`n`$-th symmetric group $`S_n`$ on the tensored space $`^n`$. Thus, our code should satisfy the invariance for these actions on $`^n`$.

Now, we focus on the irreducible decomposition of the tensored space $`^n`$ concerning the representations of $`S_n`$ and $`SU(d)`$, and define the Young index $`𝐧`$ as,

$`𝐧:=(n_1,\mathrm{},n_d),{\displaystyle \underset{i=1}{\overset{d}{}}}n_i=n,n_in_{i+1},`$
and denote the set of Young indices $`𝐧`$ by $`Y_n`$. Young index $`𝐧`$ uniquely corresponds to the irreducible unitary representation of $`S_n`$ and the one of $`SU(d)`$. Now, we denote the representation space of the irreducible unitary representation of $`S_n`$ ($`SU(d)`$) corresponding to $`𝐧`$ by $`𝒱_𝐧`$ ($`𝒰_𝐧`$), respectively. In particular, regarding a unitary representation of $`SU(d)`$, Young index $`𝐧`$ gives the highest weight of the corresponding representation. Then, the tensored space $`^n`$ is decomposed as follows; i.e. $`^n`$ is equivalent with the following direct sum space under the representation of $`S_n`$ and $`SU(d)`$.

$`^n={\displaystyle \underset{𝐧}{}}𝒲_𝐧,𝒲_𝐧:=𝒰_𝐧𝒱_𝐧.`$
Since this representation of the group $`S_n\times SU(d)`$ is unitary, any irreducible components $`𝒲_𝐧`$ are orthogonal with one another. For details, see Weyl , Goodman and Wallach , and Iwahori . The efficiency of this representation method was discussed from several viewpoints. Regarding fixed-length source coding, it was discussed by Jozsa et. al. . Regarding quantum relative entropy, it was by Hayashi. Regarding quantum hypothesis testing, it was by Hayashi. Regarding estimation of spectrum, it was by Keyl and Werner.

Next, we construct a blind code with rate $`R`$. We define the Hilbert space $`𝒦_{R,n}`$, the blind encoder $`E_{R,n}`$, the visible encoder $`F_{R,n}`$ and the decoder $`D_{R,n}`$ by

$`𝒦_{R,n}:=`$ $`{\displaystyle \underset{𝐧:H(\frac{𝐧}{n})R}{}}𝒲_𝐧`$
$`E_{R,n}(\rho ):=`$ $`P_{R,n}\rho P_{R,n}+Tr\rho (IP_{R,n}){\displaystyle \frac{I_{𝒦_{R,n}}}{TrI_{𝒦_{R,n}}}}`$
$`F_{R,n}(\stackrel{}{i}_n):=`$ $`{\displaystyle \frac{P_{R,n}\rho _{n,\stackrel{}{i}_n}P_{R,n}}{TrP_{R,n}\rho _{n,\stackrel{}{i}_n}P_{R,n}}}`$
$`D_{R,n}(\rho ):=`$ $`\rho ,`$
where we denote the projection to $`𝒦_{R,n}`$ by $`P_{R,n}`$.

###### Lemma 3

We define $`R_n`$ by

$`R_n:=R{\displaystyle \frac{4d}{n}}\mathrm{log}(n+d).`$ (18)
The rates of the blind code $`\{(𝒦_{R,n},E_{R,n},D_{R,n})\}`$ and the visible code $`\{(𝒦_{R,n},F_{R,n},D_{R,n})\}`$ satisfies

$`dim𝒦_{R_n,n}e^{nR}.`$ (19)
When the mixture $`\overline{\rho }_p`$ of the source is diagonalized as $`_{j=1}^da_j|e_je_j|`$, we can evaluate the average errors as

$`ϵ(F_{R_n,n},D_{R_n,n})`$
$``$ $`(n+d)^{4d}\mathrm{exp}\left(n\underset{H(𝐛)R_n}{\mathrm{min}}D(𝐛𝐚)\right)`$ (20)
$`ϵ(E_{R_n,n},D_{R_n,n})`$
$``$ $`2(n+d)^{4d}\mathrm{exp}\left(n\underset{H(𝐛)R_n}{\mathrm{min}}D(𝐛𝐚)\right)`$ (21)
$`1ϵ(F_{R_n,n},D_{R_n,n})`$
$``$ $`(n+d)^{\frac{d(d+1)}{2}}\mathrm{exp}\left(n\underset{𝐧Y_n:H\left(\frac{𝐧}{n}\right)R_n}{\mathrm{min}}D\left({\displaystyle \frac{𝐧}{n}}𝐚\right)\right),`$ (22)
where $`𝐚`$ is defined as $`𝐚:=\{a_i\}`$ and $`𝐛=\{b_i\}`$ denotes a probability on $`\{1,\mathrm{},d\}`$. Taking the limit, we obtain

$`\underset{¯}{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}ϵ(E_{R_n,n},D_{R_n,n})`$ $`\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚),`$ (23)
$`\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}\left(1ϵ(F_{R_n,n},D_{R_n,n})\right)`$ $`\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚).`$ (24)
Inequalities (23) and (24) imply (10) and (11), respectively. Conversely, the opposite inequalities of (23) and (24) are guaranteed by inequalities (12) and (13).

###### Remark 3

The subspace $`𝒦_{R_n,n}`$ is equal to the subspace $`\mathrm{{\rm Y}}`$ introduced by Jozsa et al.  because both are invariant for the action of the symmetric group. Therefore, our code $`E_{R_n,n}`$ coincides with their protocol.

###### Remark 4

Even if the source states $`\rho _i`$ are not pure, we can prove inequalities similar to (20), (21) and (22) by using some calculations similar to Appendix C in Hayashi and Matsumoto. However, in this case, this exponent does not seem to be optimal.

Proof of Lemma 3:  Using Lemma 10, we can evaluate as

$`dim𝒦`$ $`(n+1)^d\underset{𝐧Y_n:H\left(\frac{𝐧}{n}\right)R_n}{\mathrm{max}}dim𝒲_𝐧`$
$`(n+1)^{2d}\underset{𝐧Y_n:H\left(\frac{𝐧}{n}\right)R_n}{\mathrm{max}}dim𝒱_𝐧`$
$`(n+1)^{2d}(n+d)^{2d}e^{nR_n}.`$
Thus, we obtain (19). The average error of the visible code can be calculated as

$`ϵ(F_{R_n,n},D_{R_n,n})`$
$`=`$ $`{\displaystyle \underset{\stackrel{}{i}_n\mathrm{\Xi }^n}{}}p_{n,\stackrel{}{i}_n}\left(1Tr\rho _{n,\stackrel{}{i}_n}{\displaystyle \frac{P_{R_n,n}\rho _{n,\stackrel{}{i}_n}P_{R_n,n}}{TrP_{R_n,n}\rho _{n,\stackrel{}{i}_n}P_{R_n,n}}}\right)`$
$`=`$ $`{\displaystyle \underset{\stackrel{}{i}_n\mathrm{\Xi }^n}{}}p_{n,\stackrel{}{i}_n}\left(1TrP_{R_n,n}\rho _{n,\stackrel{}{i}_n}\right)`$
$`=`$ $`\left(1TrP_{R_n,n}{\displaystyle \underset{\stackrel{}{i}_n\mathrm{\Xi }^n}{}}p_{n,\stackrel{}{i}_n}\rho _{n,\stackrel{}{i}_n}\right)`$
$`=`$ $`\left(1TrP_{R_n,n}\overline{\rho }_p^n\right).`$
Therefore, Lemma 11 guarantees (20) and (22). Conversely,

$`ϵ(E_{R_n,n},D_{R_n,n})`$
$`=`$ $`{\displaystyle \underset{\stackrel{}{i}_n\mathrm{\Xi }^n}{}}p_{n,\stackrel{}{i}_n}[1Tr\rho _{n,\stackrel{}{i}_n}`$
$`(P_{R_n,n}\rho _{n,\stackrel{}{i}_n}P_{R_n,n}+Tr\rho _{n,\stackrel{}{i}_n}(IP_{R_n,n}){\displaystyle \frac{I_{𝒦_{R_n,n}}}{TrI_{𝒦_{R_n,n}}}})]`$
$``$ $`{\displaystyle \underset{\stackrel{}{i}_n\mathrm{\Xi }^n}{}}p_{n,\stackrel{}{i}_n}\left(1Tr\rho _{n,\stackrel{}{i}_n}P_{R_n,n}\rho _{n,\stackrel{}{i}_n}P_{R_n,n}\right)`$
$`=`$ $`{\displaystyle \underset{\stackrel{}{i}_n\mathrm{\Xi }^n}{}}p_{n,\stackrel{}{i}_n}\left(1(Tr\rho _{n,\stackrel{}{i}_n}P_{R_n,n})^2\right)`$
$``$ $`\left(1\left({\displaystyle \underset{\stackrel{}{i}_n\mathrm{\Xi }^n}{}}p_{n,\stackrel{}{i}_n}Tr\rho _{n,\stackrel{}{i}_n}P_{R_n,n}\right)^2\right)`$
$`=`$ $`1\left(Tr\overline{\rho }_p^nP_{R_n,n}\right)^22\left(1Tr\overline{\rho }_p^nP_{R_n,n}\right)`$
which implies (21).

## V Necessary inequality for the converse part

For an Hermitian matrix $`X`$, we define the projections $`\{X0\},\{X<0\}`$ by

$`\{X0\}={\displaystyle \underset{s_j0}{}}E_j,\{X<0\}={\displaystyle \underset{s_j<0}{}}E_j,`$
where the spectral decomposition of $`X`$ is given by $`X=_js_jE_j`$ ($`s_j`$ is an eigenvalue corresponding to projection $`E_j`$). Under a source $`\{\rho _i,p_i\}_{i\mathrm{\Xi }}`$, the following lemma holds.

###### Lemma 4

Any visible code $`(𝒦,F,D)`$ satisfies the following inequalities

$`ϵ(F,D)+e^\lambda dim𝒦`$ $`Tr\overline{\rho }_p\{\overline{\rho }_pe^\lambda <0\}`$ (25)
$`1ϵ(F,D)`$ $`e^\lambda dim𝒦+Tr\overline{\rho }_p\{\overline{\rho }_pe^\lambda 0\}`$ (26)
for $`\lambda `$.

Moreover, the inequality

$`1ϵ(F,D)`$ $`e^\lambda dim𝒦+e^{(1s)\lambda +\psi (s)}`$ (27)
holds for $`\lambda ,s1`$.

For our proof of the above lemma, we require the following two lemmas.

###### Lemma 5

The set of visible encoders from $`\mathrm{\Xi }`$ to $`𝒮(𝒦)`$ coincides with the convex hull of the set of extremal points, which equals

$`\left\{F\right|F(i)\text{ is a pure state }i\mathrm{\Xi }\}.`$ (28)
Proof:  If a visible encoder $`F`$ satisfies that $`f(i)`$ is a pure state for any $`i\mathrm{\Xi }`$, then $`F`$ is an extremal point. It is sufficient to show that for any visible encoder $`F(i)=_{j_i}s_{j_i}|\varphi _{j_i}\varphi _{j_i}|`$ is written by a convex hull of (28). A visible encoder $`F(j_1,j_2,\mathrm{},j_n)`$ defined by

$`F(j_1,j_2,\mathrm{},j_n|i)=|\varphi _{j_i}\varphi _{j_i}|`$
belongs to (28). Since the relation $`F=_{j_1,j_2,\mathrm{},j_n}s_{j_1}s_{j_2}\mathrm{}s_{j_n}F(j_1,j_2,\mathrm{},j_n)`$ holds, we obtain the lemma.

###### Lemma 6

The set of decoders from $`𝒮(𝒦)`$ to $`𝒮()`$ coincides with the convex hull of the subset

$`\left\{D\right|\begin{array}{c}\text{There exists a Hilbert space }^{}\text{ and}\hfill \\ \text{an isometry }T\text{ from }𝒮(𝒦)\text{ to }𝒮(^{})\hfill \\ \text{ such that }D(\rho )=Tr_{^{}}T(\rho ).\hfill \end{array}\}.`$ (32)
Proof:  From the Steinspring representation theorem, there exist a Hilbert space $`𝒦^{}`$ and a unitary $`U`$ on $`𝒦𝒦^{}`$ and an element $`\rho _0𝒮(𝒦^{})`$ such that

$`D(\rho )=Tr_{𝒦𝒦^{}}U\rho \rho _0U^{},\rho 𝒮(𝒦).`$
Assume that $`\rho _0=_js_j|\varphi _j\varphi _j|`$. Then, the decoder $`D_j`$:

$`D_j(\rho )=Tr_{𝒦𝒦^{}}U\rho |\varphi _j\varphi _j|U^{},\rho 𝒮(𝒦)`$
belongs to (32). Since $`D=_js_jD_j`$, the proof is complete.

For a proof of Lemma 4, an entanglement viewpoint plays a essential role. A state $`\rho 𝒮(_A_B)`$ is called separable if there exist states $`\rho _{A,i}𝒮(_A),\rho _{B,i}𝒮(_B)`$ and a probability $`p_i`$ such that

$`\rho ={\displaystyle \underset{i}{}}p_i\rho _{A,i}\rho _{B,i}.`$
The following lemma was proven from the viewpoint of entanglement by Nielsen and Kempe .

###### Lemma 7

When the state $`\rho 𝒮(_A_B)`$ is separable, the inequality

$`\mathrm{max}\{TrP\rho _A|P:\text{ projection on }_A,rankP=k\}`$
$``$ $`\mathrm{max}\{TrP\rho |P:\text{ projection on }_A_B,rankP=k\}`$
holds for any integer $`k`$, where $`\rho _A:=Tr__B\rho `$.

Proof of Lemma 4: From Lemma 5 and Lemma 6, it is sufficient to show the inequalities (25), (26) and (27) for the pair an encoder $`F`$ belonging to (28) and a decoder $`D`$ belonging to (32). Assume that the Hilbert space $`^{}`$ satisfies that $`D(\rho )=Tr_{^{}}T(\rho )`$. The state $`\rho _i^{}:=\frac{\rho _i𝐼T(F(i))\rho _i𝐼}{TrT(F(i))\rho _i𝐼}𝒮(^{})`$ is pure and satisfies that $`TrD(F(i))\rho _i=TrT(F(i))\rho _i𝐼=TrT(F(i))\rho _i^{}`$. Since $`Tr_{^{}}\rho _i^{}=\rho _i`$, there exists a pure state $`\sigma _i𝒮(^{})`$ such that $`\rho _i^{}=\rho _i\sigma _i`$. Since the state $`\overline{\rho }_p^{}:=_{i\mathrm{\Xi }}p_i\rho _i^{}=_{i\mathrm{\Xi }}p_i\rho _i\sigma _i`$ is separable and $`\overline{\rho }_p=Tr_{^{}}\overline{\rho }_p^{}`$, Lemma 7 guarantees that

$`\mathrm{max}\{TrP\overline{\rho }_p^{}|P:\text{ projection on }^{},rankP=dim𝒦\}`$
$``$ $`\mathrm{max}\{TrP\overline{\rho }_p|P:\text{ projection on },rankP=dim𝒦\}.`$ (33)
Since $`𝐼F(i)`$, we have $`T(𝐼)T(F(i))`$. The relations

$`{\displaystyle \underset{i\mathrm{\Xi }}{}}p_iTrD(F(i))\rho _i={\displaystyle \underset{i\mathrm{\Xi }}{}}p_iTrT(F(i))\rho _i^{}`$
$`{\displaystyle \underset{i\mathrm{\Xi }}{}}p_iTrT(𝐼)\rho _i^{}=TrT(𝐼)\overline{\rho }_p^{}`$ (34)
hold. The relations $`𝐼T(𝐼)0`$ and $`TrT(𝐼)=Tr𝐼_𝒦=dim𝒦`$ imply that

$`TrT(𝐼)\overline{\rho }_p^{}\mathrm{max}\{TrP\overline{\rho }_p^{}|\begin{array}{c}P:\text{ projection on }^{},\hfill \\ rankP=dim𝒦\hfill \end{array}\}.`$ (37)
Assume that $`P`$ is a projection on $``$ whose rank is $`dim𝒦`$, then

$`Tr(\overline{\rho }_pe^\lambda )PTr(\overline{\rho }_pe^\lambda )\{\overline{\rho }_pe^\lambda 0\}.`$
Thus, we obtain

$`Tr\overline{\rho }_pPe^\lambda dim𝒦+Tr\overline{\rho }_p\{\overline{\rho }_pe^\lambda 0\}.`$ (38)
From (33), (34), (37) and (38),

$`1ϵ(F,D)={\displaystyle \underset{i\mathrm{\Xi }}{}}p_iTrD(F(i))\rho _i`$
$``$ $`\mathrm{max}\{TrP\overline{\rho }_p^{}|P:\text{ projection on }^{},rankP=dim𝒦\}`$
$``$ $`\mathrm{max}\{TrP\overline{\rho }_p|P:\text{ projection on },rankP=dim𝒦\}`$
$``$ $`e^\lambda dim𝒦+Tr\overline{\rho }_p\{\overline{\rho }_pe^\lambda 0\}.`$
We obtain (26). Since $`Tr\overline{\rho }_p\{\overline{\rho }_pe^\lambda <0\}=1Tr\overline{\rho }_p\{\overline{\rho }_pe^\lambda 0\}`$, the inequalities (25) and (26) hold. Applying Markov inequality (90) given in Appendix E to the probability $`𝐚=\{a_i\}`$ and the random variable $`a_i^t`$, we obtain the inequality

$`Tr\overline{\rho }_p\{\overline{\rho }_pe^\lambda 0\}e^{t\lambda }Tr\overline{\rho }_{p}^{}{}_{}{}^{1+t}t0,`$
where $`a_1,\mathrm{},a_d`$ are eigenvalues of $`\overline{\rho }_p`$. Substituting $`1+t`$ for $`s`$, we obtain (27).

###### Remark 5

Assume that $`D`$ is not a CP map but a positive map. In this case, the inequality

$`1ϵ(F,D)2e^\lambda dim𝒦+2Tr\overline{\rho }_p\{\overline{\rho }_pe^\lambda 0\}`$ (39)
holds for $`\lambda `$ instead of (26). This inequality is proven in Appendix D.

## VI Proof of the converse part of Theorem 2

First, using Lemma 4, we prove inequality (12).

$`r_{e,V}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})\underset{0s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}.`$ (40)
Assume that a sequence of visible codes $`\{(𝒦_n,F_n,D_n)\}`$ satisfies that

$`\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}dim𝒦_nR.`$ (41)
It follows from (25) in Lemma 4 that

$`ϵ(F_n,D_n)Tr\overline{\rho }_p^n\{\overline{\rho }_p^ne^{nS}0\}e^{nS}dim𝒦_n.`$
When $`SR\eta (S):=\overline{\mathrm{lim}}\frac{1}{n}\mathrm{log}Tr\overline{\rho }_p^n\{\overline{\rho }_p^ne^{nS}0\}`$,

$`\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}ϵ(F_n,D_n)\eta (S).`$
Therefore, we have

$`\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}ϵ(F_n,D_n)`$ $`inf\{\eta (S)|SR\eta (S)\}`$
$`=inf\{\eta (S)|S\eta (S)R\}.`$
Now, applying (96) to the random variable $`\mathrm{log}a_i`$ under the probability distribution $`𝐚`$, we obtain

$`\begin{array}{ccc}\eta (S)\hfill & =(1s(S))\psi (s(S))\hfill & \text{ if }H(\rho )S\psi ^{}(0)\hfill \\ \eta (S)\hfill & \eta (\psi ^{}(0))\hfill & \text{ if }S>\psi ^{}(0)\hfill \\ \eta (S)\hfill & =0\hfill & \text{ if }S<H(\rho ),\hfill \end{array}`$
where the definition of $`s(S)`$ is given in Lemma 8 in Appendix A. When $`H(\rho )<S<\psi ^{}(0)`$,

$`{\displaystyle \frac{d\eta (S)}{dS}}`$ $`=1s(S)0`$
$`{\displaystyle \frac{d(SR\eta (S))}{dS}}`$ $`=s(S)0.`$
When $`H(\rho )<R<\mathrm{log}d=\psi (0)=\psi ^{}(0)\eta (\psi ^{}(0))`$, we obtain

$`inf\{\eta (S)|S\eta (S)R\}=\eta (S_R)=S_RR.`$
When $`0RH(\rho )`$, we obtain

$`inf\{\eta (S)|S\eta (S)R\}inf\{\eta (S)|SH(\rho )\}=0.`$
Using Lemma 9, we obtain (12).

Next, we prove (13). Assume that a sequence of visible codes $`\{(𝒦_n,F_n,D_n)\}`$ satisfies that

$`\overline{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}dim𝒦_nR.`$ (42)
When $`H(\rho )R`$, it is trivial that

$`\underset{¯}{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}(1ϵ(F_n,D_n))S_{H(\rho )}H(\rho )=0.`$
Lemma 9 implies (13).

Assume that $`a_1=a_k>a_{k+1}`$ and $`\mathrm{log}k<R<H(\rho )`$. Since $`\mathrm{log}Tr(\overline{\rho }_p^n)^s=n\psi (s)`$, substituting $`\lambda :=nS_R`$ and $`s:=s(S_R)1`$ into (27), we have

$`1ϵ(F_n,D_n)e^{n(S_RR)}+e^{n(S_R(1s(S_R))\psi (s(S_R)))}.`$ (43)
Note that the definitions of $`S_R,s(S)`$ are given in Lemma 8. Since $`S_RR=S_R(1s(S_R))\psi (s(S_R))`$, we have

$`\underset{¯}{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}(1ϵ(F_n,D_n))S_RR`$
$`={\displaystyle \frac{(1s(S_R))R+\psi (s(S_R))}{s(S_R)}},`$ (44)
where the last inequality follows from $`S_R=\frac{R+\psi (s(S_R))}{s(S_R)}`$ obtained from (47). From Lemma 9, we obtain (13).

Assume that $`0R\mathrm{log}k`$. Substituting $`\lambda :=n(\mathrm{log}a_1ϵ)`$ into (27), we have

$`1ϵ(F_n,D_n)`$
$``$ $`e^{n(\mathrm{log}a_1ϵR)}+e^{n((\mathrm{log}a_1ϵ)(1s)\psi (s))}`$ (45)
for $`ϵ>0`$ and $`s1`$. Since

$`\underset{s\mathrm{}}{lim}(\mathrm{log}a_1ϵ)(1s)\psi (s)`$
$`=`$ $`\underset{s\mathrm{}}{lim}ϵ(s1)\mathrm{log}{\displaystyle \frac{ka_1^s}{_{i=1}^da_i^s}}\mathrm{log}a_1+\mathrm{log}k=\mathrm{},`$
we have

$`\underset{¯}{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}(1ϵ(F_n,D_n))\mathrm{log}a_1ϵR.`$
Arbitrarity of $`ϵ>0`$ implies

$`\underset{¯}{\mathrm{lim}}{\displaystyle \frac{1}{n}}\mathrm{log}(1ϵ(F_n,D_n))\mathrm{log}a_1R.`$
Lemma 9 implies (13).

## VII Discussion

When the source $`\rho _i`$ is mixed and has no trivial redundancies, Koashi and Imoto  proved that the bound $`R_B`$ equals $`H(\rho )`$ in the blind case. Lemma 3 holds for the mixed case. However, its optimality is not proven in the sense of exponents in the mixed case. In this case it may not be optimal.

It is interesting that our exponent corresponds to the exponents of the variable-length universal entanglement concentration given by Hayashi and Matsumoto and the fixed-length entanglement concentration given by Hayashi et. al.. However, our error exponent corresponds to the success exponent of , and our fidelity exponent corresponds to the failure exponents of  and . Note that in  the optimal exponent $`r`$ is given as the function of the rate $`R`$ while in this paper and , the rate $`R`$ is given as a function the optimal exponent $`r`$. In addition, in quantum hypothesis testing, an error exponent similar to (2) is given in Ogawa and Hayashi.

## Acknowledgment

The author is grateful to Dr. A. Winter for advice on Nielsen and Kempe’s paper . He acknowledges stimulating discussions with Professor H. Nagaoka, Professor K. Matsumoto and Dr. T. Ogawa. He, also, thanks an anonymous referee for useful comments.

## Appendix A Equivalence between different characterizations

In the classical case, the exponent has two forms . Following Ogawa and Nagaoka , we prove this equivalence in the quantum source coding case. In this section we treat a state $`\rho :=_ia_i|e_ie_i|`$, and the function $`\psi (s):=\mathrm{log}Tr\rho ^s`$, where $`a_ia_{i+1}`$. We assume that $`a_1=a_k>a_{k+1}`$ and $`d=dim`$.

###### Lemma 8

If $`\mathrm{log}a_1<S\psi ^{}(0)`$ and $`\mathrm{log}k<R<\mathrm{log}d`$, we can uniquely define $`s(S)0`$ and $`S_R`$ such that

$`S`$ $`=\psi ^{}(s(S)),`$ (46)
$`R`$ $`=s(S_R)S_R+\psi (s(S_R)).`$ (47)
Conversely, when $`R\mathrm{log}k`$,

$`R<s\psi ^{}(s)+\psi (s).`$ (48)
Proof:  Since

$`\psi ^{\prime \prime }(s)={\displaystyle \frac{Tr(\mathrm{log}\rho )^2\rho ^sTr\rho ^s\left(Tr(\mathrm{log}\rho )\rho ^s\right)^2}{\left(Tr\rho ^s\right)^2}}>0`$ (49)
for $`s>0`$, the function $`\psi ^{}(s)`$ is monotone decreasing. Because $`lim_s\mathrm{}\psi ^{}(s)=\mathrm{log}a_1`$, $`s(S)`$ is uniquely defined in $`(\mathrm{log}a_1,\psi ^{}(0)]`$.

When $`S(\mathrm{log}a_1,\psi ^{}(0)]`$, we can calculate

$`{\displaystyle \frac{d}{dS}}s(S)S+\psi (s(S))=s(S)>0.`$
As shown latter, the equation

$`\underset{s\mathrm{}}{lim}\psi ^{}(s)s+\psi (s)=\mathrm{log}k.`$ (50)
holds. Since

$`\psi ^{}(0)0+\psi (0)=\psi (0)=d,`$
$`S_R`$ also is uniquely defined. The inequality $`\frac{d}{ds}(s\psi ^{}(s)+\psi (s))=s\psi ^{\prime \prime }(s)0`$ yields (48).

Finally, we show (50). We calculate as

$`\psi ^{}(s)s+\psi (s)={\displaystyle \underset{i=1}{\overset{d}{}}}s\mathrm{log}a_i{\displaystyle \frac{a_i^s}{_{j=1}^da_j^s}}+\mathrm{log}{\displaystyle \underset{i=1}{\overset{d}{}}}a_i^s`$
$`=`$ $`{\displaystyle \underset{i=k+1}{\overset{d}{}}}s{\displaystyle \frac{a_i^s}{_{j=1}^da_j^s}}\mathrm{log}a_i+\mathrm{log}{\displaystyle \underset{j=1}{\overset{d}{}}}a_j^s\mathrm{log}ka_1^s`$
$`+\left(ks{\displaystyle \frac{a_1^s}{_{j=1}^da_j^s}}\mathrm{log}a_1+s\mathrm{log}a_1\right)+\mathrm{log}k`$
$`=`$ $`{\displaystyle \underset{i=k+1}{\overset{d}{}}}s{\displaystyle \frac{a_i^s}{_{j=1}^da_j^s}}\mathrm{log}a_i+\mathrm{log}{\displaystyle \frac{_{j=1}^da_j^s}{ka_1^s}}`$
$`+s{\displaystyle \frac{_{i=k+1}^da_i^s}{_{j=1}^da_j^s}}\mathrm{log}a_1+\mathrm{log}k.`$
The terms $`\frac{a_i^s}{_{j=1}^da_j^s}`$ and $`\frac{_{i=k+1}^da_i^s}{_{j=1}^da_j^s}`$ exponentially go to $`0`$ as $`s\mathrm{}`$. The term $`\frac{_{j=1}^da_j^s}{ka_1^s}`$ goes to $`1`$. Thus, we obtain (50).

###### Lemma 9

When $`\mathrm{log}k<R<\mathrm{log}d`$, the equations

$`S_RR`$ $`=S_R(1s(S_R))\psi (s(S_R))`$ (51)
$`={\displaystyle \frac{(1s(S_R))R\psi (s(S_R))}{s(S_R)}}`$ (52)
$`=\underset{H(𝐛)=R}{\mathrm{min}}D(𝐛𝐚)=\underset{H(\sigma )=R}{\mathrm{min}}D(\sigma \rho )`$ (53)
hold, where $`\sigma `$ is a state on $``$ and $`𝐛`$ is a probability on $`\{1,\mathrm{},d\}`$. When $`0R\mathrm{log}k`$, the equations

$`\underset{H(𝐛)=R}{\mathrm{min}}D(𝐛𝐚)=\underset{H(\sigma )=R}{\mathrm{min}}D(\sigma \rho )=\mathrm{log}a_1R.`$ (54)
hold. When $`H(\rho )<R<\mathrm{log}d`$,

$`S_RR`$ $`=\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚)=\underset{H(\sigma )R}{\mathrm{min}}D(\sigma \rho )`$ (55)
$`=\underset{0<s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ (56)
$`0`$ $`=\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚)=\underset{H(\sigma )R}{\mathrm{min}}D(\sigma \rho )`$ (57)
$`=\underset{s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}.`$ (58)
When $`\mathrm{log}k<R<H(\rho )`$,

$`0`$ $`=\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚)=\underset{H(\sigma )R}{\mathrm{min}}D(\sigma \rho )`$ (59)
$`=\underset{0<s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ (60)
$`S_RR`$ $`=\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚)=\underset{H(\sigma )R}{\mathrm{min}}D(\sigma \rho )`$ (61)
$`=\underset{s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}.`$ (62)
When $`0R\mathrm{log}k`$,

$`0`$ $`=\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚)=\underset{H(\sigma )R}{\mathrm{min}}D(\sigma \rho )`$ (63)
$`=\underset{0<s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ (64)
$`\mathrm{log}a_1R`$ $`=\underset{H(𝐛)R}{\mathrm{min}}D(𝐛𝐚)=\underset{H(\sigma )R}{\mathrm{min}}D(\sigma \rho )`$ (65)
$`=\underset{s1}{sup}{\displaystyle \frac{(1s)R\psi (s)}{s}}.`$ (66)
Proof:  Equation (51) follows from (47). Equation (47) yields

$`S_R={\displaystyle \frac{R\psi (s(S_R))}{s(S_R)}}.`$
Substituting the above equation into $`S_RR`$, we obtain (52). We prove (53). Assume that $`\mathrm{log}k<R<\mathrm{log}d`$. Letting $`\rho _s:=\frac{\rho ^s}{Tr\rho ^s}`$, we calculate

$`D(\sigma \rho )D(\rho _s\rho )`$
$`=`$ $`Tr\sigma (\mathrm{log}\sigma \mathrm{log}\rho )Tr{\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\left(\mathrm{log}\left({\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\right)\mathrm{log}\rho \right)`$
$`=`$ $`Tr\sigma \left(\mathrm{log}\sigma \mathrm{log}\left({\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\right)\right)`$
$`+Tr\left(\sigma \left({\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\right)\right)\left(\mathrm{log}\left({\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\right)\mathrm{log}\rho \right)`$
$`=`$ $`D(\sigma \rho _s)(1s)Tr\left(\sigma \left({\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\right)\right)\mathrm{log}\rho `$
$`H(\sigma )+H(\rho _s)`$
$`=`$ $`Tr\sigma \left(\mathrm{log}\sigma \mathrm{log}\left({\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\right)\right)`$
$`+Tr\left(\sigma \left({\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\right)\right)\mathrm{log}\left({\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\right)`$
$`=`$ $`D(\sigma \rho _s)+sTr\left(\sigma \left({\displaystyle \frac{\rho ^s}{Tr\rho ^s}}\right)\right)\mathrm{log}\rho .`$
Equation (47) guarantees that $`H(\rho _{s(S_R)})=R.`$ Assuming that $`H(\sigma )=R`$, we have

$`{\displaystyle \frac{D(\sigma \rho _{s(S_R)})}{s(S_R)}}=Tr\left(\sigma \rho _{s(S_R)}\right)\mathrm{log}\rho `$
$`=`$ $`{\displaystyle \frac{1}{1s(S_R)}}\left(D(\sigma \rho )D(\rho _{s(S_R)}\rho )D(\sigma \rho _{s(S_R)})\right)`$
i.e.,

$`D(\sigma \rho )D(\rho _{s(S_R)}\rho )={\displaystyle \frac{1}{s(S_R)}}D(\sigma \rho _{s(S_R)})0.`$
It implies that

$`D(\rho _{s(S_R)}\rho )=\underset{H(\sigma )=R}{\mathrm{min}}D(\sigma \rho )=\underset{H(𝐛)=R}{\mathrm{min}}D(𝐛𝐚).`$
Note that $`\rho _s`$ is commutative with $`\rho `$. Equation (47) yields

$`D(\rho _{s(S_R)}\rho )=`$ $`\psi ^{}(s(S_R))(1s(S_R))\psi (s(S_R))`$
$`=`$ $`S_R(1s(S_R))\psi (s(S_R)).`$
Then, we obtain (53).

Next, we proceed (54) and assume that $`0R\mathrm{log}k`$. When $`H(\sigma )=R`$,

$`D(\sigma \rho )=Tr\sigma \mathrm{log}\sigma +Tr\sigma (\mathrm{log}\rho )`$
$``$ $`H(\sigma )+Tr\sigma (\mathrm{log}a_1)=\mathrm{log}a_1R.`$
Let $`𝐜:=\{c_i\}_{i=1}^k`$ be a probability whose entropy is $`R`$. Then we have

$`D\left({\displaystyle \underset{i=1}{\overset{k}{}}}c_i|e_ie_i|\rho \right)`$ $`={\displaystyle \underset{i=1}{\overset{k}{}}}c_i(\mathrm{log}c_i\mathrm{log}a_1)`$
$`=\mathrm{log}a_1R.`$
Thus, we obtain (54), which implies (65).

Taking the derivative with respect to $`R`$ in (47), we have

$`{\displaystyle \frac{d}{dR}}s(S_R)={\displaystyle \frac{1}{s(S_R)\psi ^{\prime \prime }(s(S_R))}}<0.`$ (67)
From (46), we have

$`{\displaystyle \frac{d}{dR}}(S_RR)`$ $`=\psi ^{\prime \prime }(s(S_R)){\displaystyle \frac{d}{dR}}s(S_R)1={\displaystyle \frac{1s(S_R)}{s(S_R)}}.`$
$`{\displaystyle \frac{d}{dR}}(S_RR)`$ $`={\displaystyle \frac{1}{s^3(S_R)}}\psi ^{\prime \prime }(s(S_R))>0.`$
Thus, the function $`RS_RR`$ is convex, and $`\frac{d}{dR}(S_RR)=0`$ if and only if $`s(S_R)=1`$, i.e. $`R=H(\rho )`$. The function takes minimum value $`0`$ at $`R=H(\rho )`$ because $`S_{H(\rho )}H(\rho )=0`$. Therefore, we obtain (55), (57), (59), (61), and (63).

Next, we discuss the other forms described by $`\psi `$. We can calculate the derivatives as

$`{\displaystyle \frac{d}{ds}}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ $`={\displaystyle \frac{Rs\psi ^{}(s)+\psi (s)}{s^2}}`$ (68)
$`{\displaystyle \frac{d}{ds}}(Rs\psi ^{}(s)+\psi (s))`$ $`=s\psi ^{\prime \prime }(s)0,`$ (69)
where the last inequality follows from (49). In (69) and (49), the equalities hold if and only if $`s=0`$.

Assume $`\mathrm{log}k<R<\mathrm{log}d`$. Since it follows from (46) and (47) that

$`Rs(S_R)\psi ^{}(s(S_R))+\psi (s(S_R))=0,`$ (70)
the equation

$`\underset{s>0}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}={\displaystyle \frac{(1s(S_R))R+\psi (s(S_R))}{s(S_R)}}`$
holds. Relation (67) implies that the function $`Rs(S_R)`$ strictly monotonically decreases, and $`s(S_R)1`$ if and only if $`RH(\rho )`$. Therefore,

$`\underset{0<s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$
$`=`$ $`\{\begin{array}{cc}\frac{(1s(S_R))R+\psi (s(S_R))}{s(S_R)}\hfill & \text{ if }H(\rho )<R<\mathrm{log}d\hfill \\ 0\hfill & \text{ if }\mathrm{log}k<RH(\rho )\hfill \end{array}`$
$`\underset{s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$
$`=`$ $`\{\begin{array}{cc}0\hfill & \text{ if }H(\rho )<R<\mathrm{log}d\hfill \\ \frac{(1s(S_R))R+\psi (s(S_R))}{s(S_R)}\hfill & \text{ if }\mathrm{log}k<RH(\rho )\hfill \end{array}`$
Note that $`\frac{(11)R\psi (1)}{1}=0`$. We obtain (56), (58), (60) and (62).

When $`0R\mathrm{log}k`$, Lemma 8 guarantees that the RHS of (68) is positive for any $`s>0`$. Thus,

$`\underset{s>0}{sup}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ $`=\underset{s\mathrm{}}{lim}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$
$`=\mathrm{log}a_1R,`$
which implies

$`\underset{0<s1}{\mathrm{max}}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ $`=0`$
$`\underset{s1}{sup}{\displaystyle \frac{(1s)R\psi (s)}{s}}`$ $`=\mathrm{log}a_1R.`$
We obtain (60) and (66).

## Appendix B Representation theoretical type methods

In this section, we prove the following two lemmas used in our proof of Lemma 3. We assume that $`\rho =_{i=1}^da_i|e_ie_i|`$ and $`d`$ is the dimension of $``$.

###### Lemma 10

The relations

$`\mathrm{exp}\left(nH\left({\displaystyle \frac{𝐧}{n}}\right)\right)(n+d)^{\frac{d(d+1)}{2}}`$
$``$ $`dim𝒱_𝐧`$ (71)
$``$ $`(n+d)^{2d}\mathrm{exp}\left(nH\left({\displaystyle \frac{𝐧}{n}}\right)\right)`$ (72)
$`\mathrm{\#}\{𝐧|𝐧Y_n\}`$ $`(n+1)^d`$ (73)
$`dim𝒰_𝐧`$ $`(n+1)^d`$ (74)
hold, where $`C(𝐧)`$ is defined as

$`C(𝐧):={\displaystyle \frac{n!}{n_1!n_2!\mathrm{}n_d!}}.`$
Proof:  Inequality (73) is trivial. Using Young index $`𝐧`$, the basis of $`𝒰_𝐧`$ is described by $`\{e_𝐧^{}\}_{𝐧^{}Y^𝐧}`$, where the set $`Y^𝐧`$ is defined as

$`Y^𝐧:=\{𝐧^{}=\{n_i^{}\}^d|\begin{array}{c}_in_i^{}=_in_i,\hfill \\ _{i=1}^mn_{s(i)}^{}_{i=1}^mn_i,\hfill \\ 1md1,\hfill \\ s\text{ is any permutation}\hfill \end{array}\}.`$
Thus, we obtain (74). Note that the correspondence $`𝐧^{}`$ and $`e_𝐧^{}`$ depends on the choice of Cartan subalgebra, i.e. the choice of basis of $``$.

According to Weyl , and Iwahori , the following equation holds and is evaluated as:

$`dim𝒱_𝐧`$
$`=`$ $`{\displaystyle \frac{n!}{(n_1+d1)!(n_2+d2)!\mathrm{}n_d!}}{\displaystyle \underset{j>i}{}}(n_in_ji+j)`$
$``$ $`{\displaystyle \frac{n!}{n_1!n_2!\mathrm{}n_d!}}{\displaystyle \underset{j>i}{}}(n_in_ji+j)`$
$``$ $`C(𝐧)(n+d)^{2d}`$ (75)
$``$ $`(n+d)^{2d}\mathrm{exp}\left(nH\left({\displaystyle \frac{𝐧}{n}}\right)\right).`$
Thus, we obtain (72). As an opposite inequality, we have

$`dim𝒱_𝐧`$
$``$ $`{\displaystyle \frac{n!}{(n_1+d1)!(n_2+d2)!\mathrm{}n_d!}}`$
$``$ $`{\displaystyle \frac{n!}{n_1!n_2!\mathrm{}n_d!}}\left({\displaystyle \frac{1}{n+d}}\right)^{d1}\left({\displaystyle \frac{1}{n+d}}\right)^{d2}\mathrm{}\left({\displaystyle \frac{1}{n+d}}\right)^0`$
$`=`$ $`C(𝐧)\left({\displaystyle \frac{1}{n+d}}\right)^{\frac{d(d1)}{2}}\mathrm{exp}\left(nH\left({\displaystyle \frac{𝐧}{n}}\right)\right)(n+d)^{\frac{d(d+1)}{2}},`$
where the last inequality follows from

$`C(𝐧){\displaystyle \frac{1}{(n+1)^d}}\mathrm{exp}\left(nH\left({\displaystyle \frac{𝐧}{n}}\right)\right),`$
which is easily proven by the type method . We obtain (71).

The following is essentially equivalent to Keyl and Werner’s result . For the reader’s convenience, we give a simpler proof.

###### Lemma 11

The following relations

$`(n+d)^{\frac{d(d+1)}{2}}\mathrm{exp}\left(nD\left({\displaystyle \frac{𝐧}{n}}𝐚\right)\right)`$
$``$ $`TrP_𝐧\rho ^n`$ (76)
$``$ $`(n+d)^{3d}\mathrm{exp}\left(nD\left({\displaystyle \frac{𝐧}{n}}𝐚\right)\right)`$ (77)
$`(n+d)^{\frac{d(d+1)}{2}}\mathrm{exp}\left(n\underset{𝐧nY_n}{\mathrm{min}}D\left({\displaystyle \frac{𝐧}{n}}𝐚\right)\right)`$
$``$ $`{\displaystyle \underset{\frac{𝐧}{n}}{}}TrP_𝐧\rho ^n`$ (78)
$``$ $`(n+d)^{4d}\mathrm{exp}\left(n\underset{𝐛}{inf}D(𝐛𝐚)\right),`$ (79)
hold, where $``$ is a subset consisting of probabilities on $`\{1,\mathrm{},d\}`$ and we denote the projection to $`𝒲_𝐧`$ by $`P_𝐧`$.

Proof:  Let $`𝒰_𝐧^{}`$ be an irreducible representation of $`SU(d)`$ in $`^n`$, which is equivalent to $`𝒰_𝐧`$. We denote its projection by $`P_𝐧^{}`$. Now, we choose the basis $`\{e_𝐧^{}\}_{𝐧^{}Y^𝐧}`$ of $`𝒰_𝐧^{}`$ depending the basis $`\{e_i\}`$ of $``$. The base $`e_𝐧^{}`$ is the eigenvector of $`\rho ^n`$ with the eigenvalue $`_{i=1}^da_i^{n_i^{}}`$. Since $`𝐧^{}`$ is majorized by $`𝐧`$, we can calculate the operator norm by

$`P_𝐧^{}\rho ^nP_𝐧^{}={\displaystyle \underset{i=1}{\overset{d}{}}}a_i^{n_i},`$ (80)
where $`X:=sup_xXx`$. from (74), (75) and (80), the relations

$`TrP_𝐧\rho ^n`$ $`=dim𝒱_𝐧\times TrP_𝐧^{}\rho ^n(n+d)^{3d}C(𝐧){\displaystyle \underset{i=1}{\overset{d}{}}}a_i^{n_i}`$
$`=(n+d)^{3d}\mathrm{Mul}(𝐚,𝐧)`$
hold, where we denote the multinomial distribution of $`𝐚`$ by $`\mathrm{Mul}(𝐚,)`$. Inequality (73) guarantees

$`{\displaystyle \frac{1}{(n+1)^d}}\mathrm{exp}\left(nD\left({\displaystyle \frac{𝐧}{n}}𝐚\right)\right)`$ $`\mathrm{Mul}(𝐚,𝐧)`$
$`\mathrm{exp}\left(nD\left({\displaystyle \frac{𝐧}{n}}𝐚\right)\right).`$
Thus, we obtain inequality (77). Inequality (73) guarantees that

$`{\displaystyle \underset{𝐧nY_n}{}}TrP_𝐧\rho ^n(n+d)^{4d}\mathrm{exp}\left(n\underset{𝐛}{inf}D(𝐛𝐚)\right),`$
which implies inequality (79). From (80), we have

$`TrP_𝐧\rho ^n=dim𝒱_𝐧TrP_𝐧^{}\rho ^n`$
$``$ $`\mathrm{exp}\left(nH\left({\displaystyle \frac{𝐧}{n}}\right)\right)(n+d)^{\frac{d(d+1)}{2}}{\displaystyle \underset{i=1}{\overset{d}{}}}a_i^{n_i}`$
$`=`$ $`(n+d)^{\frac{d(d+1)}{2}}\mathrm{exp}\left(nD\left({\displaystyle \frac{𝐧}{n}}𝐚\right)\right).`$
Therefore, we obtain inequalities (76) and (78).

## Appendix C Proof of (14), (15), (16) and (17)

Since

$`ϵ(F,D)`$ $`={\displaystyle \underset{i\mathrm{\Xi }}{}}p_i(1TrDF(i)\rho _i)`$
$`{\displaystyle \underset{i\mathrm{\Xi }}{}}p_i(1\sqrt{TrDF(i)\rho _i})=ϵ_b(F,D),`$
the inequalities

$`r_{e,V,b}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`r_{e,V}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ (81)
$`r_{e,V}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`r_{e,V,b}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
hold. Similarly, we can prove that

$`r_{e,B,b}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`r_{e,B}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$
$`r_{e,B}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }})`$ $`r_{e,B,b}^{}(R|\{\rho _i,p_i\}_{i\mathrm{\Xi }}).`$
Using Jensen’s inequality, we have

$`ϵ(F_n,D_n)`$ $`={\displaystyle \underset{i\mathrm{\Xi }}{}}p_i(1TrD_nF_n(i)\rho _i)`$
$`1\left({\displaystyle \underset{i\mathrm{\Xi }}{}}p_i\sqrt{TrD_nF_n(i)\rho _i}\right)^2`$
$`=1\left(1ϵ_b(F_n,D_n)\right)^22ϵ_b(F_n,D_n)`$
Thus, we obtain the opposite inequality from (81) and then obtain (15). Similarly, we can prove (14).

## Appendix D Proof of (39)

For any visible code $`(𝒦,F,D)`$, we define an operator $`T`$ by $`T:=\{D(𝐼)10\}D(𝐼)\{D(𝐼)10\}+\{D(𝐼)1>0\}`$. The operator inequality

$`P\rho P+(𝐼P)\rho (𝐼P){\displaystyle \frac{1}{2}}\rho `$ (82)
holds for any projection $`P`$. It is sufficient for (82) to show the pure state case. The pure state case of (82) is directly proven using the inequality $`2(|x|^2+|y|^2)|x+y|^2`$ for any two complex numbers $`x,y`$. Therefore,

$`\{D(𝐼)10\}D(F(i))\{D(𝐼)10\}`$
$`+\{D(𝐼)1>0\}D(F(i))\{D(𝐼)1>0\}`$
$``$ $`{\displaystyle \frac{1}{2}}D(F(i)).`$ (83)
The inequality $`D(𝐼)D(F(i))`$ follows from the inequality $`𝐼F(i)`$. Thus,

$`\{D(𝐼)10\}D(I)\{D(𝐼)10\}`$
$``$ $`\{D(𝐼)10\}D(F(i))\{D(𝐼)10\}.`$ (84)
From the relations $`TrD(F(i))=1`$ and $`D(F(i))0`$, we can prove

$`\{D(𝐼)1>0\}`$
$``$ $`\{D(𝐼)1>0\}D(F(i))\{D(𝐼)1>0\}.`$ (85)
It follows from (84) and (85) that

$`\{D(𝐼)10\}D(𝐼)\{D(𝐼)10\}+\{D(𝐼)1>0\}`$
$``$ $`\{D(𝐼)10\}D(F(i))\{D(𝐼)10\}`$
$`+\{D(𝐼)1>0\}D(F(i))\{D(𝐼)1>0\}.`$ (86)
From (86) and (83), we have

$`T{\displaystyle \frac{1}{2}}D(F(i)).`$ (87)
Note that

$`TrTTrD(𝐼)=dim𝒦.`$ (88)
Since $`𝐼T0`$, we have

$`Tr(\rho e^\lambda )TTr(\rho e^\lambda )\{\rho e^\lambda 0\}`$
$``$ $`Tr\rho \{\rho e^\lambda 0\}.`$ (89)
From (87), (88) and (89), we obtain (26).

## Appendix E Markov inequality and Cramér’s Theorem

In this section, we summarize Markov inequality and Cramér’s Theorem which are applied in this paper. Let $`p`$ be a probability distribution and $`X`$ be a positive real valued random variable. For any real number $`c>0`$, we can easily prove the inequality

$`{\displaystyle \frac{E_p(X)}{c}}p\{Xc\},`$ (90)
where $`E_p`$ presents the expectation under the distribution $`p`$. This inequality is called Markov inequality.

This inequality can be used for large deviation evaluation as follows. Let $`Y`$ be a real valued random variable. In the $`n`$-i.i.d. setting, we focus on the random variable.

$`Y^n:={\displaystyle \underset{i=1}{\overset{n}{}}}{\displaystyle \frac{Y_i}{n}},`$
where $`Y_i`$ is the $`i`$-th random variable identical to $`Y`$. Applying Markov inequality for the random variable $`e^{tY^n}`$, we have

$`p^n\{Y^nx\}=p^n\{e^{ntY^n}e^{ntx}\}{\displaystyle \frac{e^{n\varphi (t)}}{e^{tx}}}`$
for $`t0`$, which is equivalent to

$`{\displaystyle \frac{1}{n}}\mathrm{log}p^n\{Y^nx\}tx\varphi (t),`$
where $`\varphi (t):=\mathrm{log}E_P(\mathrm{exp}(tY))`$. Therefore,

$`{\displaystyle \frac{1}{n}}\mathrm{log}p^n\{Y^nx\}\underset{t0}{sup}(tx\varphi (t)).`$ (91)
Conversely, the inequality

$`lim{\displaystyle \frac{1}{n}}\mathrm{log}p^n\{Y^n>x\}\underset{x^{}>x}{inf}I(x)`$ (92)
holds, where $`I(x):=sup_t(tx\varphi (t))`$. For a proof of (92), see Chapter II of Bucklew. The pair of (91) and (92) is called Cramér’s Theorem.

In the following, we discuss the case $`\varphi (t)`$ is convex and differentiable. We define three real numbers $`x_1,x_2`$ and $`x_3`$ as

$`x_1:=\underset{t\mathrm{}}{lim}\varphi ^{}(t),x_2:=\underset{t\mathrm{}}{lim}\varphi ^{}(t),x_3:=\varphi ^{}(0).`$
For any $`x(x_2,x_1)`$, we can uniquely define $`t(x)`$ as

$`x=\varphi ^{}(t(x)).`$
Then,

$`I(x)`$ $`=xt(x)\varphi (t(x)),I^{}(x)=t(x),`$
$`I^{\prime \prime }(x)`$ $`=t^{}(x)={\displaystyle \frac{1}{\varphi ^{\prime \prime }(t(x))}},`$
where the last equation follows from

$`1={\displaystyle \frac{dx}{dx}}=t^{}(x)\varphi ^{\prime \prime }(t(x)).`$
Thus, we obtain

$`\underset{n\mathrm{}}{lim}{\displaystyle \frac{1}{n}}\mathrm{log}p^n\{Y_nx\}`$
$`=`$ $`\{\begin{array}{cc}xt(x)\varphi (t(x))\hfill & \text{ if }x_3xx_1\hfill \\ +\mathrm{}\hfill & \text{ if }x>x_1\hfill \\ \varphi (0)=0\hfill & \text{ if }x<x_3\hfill \end{array}`$ (96)
except for $`x=x_1`$.