1 Introduction↩︎

A fundamental bottleneck that often arises in quantum information theory is about calculating the probability of the intersection of two events. Understanding this bottleneck will help us to understand many quantum network information theory problems in the one-shot setting, e.g., entanglement-assisted multiple access channel [1], entanglement-assisted broadcast channel with common message in the one-shot setting [2]–[5]. Recently, the broadcast channel with a common message was studied for the case of a classical-quantum channel in [6]. For details on one-shot setting see for example, [7], [8], [9], and references therein. Sen also studied this problem from the point of view of communication over classical quantum multiple access channel [3], where he was able to resolve the intersection issue with respect to classical quantum states and their respective marginals.

In the classical setting, when we calculate the probability of events under a particular probability distribution, it translates to the measurement of quantum states in a quantum setting. These measurements are in general POVM. However, because of the Gelfand-Naimark’s lemma [10] it is enough to consider only projective measurements. Therefore, in this manuscript, we will only consider projective measurements.

To understand the intersection issue in the quantum case, consider the following statement about classical probability distributions. Let \(P,\) \(Q_1\) and \(Q_2\) be probability distributions over a set \(\mathcal{X}\) such that \(supp(P) \subseteq supp(Q_1)\) and \(supp(P) \subseteq supp(Q_2).\) Further, for \({k_1}, k_2 >0,\) let \(\mathcal{A}_1:=\{x: Q_1(x) \leq 2^{-{k_1}}P (x)\}\) and \(\mathcal{A}_2:=\{x: Q_2(x) \leq 2^{-{k_2}}P (x)\}\) with the property that \(\Pr_P\{\mathcal{A}_1\} \geq 1-\varepsilon\) and \(\Pr_P \{\mathcal{A}_2\} \geq 1- \varepsilon.\) Then, it is easy to see that for \(\mathcal{A}^\star:= \mathcal{A}_1 \cap \mathcal{A}_2\), we have \(\Pr_P\{\mathcal{A}^\star\} \geq 1-2\varepsilon,\) \(\Pr_{Q_1}\{\mathcal{A}^\star\} \leq 2^{-{k_1}}\) and \(\Pr_{Q_2}\{\mathcal{A}^\star\} \leq 2^{-{k_2}},\) where \(\Pr_P\{\mathcal{A}^\star\} \geq 1-2\varepsilon,\) follows from the union bound for probability and the other two inequalities follows from the fact that \(\mathcal{A}^\star \subseteq\mathcal{A}_1\) and \(\mathcal{A}^\star \subseteq \mathcal{A}_2.\) We aim to prove a similar statement in the quantum setting. To define the problem formally let us consider \(\rho, \sigma_1\) and \(\sigma_2 \in \mathcal{D}(\mathcal{H})\) such that \(supp(\rho) \subseteq supp(\sigma_1)\) and \(supp(\rho) \subseteq supp(\sigma_2)\). Further, for \({k_1}, k_2 >0,\) let \(\Pi_1, \Pi_2\) be such that \(\Pi_1:=\{\sigma_1 \preceq 2^{-{k_1}}\rho\}\) and \(\Pi_2:=\{\sigma_2 \preceq 2^{-{k_2}}\rho\}\) (see Section 2 for the definition of \(\{\cdot \preceq \cdot \}\)) with the property that \(\mathrm{Tr}[\Pi_1 \rho] \geq 1-\varepsilon\) and \(\mathrm{Tr}[\Pi_2\rho] \geq 1- \varepsilon.\) Then, we want to find a projector \(\Pi^\star\) such that \(\mathrm{Tr}[\Pi^{\star}\rho] \geq 1- f(\varepsilon),\) \(\mathrm{Tr}[\Pi^{\star}\sigma_1] \leq 2^{-{k_1}}\) and \(\mathrm{Tr}[\Pi^{\star}\sigma_2] \leq 2^{-{k_2}},\) where \(f(\varepsilon)\) is some polynomial in \(\varepsilon\) (in the classical case it is \((1-2\varepsilon)\)).

We can also have a complementary version of the problem discussed above. Let \(P,\) \(Q_1\) and \(Q_2\) be probability distributions over a set \(\mathcal{X}\) such that \(supp(P) \subseteq supp(Q_1)\) and \(supp(P) \subseteq supp(Q_2).\) Further, for \(k_1,k_2 >0,\) let \(\mathcal{A}_1:=\{x: Q_1(x) \geq 2^{-{k_1}}P (x)\}\) and \(\mathcal{A}_2:=\{x: Q_2(x) \geq 2^{-{k_2}}P (x)\}\) with the property that \(\Pr_P\{\mathcal{A}_1\} \geq 1-\varepsilon\) and \(\Pr_P \{\mathcal{A}_2\} \geq 1- \varepsilon.\) Then, it is easy to see that for \(\mathcal{A}^\star:= \mathcal{A}_1 \cap \mathcal{A}_2\), we have \(\Pr_P\{\mathcal{A}^\star\} \geq 1-2\varepsilon,\) \(\Pr_{Q_1}\{\mathcal{A}^\star\} \geq 2^{-{k_1}} (1-2\varepsilon)\) and \(\Pr_{Q_2}\{\mathcal{A}^\star\} \geq 2^{-{k_2}} (1-2\varepsilon),\) where \(\Pr_P\{\mathcal{A}^\star\} \geq 1-2\varepsilon,\) follows from the union bound for probability and the other two inequalities follows from the fact that \(\mathcal{A}^\star \subseteq\mathcal{A}_1\) and \(\mathcal{A}^\star \subseteq \mathcal{A}_2.\) We aim to prove a similar statement in the quantum setting. To define the problem formally let us consider \(\rho, \sigma_1\) and \(\sigma_2 \in \mathcal{D}(\mathcal{H})\) such that \(supp(\rho) \subseteq supp(\sigma_1)\) and \(supp(\rho) \subseteq supp(\sigma_2)\). Further, for \(k_1, k_2 >0,\) let \(\Pi_1, \Pi_2\) be such that \(\Pi_1:=\{\sigma_1 \succeq 2^{-{k_1}}\rho\}\) and \(\Pi_2:=\{\sigma_2 \succeq 2^{-{k_2}}\rho\}\) with the property that \(\mathrm{Tr}[\Pi_1 \rho] \geq 1-\varepsilon\) and \(\mathrm{Tr}[\Pi_2\rho] \geq 1- \varepsilon.\) Then, we want to find a projector \(\Pi^\star\) such that \(\mathrm{Tr}[\Pi^{\star}\rho] \geq 1- f(\varepsilon),\) \(\mathrm{Tr}[\Pi^{\star}\sigma_1] \geq 2^{-{k_1}}f(\varepsilon)\) and \(\mathrm{Tr}[\Pi^{\star}\sigma_2] \geq 2^{-{k_2}}f(\varepsilon),\) where \(f(\varepsilon)\) is some polynomial in \(\varepsilon\) (in the classical case it is\((1-2\varepsilon)\)).

We can have a more general version of the problem discussed above. Consider two finite collections of distributions \(\mathcal{S}_1:=\{P_i\}_{i=1}^{|\mathcal{S}_1|}\) and \(\mathcal{S}_2:=\{Q_j\}_{j=1}^{|\mathcal{S}_2|},\) defined over a set \(\mathcal{X}.\) Further, \(\forall i \in \mathcal{S}_1\) and \(\forall j \in \mathcal{S}_2,\) we are given a set \(\mathcal{A}_{ij} \subset \mathcal{X}\) such that \(\Pr_{P_i}\{A_{ij}\} \geq 1- \varepsilon\) and \(\Pr_{Q_j}\{A_{ij}\} \leq 2^{-k_{ij}},\) for some \(k_{ij}>0.\) We want to construct an \(\mathcal{A}^\star\) such that \(\forall i \in \mathcal{S}_1, j \in \mathcal{S}_2,\) we have \(\Pr_{P_i}\{\mathcal{A}^\star\} \geq 1- |\mathcal{S}_2|\varepsilon\) and \(\Pr_{Q_j}\{\mathcal{A}^\star\} \leq |\mathcal{S}_1|.2^{-k},\) where \(k:= \min_{i,j}k_{i,j.}\) It is easy to see that \(\mathcal{A}^\star:= \cap_{j=1}^{|\mathcal{S}_2|}\cup_{i=1}^{|\mathcal{S}_1|}\mathcal{A}_{i,j}.\) We aim to prove a similar statement in the quantum setting. To define the problem formally let us consider two collections of quantum states \(\Theta_{\mathcal{S}_1} := \left\{\rho_i\right\}_{i=1}^{|\mathcal{S}_1|}\) and \(\Theta_{\mathcal{S}_2} := \left\{\sigma_j\right\}_{j=1}^{|\mathcal{S}_2|}\), defined over a Hilbert space \(\mathcal{H}\). Further for \(\forall i \in \mathcal{S}_1, j \in \mathcal{S}_2\), we are given a projector \(\Pi_{ij}\) such that \(\mathrm{Tr}[\Pi_{ij}\rho_i] \geq 1 - \varepsilon\) and \(\mathrm{Tr}[\Pi_{ij}\sigma_j] \leq 2^{-k_{ij}}\) for some \(k_{ij} > 0\). We want to find a projector \(\Pi^{\star}\) which is similar in spirit to \(\mathcal{A}^\star:= \cap_{j=1}^{|\mathcal{S}_2|}\cup_{i=1}^{|\mathcal{S}_1|}\mathcal{A}_{i,j}.\) Such a \(\Pi^{\star}\) will help us to study the problem of asymmetric composite hypothesis testing discussed in Lemma 11.

In the classical case for two sets \(\mathcal{A}_1,\mathcal{A}_2 \subseteq \mathcal{X}\), it is well understood what does \(\mathcal{A}_{1 \cup 2} := \mathcal{A}_1 \cup \mathcal{A}_2\) and \(\mathcal{A}_{1 \cap 2} := \mathcal{A}_1 \cap \mathcal{A}_2\) mean. Likewise, in the quantum case consider \(\Pi_1,\Pi_2 \preceq \mathbb{I}_{\mathcal{H}}\) which are projectors over some subspaces of Hilbert space \(\mathcal{H}\). Unlike the classical case, we do not have a very clear understanding of \(\Pi_{1 \cup 2}\) and \(\Pi_{1 \cap 2}\). One approach to construct \(\Pi_{1 \cup 2}\), is by defining a projector on the span of the eigenvectors of the \(\Pi_1\) and \(\Pi_2\). But this approach has a drawback, because this span may be the whole Hilbert space \(\mathcal{H}\). Similarly, one may define \(\Pi_{1 \cap 2}\), by first defining a projector on the span of the eigenvectors of \(\Pi_1^c\) and \(\Pi_2^c\) and then take its orthogonal compliment. This approach also has a drawback, because this span may be the whole Hilbert space \(\mathcal{H}\) and therefore \(\Pi_{1 \cap 2}\) may not exist. Another approach for constructing \(\Pi_{1 \cap 2}\) can be \(\Pi_1\Pi_2\Pi_1.\) However, this construction also has an issue because \(\Pi_1\) and \(\Pi_2\) do not commute in general and sandwiching one projector with the other will depend on their ordering.

In this paper, we will address the issues discussed above. We will show that it is indeed possible to construct a \(\Pi^\star\) such that it satisfies the properties that are very analogous to the intersection and union of subsets as discussed above. Our construction for \(\Pi^\star\) heavily relies on Jordan’s lemma [11]. This lemma accomplishes simultaneous block diagonalization of two projection operators. This remarkable observation from Jordan has found many applications in quantum information and computation, for example, [12], [13] and also in post-quantum cryptography [14].

We now mention the following lemma which we prove in this work. Almost all the results obtained in this manuscript are based on this lemma. For the notations used in the statement of the lemma below, see Section 2.

We also generalize the above lemma for the case when we have a collection \(\{\sigma_i\}_{i=1}^{|\mathcal{S}|},\) where \(|\mathcal{S}|< \infty.\) For details see Lemma 5 and its proof in subsection 8.2 in Appendix.

We use Lemma 1 to study a problem of communication over a noisy classical-quantum channel in an adversarial setting. In this setting, like the compound channel case [15] we have a finite collection of channels \(\{\mathcal{N}^{(i)}_{X \to B}\}_{i=1}^{|\mathcal{S}|}.\) However, unlike the compound channel scenario the goal here is that we aim to communicate successfully only if the channel \(\mathcal{N}^{(s_0)}_{X \to B}\) is being used. However, for any \(s \neq s_0,\) we only want to detect that the channel \(\mathcal{N}^{(s_0)}_{X \to B}\) is not being used.

We can think of this scenario wherein a third party first authenticates the channel being used by inputting the symbol \(s_0\) into the channel. However, if this third party cheats by inputting some other symbol \(s \neq s_0\) in the channel. Then, we should either detect this or decode the message correctly. We define the capacity (\(C_{Auth}\)) for this model of communication and show that \[C_{Auth}= \max_{p_X}I[X;B_{(s_0)}],\]

where, \(I[X;B_{(s_0)}]\) is calculated with respect to the channel \(\mathcal{N}^{(s_0)}_{X \to B}\) and defined in Lemma 7. It can be observed that this communication model is also about channel discrimination. In our achievability proof, we use Lemma 1 to accomplish channel discrimination without disturbing the state a lot. Conditioned on the fact that we have detected the correct channel (\(\mathcal{N}^{(s_0)}_{X \to B}\)) we then proceed to decode the message sent by the sender. We also give a converse for this problem.

A more general version of the above communication model was introduced and studied by Kosut and Kliewer in [16]. In this general version, parties are interested in communicating successfully only if the channel \(\mathcal{N}^{(s_0)}_{X \to B}\) is being used across all the \(n\) channel uses. However, in other cases when the channel \(\mathcal{N}^{(s_0)}_{X \to B}\) is not being used across all the \(n\) channel uses, i.e. if the channel statistic is changing across all the \(n\) channel uses. Then, the receiver should either declare that the channel is behaving arbitrarily or decoding the message correctly.

With the help of the techniques used to prove Lemma \(1\), we also give a proof for a complementary version of the problem discussed in Lemma 1, mentioned as Lemma 2 below.

The Corollary below follows from Lemma 2 and it can be viewed as a quantum generalization of Fact 1, mentioned in section 2.

However, unlike the classical result mentioned in Fact 1, we have a subtractive term in the quantum setting as mentioned in the above corollary.

1.1 Comparison with previous works↩︎

Sen in [3], resolved the intersection issue for the case of classical-quantum states and their marginals respectively, using “tilting" and”augmenting" the Hilbert space to a significantly larger Hilbert space. Furthermore, he mentions the following in [3],

“The statement of our quantum joint typicality lemma is not as strong as the classical statement. It can only handle negative hypothesis states that are a tensor product of marginals and at most one arbitrary quantum state. Proving a quantum lemma that can handle arbitrary negative hypothesis states, as in the classical setting, is an important open problem."

Unlike Sen [3], we get a small additive term (See ?? in Lemma 1) because of the non-commutativity of the projection operators involved.

The problem of asymmetric composite hypothesis testing was also studied by Berta et al. in [17]. We make a comparison of our results (Lemma 10 and Lemma 11) with the results obtained in [17] in subsection 6.4.

The rest of the paper is organized as follows. In Section 2, we mention the notations and facts used in this manuscript. Section 3 discusses a detailed proof for Lemma 1 and also discusses two generalized versions of Lemma 1, which are mentioned as Lemma 5 and 6. In Section 4, we study the problem of communication over authenticated classical-quantum channels and establish its capacity. In Section 5, we give a proof for Lemma 2 and in Section 6, we study the problems of quantum asymmetric composite hypothesis testing under various settings.

2 Notations and Facts↩︎

We use \(\mathcal{H}\) to denote a finite-dimensional Hilbert space and \(\mathcal{D}(\mathcal{H})\) to represent the set of all quantum states acting on \(\mathcal{H}\). For any quantum state \(\rho\), we define \(supp(\rho):=span\{|i \rangle: \lambda_{i}> 0\},\) where \(\left\{\lambda_i\right\}\) represent non-zero eigenvalues of \(\rho\). Similarly, for any distribution \(P\) defined over a set \(\mathcal{X}\), \(supp(P):=\{x\in \mathcal{X}: P(x)>0\}.\) Given two distribution \(P \text{ and } Q\) over the set \(\mathcal{X}\) such that \(supp(P) \subseteq supp(Q)\), the relative entropy between \(P\) and \(Q\) is defined as, \[D(P\|Q) := \sum_{x \in \mathcal{X}}P(x)\log\left(\frac{P(x)}{Q(x)}\right).\]

Given two quantum states \(\rho, \sigma \in \mathcal{D}(\mathcal{H})\) such that \(supp(\rho) \subseteq supp(\sigma)\), the quantum relative entropy (also known to be quantum KL-divergence) between \(\rho\) and \(\sigma\) is defined as, \[D(\rho\| \sigma):= \mathrm{Tr}[\rho(\log(\rho)-\log(\sigma)].\]

For two normal operators \(A\) and \(B\) we will use the notation \(\Pi :=\{A \succeq B\} \triangleq \{B \preceq A\}\) to denote a projection operator on the positive eigenspace of the operator \((A-B).\) We use \(\rho^{\otimes n}\) over \({\mathcal{H}}^{\otimes n}\), to represent \(n\) independent copies of \(\rho\).

3 Proof of Lemma 1↩︎

3.1 Construction of the Intersection Projector \(\Pi^{\star}\)↩︎

Let \(\Pi_1\) and \(\Pi_2\) be as mentioned in Lemma 1. We will apply Fact 2 on the pair \(\{\Pi_1, \Pi_2\}.\) Consider \(\left\{\mathbf{P}_{\alpha}\right\}_{{\alpha}=1}^{{\bar{k}}}\) (where \(\bar{k}\) is some natural number depending on \(\Pi_1,\Pi_2\)) as the set of orthogonal projectors obtained by Fact 2 applied with respect to the pair \(\{\Pi_1, \Pi_2\}.\) Thus, \(\sum_{{\alpha} =1}^{{\bar{k}}}\mathbf{P}_{\alpha} = \mathbb{I}.\) Furthermore, for every \({\alpha} \in [1:{\bar{k}}]\) we define \(\Pi_{1,{\alpha}} := \mathbf{P}_{\alpha}\Pi_1\mathbf{P}_{\alpha}\) as the following one dimensional projector: \[\begin{align} \Pi_{1,{\alpha}} := |v_{\alpha} \rangle\langle v_{\alpha}|\nonumber, \end{align}\] for some \(|v_{\alpha} \rangle\) in the range of \(\mathbf{P}_{\alpha}.\) Similarly, for every \({\alpha} \in [1:{\bar{k}}]\), we have \[\begin{align} \Pi_{2,{\alpha}} := |w_{\alpha} \rangle\langle w_{\alpha}|\nonumber, \end{align}\] for some \(|w_{\alpha} \rangle\) in the range of \(\mathbf{P}_{\alpha}.\) Thus, it now follows from the property of \(\{|v_{\alpha} \rangle\}_{{\alpha}=1}^{\bar{k}}\) and \(\{|w_{\alpha} \rangle\}_{{\alpha}=1}^{\bar{k}}\) that \[\begin{align} \Pi_1 &:= \sum_{{\alpha} =1}^{{\bar{k}}} |v_{\alpha} \rangle\langle v_{\alpha}|, \end{align}\] \[\begin{align} \Pi_2&:= \sum_{{\alpha} =1}^{{\bar{k}}} |w_{\alpha} \rangle\langle w_{\alpha}|. \end{align}\]

Further, for every \({\alpha} \in [1:{\bar{k}}],\) let \[\begin{align} \rho_{\alpha} &:= \mathbf{P}_{\alpha} \rho \mathbf{P}_{\alpha},\label{rhoalphal1}\\ \sigma_{1,{\alpha}} &:= \mathbf{P}_{\alpha} \sigma_1 \mathbf{P}_{\alpha},\\ \sigma_{2,{\alpha}} &:= \mathbf{P}_{\alpha} \sigma_2 \mathbf{P}_{\alpha}. \end{align}\tag{1}\]

For our future discussions, it will be useful to make the following observations, for every \({\alpha} \in [1:{\bar{k}}],\) \(\rho_{\alpha}\succeq 0\) and \(\sum_{{\alpha}=1}^{{\bar{k}}}\mathrm{Tr}[\rho_{\alpha}]= 1.\) Thus, \(\{\mathrm{Tr}[\rho_{\alpha}]\}_{{\alpha}=1}^{{\bar{k}}}\) forms a valid probability distribution over \({\alpha} \in [1:{{\bar{k}}}]\). To construct an intersection projector \(\Pi^\star\) that satisfies ?? , ?? , ?? we first make few observations. From Jordan’s lemma (Fact 2) we have that for every \({\alpha} \in [1:\bar{k}]\) the vectors \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in either a two-dimensional subspace or one-dimensional subspace. For the blocks where both \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in a two-dimensional subspace we have the following, \[\label{valphatilda} |v_{\alpha} \rangle = \cos(\theta_{\alpha})|w_{\alpha} \rangle + \sin(\theta_{\alpha})|w^{\perp}_{\alpha} \rangle.\tag{2}\]

For the blocks, where both \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in one dimensional subspace then in that case \(\cos(\theta_{\alpha})=1,\) i.e., \(|w_{\alpha} \rangle = |v_{\alpha} \rangle\) for these cases. Now we define the following set \[\begin{align} Good&:= \left\{{\alpha}: \cos^2(\theta_{\alpha}) \geq 1- 8\varepsilon^{\frac{1}{2}}\right\},\label{good1} \end{align}\tag{3}\] where, \(\cos^2(\theta_{\alpha})= {|\langle v_{\alpha}| w_{\alpha}\rangle|}^2\). The intuition for defining the set \(\textrm{Good}\) is that we only want to consider those blocks where \(|v_{\alpha} \rangle\) and \(|w_{\alpha} \rangle\) are almost the same, i.e., the angle between them is very small. From Lemma 3 mentioned below, it follows that under the probability distribution \(\{\mathrm{Tr}[\rho_{\alpha}]\}_{\alpha=1}^k\),

\[\Pr\{\textrm{Good}\} \geq 1- \varepsilon^{\frac{1}{2}}.\label{c23}\tag{4}\]

To show the existence of \(\Pi^{\star}\) which satisfies ?? , ?? and ?? we construct \(\Pi^{\star}\) as follows, \[\label{tilda} \Pi^{\star}:= \sum_{{\alpha} \in Good} |v_{\alpha} \rangle\langle v_{\alpha}|.\tag{5}\]

We will now show that \(\Pi^\star\) satisfies ?? , ?? and ?? in the following subsection.

3.2 Proof for the properties of \(\Pi^{\star}\)↩︎

Proof of ??↩︎

Consider the following set of inequalities,

\[\begin{align} \mathrm{Tr}[\Pi^{\star}\rho] &\overset{a}=\sum_{{\alpha}\in Good}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}]\\ &= \sum_{{\alpha}=1}^{{\bar{k}}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] - \sum_{{\alpha}\notin Good} \mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] \\ &\overset{b} \geq 1- \varepsilon- \sum_{{\alpha}\notinGood}\mathrm{Tr}[\rho_{\alpha}]\\ &\overset{c} \geq 1-\varepsilon-\varepsilon^{\frac{1}{2}}\\ &\geq 1 -2\varepsilon^{\frac{1}{2}}, \end{align}\] where, \(a\) follows from the definition of 5 , \(b\) follows from the fact that \(\sum_{{\alpha}=1}^{{\bar{k}}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] = \mathrm{Tr}[\Pi_1 \rho] \geq 1 - \varepsilon\) and \(c\) follows from 4 .

Proof of ??↩︎

Consider the following set of inequalities, \[\begin{align} \mathrm{Tr}[\Pi^{\star}\sigma_1] &\overset{a}= \sum_{{\alpha}\in Good} \mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \sigma_{1,{\alpha}} ] \\ &\overset{b} \leq 2^{-{k_1}}\sum_{{\alpha} \in Good}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}]\\ &\leq 2^{-{k_1}}\sum_{{\alpha} \in Good}\mathrm{Tr}[ \rho_{\alpha}]\\ &\leq 2^{-{k_1}}, \end{align}\] where, \(a\) follows from the definition of \(\Pi^{\star}\) in \(\eqref{tilda},\) \(b\) follows from the property of the projector \(\Pi_1\) mentioned in the statement of Lemma 1.

Proof of ??↩︎

Consider the following set of inequalities, \[\begin{align} \mathrm{Tr}[\Pi^{\star}\sigma_2] &\overset{a}= \sum_{{\alpha}\in Good} \mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}|\sigma_{2,{\alpha}}] \nonumber\\ &\overset{b}=\sum_{{\alpha} \in Good}\bigg(\cos^2(\theta_{\alpha})\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}|\sigma_{2,{\alpha}}] + \sin^2(\theta_{\alpha})\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] \nonumber\\ &+ \cos(\theta_{\alpha})\sin(\theta_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}]\right) \bigg) \nonumber \end{align}\] \[\begin{align} &\overset{c} \leq \sum_{{\alpha} \in Good}\bigg(\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}] + \sin^2(\theta_{\alpha})\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] \nonumber\\ &+ \cos(\theta_{\alpha})\sin(\theta_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}]\right) \bigg) \nonumber\\ &\overset{d}{\leq}\mathrm{Tr}[\Pi_2\sigma_2] + \sum_{{\alpha} \in Good}\bigg(8\varepsilon^{\frac{1}{2}}\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] \nonumber\\ &+ \cos(\theta_{\alpha})\sin(\theta_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}]\right) \bigg) \nonumber\\ &\overset{e}{\leq}\mathrm{Tr}[\Pi_2\sigma_2] + \sum_{{\alpha} \in Good}\bigg(8\varepsilon^{\frac{1}{2}}\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] \nonumber + 2\sqrt{2}\varepsilon^{\frac{1}{4}}\left(\mathrm{Tr}[\sigma_{2,{\alpha}}] \right) \bigg) \nonumber\\ &\overset{f}{\leq} 2^{-{k_2}}\mathrm{Tr}[\Pi_2\rho] + \sum_{{\alpha} \in Good}\bigg(8\varepsilon^{\frac{1}{2}}\mathrm{Tr}[\sigma_{2,{\alpha}}] \nonumber + 2\sqrt{2}\varepsilon^{\frac{1}{4}}\mathrm{Tr}[\sigma_{2,{\alpha}}] \bigg) \nonumber\\ &\leq 2^{-{k_2}} + 2\sqrt{2}\varepsilon^{\frac{1}{4}} + 8\varepsilon^{\frac{1}{2}},\nonumber\\ &\overset{g}{\leq} 2^{-{k_2}} + 4\sqrt{2}\varepsilon^{\frac{1}{4}}, \end{align}\] where, \(a\) follows from the definition of \(\Pi^{\star}\) (see 5 ), \(b\) follows from 2 , \(c\) follows because \(\cos^2({\theta_{\alpha}}) \leq 1\), \(d\) follows from fact that from 3 , for all \(\alpha \in Good\), \(\sin^{2}(\theta_{\alpha}) \leq 8\varepsilon^{\frac{1}{2}}\) , \(e\) follows from the following series of inequalities: \[\begin{align} &\cos(\theta_{\alpha})\sin(\theta_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}]\right)\nonumber\\ &\leq\left\vert\cos(\theta_{\alpha})\sin(\theta_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}]\right)\right\vert\nonumber\\ &= \left\vert\cos(\theta_{\alpha})\sin(\theta_{\alpha})\right\vert\left\vert\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}]\right)\right\vert\nonumber\\ &= \left\vert\cos(\theta_{\alpha})\right\vert\left\vert\sin(\theta_{\alpha})\right\vert\left\vert\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}]\right)\right\vert\nonumber\\ &\leq 2\sqrt{2}\varepsilon^{\frac{1}{4}} \mathrm{Tr}[\sigma_{2,{\alpha}}],\label{extra95term95bound} \end{align}\tag{6}\] where, the last inequality follows from the facts that for all \(\alpha \in Good\), \(|\sin(\theta_{\alpha})| \leq 2\sqrt{2}\varepsilon^{\frac{1}{4}}, \left\vert\cos(\theta_{\alpha})\right\vert \leq 1\) and from ?? and ?? of Lemma 4 since \(\sigma_{2,{\alpha}} \succeq 0\). Ineqality \(f\) follows from the definition of \(\Pi_2\) (see the statement of Lemma 1) and \(g\) follows since \(8\varepsilon^{\frac{1}{2}} \in (0,1]\) is arbitrarily close to zero, \(8\varepsilon^{\frac{1}{2}} \leq \sqrt{8\varepsilon^{\frac{1}{2}}} = 2\sqrt{2}\varepsilon^{\frac{1}{4}}\).

Proof of ?? : From the positivity of the matrix \(A\) it follows that for any non-zero -vector \(|x\rangle\), \(\langle x|A|x\rangle \geq 0\). Now if we multiply \(A\) by the row vector \([1,-1]\) on the left and by the column vector \([1,-1]^T\) on the right, we will get \(\mathrm{Tr}[A] - 2 Re(b)\geq 0\), since \(A\) is positive.

Proof of ?? : Similarly if we multiply \(A\) by the row vector \([1,1]\) on the left and by the column vector \([1,1]^T\) on the right, we will get \(\mathrm{Tr}[A] + 2 Re(b)\geq 0\), since \(A\) is positive.

The following lemma is a general version of Lemma 1, where there are more than two projectors.

We can derive different bounds as compared to the bounds obtained in Lemma 5 if instead of the parallel construction discussed in Figure 1, we use a sequential construction as discussed below.

We start with \(2^{t}\) projectors and consider the first two projectors i.e. \(\Pi_1\) and \(\Pi_2\) from the collection. We find the intersection \(\Pi_{\{1,2\}}\) of the pair \(\{\Pi_{1},\Pi_{2}\}\). Next, we consider \(\Pi_{\{1,2\}}\) and \(\Pi_3\) and find the intersection \(\Pi_{\{1,2,3\}}\).

We keep repeating this process until we are left with only one projector. This approach allows us to systematically work our way down from the initial \(2^{t}\) projectors to a final single projector through a series of intersection operations sequentially. However, at each step, we change the set \(Good\) which depends on the number of the step. See Figure 2 below for a better understanding of the above strategy.

The above sequential construction yields us the following lemma.

4 Communication Over Authenticated Classical-Quantum channel↩︎

Consider a finite collection of classical-quantum channels \(\{\mathcal{N}^{(s)}_{X \to B}\}_{s=1}^{|\mathcal{S}|}.\) Now \(\mathcal{N}^{(s)}_{X \to B}\) corresponding to state \(s\) can be defined as a map from a classical system \(X\) with alphabet \(\mathcal{X}\) and orthonormal basis\(\{ |x \rangle : x \in \mathcal{X}\}\) to a quantum system \(B\) with an output Hilbert space \(\mathcal{H}_{B}\) with a specified set of quantum states \(\{\rho_{x}^{(s)} : x \in \mathcal{X}\}\). We can represent the above mapping using a classical quantum state \(\rho^{(s)}_{XB}\) corresponding to a state \(s \in \mathcal{S}\), where \(|\mathcal{S}| < \infty\) as follows, \[\rho^{(s)}_{XB} := \sum_{x}P_{X}(x)|x\rangle\langle x|\otimes\rho_{x}^{(s)}.\]

In this setting, both the sender and receiver are not aware of which one amongst these \(|\mathcal{S}|\) channels will be used for communication. However, they are interested in communicating successfully (with high probability) only when the \(s_0\) channel is used for communication. For all other cases, they should either detect that the \(s_0\) channel is not being used for communication or they should be able to communicate successfully (with high probability).

We define the average error probability of a code \(\mathcal{C}_{n}\),for a given \(s \in \mathcal{S}\), \(\Pr\{\mathcal{C}_{n},s\}\) as follows, \[\Pr\{\mathcal{C}_{n},s\}: =\frac{1}{2^{nR}}\sum_{m=1}^{2^{nR}}e (m, \mathcal{C}_{n}, s).\nonumber\]

For some \(R>0\), for every \(\bar{\varepsilon} \in (0,1)\), \(\delta>0\), and sufficiently large \(n\) , let there exist a (\(2^{nR},n\))-code \(\mathcal{C}_{n}\) such that \[\frac{\log|\mathcal{M}_n|}{n} > R -\delta, ~~ \max_{s \in \mathcal{S}} \Pr\{\mathcal{C}_{n},s\} < \bar{\varepsilon}.\]

The supremum over all such \(R\) is called the authentication capacity \(C_{Auth}\) of the classical-quantum authenticated channel.

This communication model can be considered as a relaxed version of the compound channel wherein irrespective of the channel being used the parties should be able to communicate successfully with high probability. Before further discussion on the analysis of error, we first state the following lemma.

5 Proof of Lemma 2↩︎

Let \(\Pi_1\) and \(\Pi_2\) be as mentioned in Lemma 2. We will apply Fact 2 on the pair \(\{\Pi_1, \Pi_2\}.\) Consider \(\left\{\mathbf{P}_{\alpha}\right\}_{{\alpha}=1}^k\) (where \(k\) is some natural number depending on \(\Pi_1,\Pi_2\)) as the set of orthogonal projectors obtained by Fact 2 applied with respect to the pair \(\{\Pi_1, \Pi_2\}.\) Thus, \(\sum_{{\alpha} =1}^k \mathbf{P}_{\alpha} = \mathbb{I}.\) Furthermore, for every \({\alpha} \in [1:k]\) we define \(\Pi_{1,{\alpha}} := \mathbf{P}_{\alpha}\Pi_1\mathbf{P}_{\alpha}\) and \(\Pi_{2,{\alpha}} := \mathbf{P}_{\alpha}\Pi_2\mathbf{P}_{\alpha}\) as the following one dimensional projector: \[\begin{align} \Pi_{1,{\alpha}} := |v_{\alpha} \rangle\langle v_{\alpha}|, \end{align}\] for some \(|v_{\alpha} \rangle\) in the range of \(\mathbf{P}_{\alpha}.\) Similarly, for every \({\alpha} \in [1:k]\), we have \[\begin{align} \Pi_{2,{\alpha}} := |w_{\alpha} \rangle\langle w_{\alpha}|, \end{align}\] for some \(|w_\alpha \rangle\) in the range of \(\mathbf{P}_{\alpha}.\) Thus, it is now follows from the property of \(\{|v_{\alpha} \rangle\}_{{\alpha}=1}^k\) and \(\{|w_{\alpha} \rangle\}_{{\alpha}=1}^k\) that \[\begin{align} \Pi_1 &:= \sum_{{\alpha} =1}^k |v_{\alpha} \rangle\langle v_{\alpha}|,\\ \Pi_2&:= \sum_{{\alpha} =1}^k |w_{\alpha} \rangle\langle w_{\alpha}|. \end{align}\]

Further, for every \({\alpha} \in [1:k],\) let \[\begin{align} \rho_{\alpha} &:= \mathbf{P}_{\alpha} \rho \mathbf{P}_{\alpha},\nonumber\\ \sigma_{1,{\alpha}} &:= \mathbf{P}_{\alpha} \sigma_1 \mathbf{P}_{\alpha},\nonumber\\ \sigma_{2,{\alpha}} &:= \mathbf{P}_{\alpha} \sigma_2 \mathbf{P}_{\alpha}.\label{sigma95295decom} \end{align}\tag{15}\]

Thus, from the definitions of \(\Pi_1\) and \(\Pi_2\), we have the following pair of inequalities for every \({\alpha} \in [1:k],\) \[\begin{align} \tag{16} \langle v_{\alpha}| \sigma_{1,{\alpha}}|v_{\alpha} \rangle &\geq 2^{-{k_1}} \langle v_{\alpha}|\rho_{\alpha}|v_{\alpha} \rangle, \\ \tag{17} \langle w_{\alpha}| \sigma_{2,{\alpha}}|w_{\alpha} \rangle &\geq 2^{-{k_2}} \langle w_{\alpha}|\rho_{\alpha}|w_{\alpha} \rangle. \end{align}\]

For our future discussions, it will be useful to make the following observations, for every \({\alpha} \in [1:k],\) \(\rho_{\alpha}\succeq 0\) and \(\sum_{{\alpha}=1}^k\mathrm{Tr}[\rho_{\alpha}]= 1.\) Thus, \(\{\mathrm{Tr}[\rho_{\alpha}]\}_{{\alpha}=1}^k\) forms a valid probability distribution over \({\alpha} \in [1:k]\). To construct an intersection projector \(\Pi^\star\) that satisfies ?? , ?? , ?? we first make few observations. From Jordan’s lemma (Fact 2) we have that for every \({\alpha} \in [1:k]\) the vectors \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in either a two-dimensional subspace or one-dimensional subspace. For the blocks where both \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in a two-dimensional subspace we have the following, \[\label{valpha} |v_{\alpha} \rangle = \cos(\theta_{\alpha})|w_{\alpha} \rangle + \sin(\theta_{\alpha})|w^{\perp}_{\alpha} \rangle.\tag{18}\]

For the blocks, where both \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in one dimensional subspace then in that case \(\cos(\theta_{\alpha})=1,\) i.e., \(|w_{\alpha} \rangle = |v_{\alpha} \rangle\) for these cases. Now we define the following set: \[\begin{align} {Good}&:=\left\{{\alpha}: \cos^2(\theta_{\alpha}) \geq 1- 8\varepsilon^{\frac{1}{2}}\right\}, \label{good95lb} \end{align}\tag{19}\] where, \(\cos^2(\theta_{\alpha}) = {|\langle v_{\alpha}| w_{\alpha}\rangle|}^2\). From 4 , the probability of the set \({Good}\) under the distribution \(\mathrm{Tr}[\rho_{\alpha}]\) satisfies the following lower bound: \[\Pr\{{Good}\} \geq 1- \varepsilon^{\frac{1}{2}}. \label{pgl}\tag{20}\]

To show the existence of \(\Pi^\star\) which satisfies ?? , ?? and ?? we construct \(\Pi^\star\) as follows, \[\label{starlb} \Pi^\star:= \sum_{{\alpha} \in {Good}} |v_{\alpha} \rangle\langle v_{\alpha}|.\tag{21}\]

Now we will show that \(\Pi^\star\) satisfies ?? , ?? and ?? in the following subsections.

5.1 Proof for the properties of \(\Pi^\star\)↩︎

Proof of ??↩︎

Consider the following set of inequalities, \[\begin{align} \mathrm{Tr}[\Pi^\star\rho] &\overset{a}=\sum_{{\alpha}\in {Good}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}]\nonumber\\ &= \sum_{\alpha = 1}^{k}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] - \sum_{{\alpha}\notin {Good}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}]\nonumber\\ &\overset{b}\geq 1 - \varepsilon- \sum_{{\alpha}\notin {Good}}\mathrm{Tr}[ \rho_{\alpha}]\nonumber\\ &\overset{c}\geq 1 - \varepsilon- \varepsilon^{\frac{1}{2}}\nonumber\\ &\geq 1-2\varepsilon^{\frac{1}{2}},\label{prop95rlb1} \end{align}\tag{22}\] where, \(a\) follows from the definition of 21 , \(b\) follows from the fact that \(\sum_{{\alpha}=1}^{{k}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] = \mathrm{Tr}[\Pi_1 \rho] \geq 1 - \varepsilon\) and \(c\) follows from 20 .

Proof of ??↩︎

Consider the following set of inequalities, \[\begin{align} \mathrm{Tr}[\Pi^\star\sigma_1] &\overset{a}= \sum_{{\alpha}\in {Good}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \sigma_{1,{\alpha}}] \end{align}\] \[\begin{align} &\overset{b} \geq 2^{-{k_1}}\sum_{{\alpha} \in {Good}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}]\\ &\overset{c}\geq 2^{-{k_1}}(1-2\varepsilon^{\frac{1}{2}}), \end{align}\] where, \(a\) follows from the definition of \(\eqref{starlb},\) \(b\) follows from 16 , \(c\) follows from 22 .

Proof of ??↩︎

Consider the following set of inequalities, \[\begin{align} &\mathrm{Tr}[\Pi^\star\sigma_2] \overset{a}= \sum_{{\alpha}\in {Good}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \sigma_{2,{\alpha}}] \nonumber\\ &\overset{b}=\sum_{{\alpha} \in {Good}}\bigg(\cos^2(\theta_{\alpha})\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}|\sigma_{2,{\alpha}}] + \sin^2(\theta_{\alpha})\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \cos(\theta_{\alpha})\sin(\theta_{\alpha})\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}]\nonumber \\ &+ \cos(\theta_{\alpha})\sin(\theta_{\alpha})\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}] \bigg) \nonumber\\ &\overset{c} \geq \sum_{{\alpha} \in {Good}}\bigg((1 - 8\varepsilon^{\frac{1}{2}})\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}] + \cos(\theta_{\alpha})\sin(\theta_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}]\right)\bigg) \nonumber\\ &\overset{d}\geq \sum_{{\alpha} \in {Good}}\bigg((1 - 8\varepsilon^{\frac{1}{2}})\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}] -\left\vert \cos(\theta_{\alpha})\sin(\theta_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}]\right)\right\vert\bigg) \nonumber\\ &\overset{e}\geq \sum_{{\alpha} \in {Good}}\bigg((1 - 8\varepsilon^{\frac{1}{2}})\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}] - 2\sqrt{2}\varepsilon^{\frac{1}{4}}\mathrm{Tr}[\sigma_{2,{\alpha}}]\bigg) \nonumber\\ &\overset{f}\geq 2^{-k_2}\bigg((1 - 8\varepsilon^{\frac{1}{2}})\sum_{{\alpha} \in {Good}}\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}| \rho_{{\alpha}}]\bigg) - 2\sqrt{2}\varepsilon^{\frac{1}{4}}\nonumber\\ &\overset{g}{\geq} 2^{-k_2}(1 - 8\varepsilon^{\frac{1}{2}})(1-2\varepsilon^{\frac{1}{2}}) - 2\sqrt{2}\varepsilon^{\frac{1}{4}}\nonumber\\ &\geq 2^{-{k_2}}(1-10\varepsilon^{\frac{1}{2}}) - 2\sqrt{2}\varepsilon^{\frac{1}{4}},\nonumber \label{mrf} \end{align}\tag{23}\] where, \(a\) follows from the definition of \(\Pi^\star\) (see 21 ), \(b\) follows from 18 , \(c\) follows from \(\cos^2(\theta_{\alpha}) \geq (1 - 8\varepsilon^{\frac{1}{2}})\) for every \(\alpha \in {Good}\) due to 19 and the trivial bound \(\sin^2(\theta_{\alpha})\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{2,{\alpha}}] \geq 0\), \(d\) follows from facts that for any real number \(x\), \(x \geq -\left\vert x\right\vert\) and \(\cos(\theta_{\alpha})\sin(\theta_{\alpha})(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}|\) \(\sigma_{2,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{2,{\alpha}}])\) is a real number, \(e\) follows from 6 , \(f\) holds because of 17 and the fact that \(\sum_{\alpha \in Good}\mathrm{Tr}[\sigma_{2,\alpha}] \leq \sum_{\alpha = 1}^{k}\mathrm{Tr}[\sigma_{2,\alpha}] = 1,\) and \(g\) follows from the fact that \(\sum_{{\alpha} \in {Good}}\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}| \rho_{{\alpha}}] = \mathrm{Tr}[\Pi^{\star}\rho] \geq 1 - 2\varepsilon^{\frac{1}{2}}\) due to 22 .

6 Asymmetric Composite Hypothesis Testing↩︎

6.1 Asymmetric Composite Hypothesis Testing \(\big(\)The case of \(\{\rho_s\}_{s=1}^{|\mathcal{S}|}\) and \(\sigma \big)\)↩︎

Consider a collection \(\{\rho_s\}_{s=1}^{|\mathcal{S}|}\) and \(\sigma\) where \(s \in \mathcal{S},|\mathcal{S}| < \infty.\) and \(\forall s, \rho_{s},\sigma \in \mathcal{D}(\mathcal{H})\). The aim here is to accept states from the collection \(\{\rho_s\}_{s=1}^{|\mathcal{S}|}\) with high probability and the state \(\sigma\) is wrongly identified as a state in the collection \(\{\rho_s\}_{s=1}^{|\mathcal{S}|}\) with very low probability. Formally, this problem can be defined as follows,

In this subsection, we will give an upper-bound (achievability) on \(\frac{1}{n}\log\beta_{(n,\varepsilon)}\left(\Theta_{\mathcal{S}},\sigma\right)\). However, before giving this upper-bound, we first discuss the following classical problem. Consider a finite collection of distributions \(\{P_i\}_{i=1}^{|\mathcal{S}|}\) and a distribution \(Q\) defined over a set \(\mathcal{X}.\) Further, \(\forall i \in \mathcal{S},\) we are given a set \(\mathcal{A}_{i} \subset \mathcal{X}\) such that \(\Pr_{P_i}\{A_{i}\} \geq 1- \varepsilon\) and \(\Pr_{Q}\{A_{i}\} \leq 2^{-k_{i}},\) for some \(k_{i}>0.\) It is easy to show that \(\forall i \in \mathcal{S}_,\) we have \(\Pr_{P_i}\{\mathcal{A}^\star\} \geq 1- |\mathcal{S}|\varepsilon\) and \(\Pr_{Q_j}\{\mathcal{A}^\star\} \leq 2^{-k},\) where \(k:= \min_{i}k_{i,}\) and \(\mathcal{A}^\star:= \cup_{i=1}^{|\mathcal{S}|}\mathcal{A}_{i}.\). Observe that we can re-write \(\mathcal{A}^\star:= \mathcal{X}\setminus \left\{\cap_{i=1}^{|\mathcal{S}|}\mathcal{A}_{i}^{c}\right\}\). In Lemma 9, we construct a \(\Pi_{n}^{\star}\) which behaves very similar to \(\mathcal{A}^\star:= \mathcal{X}\setminus \left\{\cap_{i=1}^{|\mathcal{S}|}\mathcal{A}_{i}^{c}\right\}\). This lemma will help us to give the achievability result. Before proving Lemma 9, we first prove the lemma below, which is for the case \(|\mathcal{S}| = 2\).

We now prove a general version of Lemma 8 below, wherein for the sake of simplicity, we assume that \(|\mathcal{S}|=2^t\) for some \(t>0.\) The case when \(|\mathcal{S}|\), is not of the form \(2^t\) can be handled similarly.

For the case when \(\mathbf{|\mathcal{S}|}\) is not in the form of \({2^{t}}\), for \(t > 0\), then the term \(\log|\mathcal{S}|\) in ?? and ?? becomes \(\left\lceil \log|\mathcal{S}| \right\rceil\).

A similar result was also proved by Anshu et al. in [13] using Jordan’s lemma. Even though we also use Jordan’s lemma in our construction, there is a difference both in the proof technique and the bounds obtained between these two results.

The definition of the set \(Near\) in [13] is not similar to that of the set \(Good\) in our case and the construction of \(\Pi^{\star}_{n}\) in Lemma 9 is different than that of \(\Pi^{\star}\) in [13]. This is because, in Lemma 9, for each pair of projectors, we find the complementary subspace of the intersection of the complementary subspaces of individual projectors, whereas in [13], for each pair of projectors, the union of the projectors is computed directly.

While there is a difference in strategy, the result of Lemma 9 is slightly different than [13] as well. The lower-bound mentioned in the RHS of ?? of Lemma 9, decreases with a rate \(O(\delta^{\frac{1}{2}})\) with increasing \(\delta\) whereas, in [13] the lower-bound decreases with a rate \(O(\delta)\) with increasing \(\delta\) and is smaller than \(O(\delta ^{\frac{1}{2}})\). However, the upper-bound mentioned in the RHS of ?? performs better than that of [13], since in the RHS of ?? , the upper-bound decreases with a rate \(O(\frac{1}{\delta})\) which is smaller than \(O(\frac{1}{\delta^2})\) in [13]. Thus it is important to observe that, there is a trade-off between Lemma 9 and [13].

Using Lemma 9 and Definition 2, we now give the following upper-bound for the quantity \(\beta_{(n,\varepsilon)}\left(\Theta_{\mathcal{S}},\sigma\right)\) defined in ?? ,

6.2 Asymmetric Composite Hypothesis Testing \(\big(\)The case of \(\rho\) and \(\{\sigma_s\}_{s=1}^{|\mathcal{S}|}\big)\)↩︎

Consider \(\rho\) and a collection \(\{\sigma_s\}_{s=1}^{|\mathcal{S}|}\) where \(s \in \mathcal{S},|\mathcal{S}| < \infty.\) and \(\forall s, \rho,\sigma_{s} \in \mathcal{D}(\mathcal{H})\). The aim here is to accept the state \(\rho\) with high probability and the probability that any state from the collection \(\{\sigma_s\}_{s=1}^{|\mathcal{S}|}\) is wrongly identified as \(\rho\) should be very small. Formally, this problem can be defined as follows,

In this subsection, we will give an upper-bound (achievability) on \(\mathrm{Tr}[\Lambda\sigma_s^{\otimes n}]\). However, before giving this upper-bound, we first discuss the following classical problem. Consider a distribution \(P\) and a finite collection of distributions \(\{Q_i\}_{i=1}^{|\mathcal{S}|}\), defined over a set \(\mathcal{X}.\) Further, \(\forall i \in \mathcal{S},\) we are given a set \(\mathcal{A}_{i} \subset \mathcal{X}\) such that \(\Pr_{P}\{\mathcal{A}_{i}\} \geq 1- \varepsilon\) and \(\Pr_{Q_i}\{\mathcal{A}_{i}\} \leq 2^{-k_{i}},\) for some \(k_{i}>0.\) It is easy to show that \(\forall i \in \mathcal{S}_,\) we have \(\Pr_{P_i}\{\mathcal{A}^\star\} \geq 1- |\mathcal{S}|\varepsilon\) and \(\Pr_{Q_j}\{\mathcal{A}^\star\} \leq 2^{-k},\) where \(k:= \min_{i}k_{i,}\) and \(\mathcal{A}^\star:= \cap_{i=1}^{|\mathcal{S}|}\mathcal{A}_{i}\). In Lemma 10, we construct a \(\Pi_{n}^{\star}\) which behaves very similar to \(\mathcal{A}^\star:= \cap_{i=1}^{|\mathcal{S}|}\mathcal{A}_{i}\). This lemma will help us to prove the achievability result below.

6.3 Asymmetric Composite Hypothesis Testing \(\big(\)The case of \(\{\rho_s\}_{s=1}^{|\mathcal{S}_1|}\) and \(\{\sigma_t\}_{t=1}^{|\mathcal{S}_2|}\big)\)↩︎

We now deal with a more general case wherein we have two collections of states \(\{\rho_s\}_{s=1}^{|\mathcal{S}_1|} \text{ and } \{\sigma_t\}_{t=1}^{|\mathcal{S}_2|},\) where \(s \in \mathcal{S}_1,t \in \mathcal{S}_2\) and \(|\mathcal{S}_1|,|\mathcal{S}_2| < \infty.\) The aim here is to accept any state from the collection \(\{\rho_s\}_{s=1}^{|\mathcal{S}_1|}\) with high probability and the probability that any state from the collection \(\{\sigma_s\}_{s=1}^{|\mathcal{S}|}\) is wrongly identified as a state in \(\{\rho_s\}_{s=1}^{|\mathcal{S}_1|}\) should be very small. To be more precise consider the statement of Lemma 11. For the sake of simplicity, we will assume \({|\mathcal{S}_1|:=2^u,|\mathcal{S}_2|:=2^v}\) in the lemma below for some \({u,v>0}\). The general case can be analyzed similarly. Before proving Lemma 11, we consider a classical version of the above problem. Consider two finite collections of distributions \(\mathcal{S}_1:=\{P_i\}_{i=1}^{|\mathcal{S}_1|}\) and \(\mathcal{S}_2:=\{Q_j\}_{j=1}^{|\mathcal{S}_2|},\) defined over a set \(\mathcal{X}.\) Further, \(\forall i \in \mathcal{S}_1\) and \(\forall j \in \mathcal{S}_2,\) we are given a set \(\mathcal{A}_{ij} \subset \mathcal{X}\) such that \(\Pr_{P_i}\{A_{ij}\} \geq 1- \varepsilon\) and \(\Pr_{Q_j}\{A_{ij}\} \leq 2^{-k_{ij}},\) for some \(k_{ij}>0.\) We want to construct an \(\mathcal{A}^\star\) such that \(\forall i \in \mathcal{S}_1, j \in \mathcal{S}_2,\) we have \(\Pr_{P_i}\{\mathcal{A}^\star\} \geq 1- |\mathcal{S}_2|\varepsilon\) and \(\Pr_{Q_j}\{\mathcal{A}^\star\} \leq 2^{-k},\) where \(k:= \min_{i,j}k_{i,j.}\) It is easy to see that \(\mathcal{A}^\star:= \cap_{j=1}^{|\mathcal{S}_2|}\cup_{i=1}^{|\mathcal{S}_1|}\mathcal{A}_{i,j}.\) In Lemma 11, we construct a \(\Pi_{n}^{\star}\) which behaves very similar to \(\mathcal{A}^\star:= \cap_{j=1}^{|\mathcal{S}_2|}\cup_{i=1}^{|\mathcal{S}_1|}\mathcal{A}_{i,j}.\) This lemma will help us to prove the achievability result below.

6.4 Comparison with [17]↩︎

In [17], Berta et al. studied the following problem. They considered two sets of quantum states \(\mathcal{S}\) and \(\mathcal{T}.\) Further, they defined the sets \(\mathcal{S}_n:= conv\{\rho^{\otimes n}; \rho \in \mathcal{S}\}\) and \(\mathcal{T}_n:= conv\{\sigma^{\otimes n}; \sigma \in \mathcal{T}\},\) The aim here is to design a positive operator \(\Lambda_n \preceq \mathbb{I}\), such that for all \(\rho^{\otimes n} \in \mathcal{S}_n\), we have, \(\mathrm{Tr}(\Lambda_n \rho^{\otimes n})\geq 1-\varepsilon,\) where \(\varepsilon\in (0,1)\) and for every \(\sigma^{\otimes n} \in \mathcal{T}_n\), \(\mathrm{Tr}(\Lambda_n \sigma^{\otimes n})\) is as small as possible. For this problem in the case when \(\mathcal{S}\) is a singleton set. [17] implies existence of a POVM such that \(\mathrm{Tr}(\Lambda_n \rho^{\otimes n})\geq 1-\varepsilon,\) with the property that for every for every \(\sigma^{\otimes n} \in \mathcal{T}_n\) \[\label{berta} \mathrm{Tr}(\Lambda_n \sigma^{\otimes n}) \leq 2^{- \underset{\mu \in \mathcal{T}}{\inf} D(\rho^{\otimes n} \| \int \sigma^{\otimes n}d\mu(\sigma))}.\tag{27}\]

As observed in [17], the exponent in 27 is not in single letter form, which is due to the following reason: \[\lim_{ n \to \infty}\frac{1}{n} \underset{\mu \in \mathcal{T}}{\inf} D(\rho^{\otimes n} \| \int \sigma^{\otimes n}d\mu(\sigma)) \neq \underset{\sigma \in \mathcal{T}}{\inf} D(\rho \| \sigma).\label{non95convergence}\tag{28}\]

As compared to 27 , in ?? of Lemma 10, the exponent of the leading term is in single letter form. However, because of the non-commutativity of the projection operators involved, we get an additive term, which can be made arbitrarily small.

The case, when \(\mathcal{S}\) is not a singleton set, [17] implies existence of a POVM such that \(\underset{\nu \in \mathcal{T}}{\sup}\mathrm{Tr}(\Lambda_n \int \rho^{\otimes n}d\nu(\rho))\geq 1-\varepsilon,\) with the property that for every for every \(\sigma^{\otimes n} \in \mathcal{T}_n\), \[\label{berta2} \mathrm{Tr}(\Lambda_n \sigma^{\otimes n}) \leq 2^{\underset{\substack{\rho \in \mathcal{S}, \mu \in \mathcal{T}}}{-\inf} D(\rho^{\otimes n} \| \int \sigma^{\otimes n}d\mu(\sigma))}.\tag{29}\]

The exponent in 29 is not in single letter form, whereas, in ?? of Lemma 11, the exponent of the leading term is in single letter form due to 28 . However, we get an additive term in terms of \(\delta\). This is because proof of Lemma 11 follows from the result of Lemma 10, which faces the same issue discussed in the above paragraph. Therefore, we can not make the probability that any state from the collection \(\{\sigma_s\}_{s=1}^{|\mathcal{S}|}\) is wrongly identified as a state in \(\{\rho_s\}_{s=1}^{|\mathcal{S}_1|}\) arbitrarily small, since there is a trade-off between ?? and ?? in terms of \(\delta\).

However, note that Anshu et al. in [13], using the results of [13], provide a proof of 29 , when \(\mathcal{T}\) is a finite set. As observed earlier, apart from the constants, the result mentioned in Lemma 9 is structurally similar to that of [13]. Therefore, one can recover a proof of (\(51\)) in the case when \(\mathcal{T}\) is a finite set using Lemma \(7\).

7 Conclusion and Acknowledgements↩︎

In this work, we have provided a notion of intersection and union of a collection of projection operators. Our method is based on Jordan’s lemma and is arguably intuitive. An observation that we make while constructing a projection operator which behaves analogous to intersection of subsets is to consider only those sub-spaces that have very small angles between them. Using our technique we study a communication model, wherein, a third party authenticates the communication channel. We derive the capacity of this communication model. This communication model is similar to the compound channel case. However, unlike the compound channel case, the parties are only interested to communicate successfully only if the particular \(s_o\) channel in the collection is used. In all other cases, the receiver should either declare that some channel other than \(s_0\) channel is being used or it should decode the message correctly. We also study the problem of asymmetric composite hypothesis testing using the techniques developed in this manuscript.

As a future work, one can study a more general version of the communication model studied in this paper. In a more general version, the parties are interested to communicate successfully if the \(s_0\) channel is being used across all the \(n\) channel uses. In other cases when the \(s_o\) channel is not being used across all the \(n\) channel uses, i.e., if the channel statistic is changing across all the \(n\) channel uses. Then, the receiver should either declare that the channel is behaving arbitrarily or decode the message correctly. Further, it will be interesting to find more applications of the intersection and union projectors developed in this work.

We thank the anonymous referees and the editor for their helpful suggestions which have helped us to greatly improve the presentation and the technical content of this manuscript. We are grateful to one of the referees for the changes suggested in the proofs of Lemma 1, 2 and 5.

The work of N. A. Warsi was supported in part by MTR/2022/000814, DST/INT/RUS/RSF/P-41/2021 from the Department of Science & Technology, Govt. of India and DCSW grant provided by the Indian Statistical Institute.

8 Appendix↩︎

8.1 Proof of Lemma 3:↩︎

Using the basis obtained from Jordan’s lemma (fact 2) we have the following representation of \(\Pi_1\Pi_2\Pi_1,\) \[\label{intersection95gub} \Pi_1\Pi_2\Pi_1 := \sum_{{\alpha} =1}^{\bar{k}} \cos^2(\theta_{\alpha})|v_{\alpha} \rangle\langle v_{\alpha}|,\tag{30}\] where, \(\cos^2(\theta_{\alpha}):= {|\langle v_{\alpha}| w_{\alpha}\rangle|}^2\). We now have the following set of inequalities, \[\begin{align} 1 - 4(\varepsilon_1+\varepsilon_2) & \overset{a}\leq \mathrm{Tr}[\Pi_1\Pi_2\Pi_1 \rho] \nonumber\\ &\overset{b}= \sum_{{\alpha} =1}^{\bar{k}} \cos^2(\theta_{\alpha})\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] \nonumber\\ \label{expec95gub} & \overset{c}\leq \sum_{{\alpha} =1}^{\bar{k}}\cos^2(\theta_{\alpha})\mathrm{Tr}[\rho_{\alpha}], \end{align}\tag{31}\] where, \(a\) follows from the Gao’s union bound (Fact 6) and the fact that \(\mathrm{Tr}[\Pi_1 \rho] \geq 1 - \varepsilon_1\) and \(\mathrm{Tr}[\Pi_2 \rho] \geq 1 - \varepsilon_2\), \(b\) follows from 30 and \(c\) follows from the property of the trace and the fact that \(|v_{\alpha} \rangle\langle v_{\alpha}|\) is a projector. Thus, it follows from 31 that \[\begin{align} \label{expectation95gub} \mathbb{E}[\cos^2(\theta_{\alpha})] \geq 1-4(\varepsilon_1+\varepsilon_2), \end{align}\tag{32}\] where, in the above the expectation is calculated with respect to the distribution \(\mathrm{Tr}[\rho_{\alpha}].\) Thus, \[\begin{align} \Pr\{\sin^2(\theta_{\alpha}) > \delta\} & \overset{a} \leq \frac{\mathbb{E}[\sin^2(\theta_{\alpha})] }{\delta}\nonumber\\ &\overset{b} \leq \frac{4(\varepsilon_1 + \varepsilon_2)}{\delta},\label{c2395gub95equation} \end{align}\tag{33}\] where, \(a\) follows from the Fact 3 and \(b\) follows from 32 . This completes the proof of Lemma 3.0◻

8.2 Proof of Lemma 5↩︎

We will prove Lemma 5 using ‘proof by induction’. We start the collection of \(|\mathcal{S}|= 2^{t}\) projectors \({\{\Pi_i\}}_{i\in\{1,2,\cdots,|\mathcal{S}|\}}\). We then, consider the pairs of projectors \(\left\{\Pi_{1},\Pi_{2}\right\}, \left\{\Pi_{3},\Pi_{4}\right\},\cdots\left\{\Pi_{2^t-1},\Pi_{2^t}\right\}\). For each \(i \in \{1,2,\cdots,2^{t-1}\}\), we have the following properties for \(\left\{\Pi_{2i-1},\Pi_{2i}\right\}\), \[\begin{align} &\mathrm{Tr}[\Pi_{2i-1}\rho] \geq 1- \varepsilon,\\ &\mathrm{Tr}[\Pi_{2i-1}\sigma_{2i-1}] \leq 2^{-k_{2i-1}},\\ &\mathrm{Tr}[\Pi_{2i}\rho] \geq 1- \varepsilon,\\ &\mathrm{Tr}[\Pi_{2i}\sigma_{2i}] \leq 2^{-k_{2i}}. \end{align}\]

Using a similar approach used to prove Lemma 1, we construct intersection projectors \(\Pi_{\{1,2\}},\Pi_{\{3,4\}},\) \(\cdots,\Pi_{\{2^{t}-1,2^{t}\}}\) corresponding to the pairs \(\left\{\Pi_{1},\Pi_{2}\right\}, \left\{\Pi_{3},\Pi_{4}\right\},\cdots\left\{\Pi_{2^t-1},\Pi_{2^t}\right\}\) respectively using the following set, \[Good^{(1)}:= \left\{{\alpha}: \cos^2(\theta_{\alpha}^{(1)}) \geq 1- 8\varepsilon^{\beta}\right\},\label{goodstep1}\tag{34}\] where, \(\theta_\alpha^{(1)}\) depends on the choice of the pair of the projectors at step \(1\). Thus, \(\forall i \in \{1,2,\cdots,2^{t-1}\}\), \(\Pi_{\{2i-1,2i\}}\) has the following properties, \[\begin{align} \mathrm{Tr}[\Pi_{\{2i-1,2i\}}\rho] &\geq 1 - 2\varepsilon^{(1 - \beta)}, \\ \mathrm{Tr}[\Pi_{\{2i-1,2i\}}\sigma_{j}] &\leq 2^{-k_{j}} + c(1)\varepsilon^{\frac{\beta}{2}}, \forall j \in \{2i-1,2i\}, \end{align}\] where, \(c(1) \in [0,4\sqrt{2}]\). Thus, the above discussion proves the base case. Note that in this step for each pair of projectors, we define \(Good^{(1)}\) by replacing \(\varepsilon^{\frac{1}{2}}\) by \(\varepsilon^\beta\) in 3 . In the next step we again construct intersection projectors \(\Pi_{\{1,2,3,4\}},\Pi_{\{5,6,7,8\}},\cdots,\Pi_{\{2^{t}-3,2^{t}-2, 2^{t}-1, 2^{t}\}}\) corresponding to the pairs \(\left\{\Pi_{\{1,2\}},\Pi_{\{3,4\}}\right\},\) \(\left\{\Pi_{\{5,6\}},\Pi_{\{7,8\}}\right\},\cdots,\left\{\Pi_{\{2^{t}-3,2^{t}-2\}}, \Pi_{\{2^{t}-1,2^{t}\}}\right\}\) respectively.

We keep doing this for \(t-1\) times and at each \(k\)-th step we define \(Good^{(k)}\) for the pair of projectors as follows, \[\begin{align} Good^{(k)}&:= \left\{{\alpha}: \cos^2(\theta_{\alpha}^{(k)}) \geq 1- 8k\varepsilon^{\beta}\right\},\label{goodi} \end{align}\tag{35}\] where, \(\theta_\alpha^{(k)}\) depends on the choice of the pair of the projectors at \(k\)-th step similar to that of 2 . Finally, we are left with the pair \(\left\{\Pi_{\{1,\cdots,2^{t-1}\}},\Pi_{\{2^{t-1}+1,\cdots,2^{t}\}}\right\}\). We assume that for \(t-1\)-th step the statement of Lemma 5 holds i.e. \(\Pi_{\{1,\cdots,2^{t-1}\}}\) and \(\Pi_{\{2^{t-1} + 1,\cdots,2^{t}\}}\) satisfy the following:

\[\begin{align} \mathrm{Tr}[\Pi_{\{1,\cdots,2^{t-1}\}}\rho] &\geq 1 - t\varepsilon^{1-(t-1)\beta},\tag{36}\\ \mathrm{Tr}[\Pi_{\{1,\cdots,2^{t-1}\}}\sigma_u] &\leq 2^{-k_u} + c({t-1})\varepsilon^{\frac{\beta}{2}}, \forall u \in \{1,\cdots,2^{t-1}\},\tag{37}\\ \mathrm{Tr}[\Pi_{\{2^{t-1} + 1,\cdots,2^{t}\}}\rho] &\geq 1 - t\varepsilon^{1-(t-1)\beta},\tag{38}\\ \mathrm{Tr}[\Pi_{\{2^{t-1} + 1,\cdots,2^{t}\}}\sigma_v] &\leq 2^{-k_v} + c({t-1})\varepsilon^{\frac{\beta}{2}}, \forall v \in \{2^{t-1} + 1,\cdots,2^{t}\},\tag{39} \end{align}\] where, \(c({t-1}) \in [0,4\sqrt{2}\sum_{i=1}^{t-1}\sqrt{i}].\) For simplicity of notations, we denote \(\Pi_{\{1,\cdots,2^{t-1}\}}\) and \(\Pi_{\{2^{t-1} + 1,\cdots,2^{t}\}}\) as \(\Pi_{A}\) and \(\Pi_{B}\). We will apply Fact 2 on the pair \(\{\Pi_A, \Pi_B\}.\) Consider \(\left\{\mathbf{P}_{\alpha}\right\}_{{\alpha}=1}^{{\bar{k}}}\) (where \(\bar{k}\) is some natural number depending on \(\Pi_A,\Pi_B\)) as the set of orthogonal projectors obtained by Fact 2 applied with respect to the pair \(\{\Pi_A, \Pi_B\}.\) Thus, \(\sum_{{\alpha} =1}^{{\bar{k}}}\mathbf{P}_{\alpha} = \mathbb{I}.\) Furthermore, for every \({\alpha} \in [1:{\bar{k}}]\) we define \(\Pi_{A,{\alpha}} := \mathbf{P}_{\alpha}\Pi_A\mathbf{P}_{\alpha}\) as the following one dimensional projector: \[\begin{align} \Pi_{A,{\alpha}} := |v_{\alpha} \rangle\langle v_{\alpha}|\nonumber, \end{align}\] for some \(|v_{\alpha} \rangle\) in the range of \(\mathbf{P}_{\alpha}.\) Similarly, for every \({\alpha} \in [1:{\bar{k}}]\), we have \[\begin{align} \Pi_{B,{\alpha}} := |w_{\alpha} \rangle\langle w_{\alpha}|\nonumber, \end{align}\] for some \(|w_{\alpha} \rangle\) in the range of \(\mathbf{P}_{\alpha}.\) Thus, it now follows from the property of \(\{|v_{\alpha} \rangle\}_{{\alpha}=1}^{\bar{k}}\) and \(\{|w_{\alpha} \rangle\}_{{\alpha}=1}^{\bar{k}}\) that \[\begin{align} \Pi_A &:= \sum_{{\alpha} =1}^{{\bar{k}}} |v_{\alpha} \rangle\langle v_{\alpha}|, \end{align}\] \[\begin{align} \Pi_B&:= \sum_{{\alpha} =1}^{{\bar{k}}} |w_{\alpha} \rangle\langle w_{\alpha}|. \end{align}\]

Further, for every \({\alpha} \in [1:{\bar{k}}],\) let \[\begin{align} \rho_{\alpha} &:= \mathbf{P}_{\alpha} \rho \mathbf{P}_{\alpha},\label{rhoalpha}\\ \sigma_{j,{\alpha}} &:= \mathbf{P}_{\alpha} \sigma_j \mathbf{P}_{\alpha}, \forall j \in {1,\cdots,\left\vert\mathcal{S}\right\vert}. \end{align}\tag{40}\]

From Jordan’s lemma (Fact 2) we have that for every \({\alpha} \in [1:\bar{k}]\) the vectors \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in either a two-dimensional subspace or one-dimensional subspace. For the blocks where both \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in a two-dimensional subspace we have the following, \[\label{valphatilda95gub} |v_{\alpha} \rangle = \cos(\theta_{\alpha}^{(t)})|w_{\alpha} \rangle + \sin(\theta_{\alpha}^{(t)})|w^{\perp}_{\alpha} \rangle.\tag{41}\] For the blocks, where both \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in one dimensional subspace then in that case \(\cos(\theta_{\alpha}^{(t)})=1,\) i.e., \(|w_{\alpha} \rangle = |v_{\alpha} \rangle\) for these cases. We now consider the following set \[\begin{align} Good^{(t)}&:= \left\{{\alpha}: \cos^2(\theta_{\alpha}^{(t)}) \geq 1- 8t\varepsilon^{\beta}\right\},\label{good195gub} \end{align}\tag{42}\] where, \(\cos^2(\theta_{\alpha}^{(t)})= {|\langle v_{\alpha}| w_{\alpha}\rangle|}^2\). Then, from Lemma 3, fixing \(\varepsilon_1 =\varepsilon_2 = t\varepsilon^{1 -(t-1)\beta}\) and \(\delta = 8t\varepsilon^{\beta}\), the probability of the set \(Good^{(t)}\) (defined in 42 ) under the distribution \(\{\mathrm{Tr}[\rho_\alpha]\}\) has the following lower bound, \[\sum_{{\alpha}\inGood^{(t)}}\mathrm{Tr}[\rho_{\alpha}] = \Pr\left\{Good^{(t)}\right\} \geq 1 - \varepsilon^{1 - t\beta}.\label{Good95prob95gub}\tag{43}\] We now construct \(\Pi^{\star}\) as follows, \[\label{tilda95gub} \Pi^{\star}:= \sum_{{\alpha} \in Good^{(t)}} |v_{\alpha} \rangle\langle v_{\alpha}|.\tag{44}\] In the following discussions, we will show that \(\Pi^\star\) satisfies ?? and ?? .

Proof of ??↩︎

Consider the following set of inequalities, \[\begin{align} \mathrm{Tr}[\Pi^{\star}\rho] &\overset{a}=\sum_{{\alpha}\in Good^{(t)}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}]\nonumber\\ &= \sum_{{\alpha}=1}^{{\bar{k}}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] - \sum_{{\alpha}\notin Good^{(t)}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] \nonumber\\ &\overset{b} \geq 1- t\varepsilon^{1-(t-1)\beta} - \sum_{{\alpha}\notinGood^{(t)}}\mathrm{Tr}[\rho_{\alpha}]\nonumber\\ &\overset{c} \geq 1-t\varepsilon^{1-(t-1)\beta} -\varepsilon^{1-t\beta}\nonumber\\ &\geq 1 - (t+1)\varepsilon^{1-t\beta},\label{gub95lowb} \end{align}\tag{45}\] where, \(a\) follows from the definition of 44 , \(b\) follows from the fact that \(\sum_{{\alpha}=1}^{{\bar{k}}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] = \mathrm{Tr}[\Pi_A \rho] \geq 1 - t\varepsilon^{1-(t-1)\beta}\) (where the last inequality follows from 36 ) and \(c\) follows from 43 .

Proof of ??↩︎

We provide the proof of ?? under two cases. We first consider a state \(\sigma_j\), where \(j \in \{1,\cdots,2^{t-1}\}\). Then the following set of inequalities holds, \[\begin{align} \mathrm{Tr}[\Pi^{\star}\sigma_j] &\overset{a}= \sum_{{\alpha}\in Good^{(t)}} \mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \sigma_{j,{\alpha}} ]\nonumber\\ &\overset{b}{\leq} \sum_{\alpha=1}^{\bar{k}} \mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \sigma_{j,{\alpha}} ]\nonumber\\ &= \mathrm{Tr}[\Pi_{A}\sigma_j]\\ &\overset{c}{\leq} 2^{-k_j} + c({t-1})\varepsilon^{\frac{\beta}{2}}\nonumber\\ &{\leq} 2^{-k_j} + c({t})\varepsilon^{\frac{\beta}{2}},\label{gub95case1} \end{align}\tag{46}\] where, \(a\) follows from the definition of \(\Pi^{\star}\) in \(\eqref{tilda95gub},\) \(b\) follows from the fact that \(Good^{(t)} \subseteq \{1,\cdots,\bar{k}\}\), \(c\) follows from 37 and in 46 , \(c(t)\) is some constant within the range \([0,4\sqrt{2}\sum_{i=1}^{t}\sqrt{i}].\) We now consider a state \(\sigma_j\), where \(j \in \{2^{t-1}+1,\cdots,2^t\}\). Then the following set of inequalities holds, \[\begin{align} \mathrm{Tr}[\Pi^{\star}\sigma_j] &\overset{a}= \sum_{{\alpha}\in Good^{(t)}} \mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}|\sigma_{j,{\alpha}}] \nonumber\\ &\overset{b}=\sum_{{\alpha} \in Good^{(t)}}\bigg(\cos^2(\theta_{\alpha}^{(t)})\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}|\sigma_{j,{\alpha}}] + \sin^2(\theta_{\alpha}^{(t)})\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] \nonumber\\ &+ \cos(\theta_{\alpha}^{(t)})\sin(\theta_{\alpha}^{(t)})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right) \bigg) \nonumber\\ &\overset{c} \leq \sum_{{\alpha} \in Good^{(t)}}\bigg(\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}] + \sin^2(\theta_{\alpha}^{(t)})\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] \nonumber\\ &+ \cos(\theta_{\alpha}^{(t)})\sin(\theta_{\alpha}^{(t)})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right) \bigg) \nonumber\\ &\overset{d}{\leq}\mathrm{Tr}[\Pi_B\sigma_j] + \sum_{{\alpha} \in Good^{(t)}}\bigg(8t\varepsilon^{\beta}\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] \nonumber\\ &+ \cos(\theta_{\alpha}^{(t)})\sin(\theta_{\alpha}^{(t)})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right) \bigg) \nonumber\\ &\overset{e}{\leq}\mathrm{Tr}[\Pi_B\sigma_j] + \sum_{{\alpha} \in Good^{(t)}}\bigg(8t\varepsilon^{\beta}\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] \nonumber + 2\sqrt{2}\sqrt{t}\varepsilon^{\frac{\beta}{2}}\left(\mathrm{Tr}[\sigma_{j,{\alpha}}] \right) \bigg) \nonumber\\ &\overset{f}{\leq} 2^{-{k_j}} + c({t-1})\varepsilon^{\frac{\beta}{2}} + \sum_{{\alpha} \in Good^{(t)}}\bigg(8t\varepsilon^{\beta}\mathrm{Tr}[\sigma_{j,{\alpha}}] + 2\sqrt{2}\sqrt{t}\varepsilon^{\frac{\beta}{2}}\mathrm{Tr}[\sigma_{j,{\alpha}}] \bigg) \nonumber\\ &\leq 2^{-{k_j}}+ c({t-1})\varepsilon^{\frac{\beta}{2}} + 2\sqrt{2}\sqrt{t}\varepsilon^{\frac{\beta}{2}} + 8t\varepsilon^{\beta}\nonumber\\ &\overset{g}{\leq} 2^{-{k_j}}+ c({t-1})\varepsilon^{\frac{\beta}{2}} + 4\sqrt{2}\sqrt{t}\varepsilon^{\frac{\beta}{2}}\nonumber\\ &\leq 2^{-{k_j}}+ c({t})\varepsilon^{\frac{\beta}{2}},\label{gub95case2} \end{align}\tag{47}\] where, \(a\) follows from the definition of \(\Pi^{\star}\) (see 44 ), \(b\) follows from 41 , \(c\) follows because \(\cos^2({\theta_{\alpha}^{(t)}}) \leq 1\), \(d\) follows from the fact that from 42 , for all \(\alpha \in Good^{(t)}\), \(\sin^{2}(\theta_{\alpha}^{(t)}) \leq 8t\varepsilon^{\beta}\) , \(e\) follows from the following series of inequalities: \[\begin{align} &\cos(\theta_{\alpha}^{(t)})\sin(\theta_{\alpha}^{(t)})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right)\nonumber\\ &\leq\left\vert\cos(\theta_{\alpha}^{(t)})\sin(\theta_{\alpha}^{(t)})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right)\right\vert\nonumber\\ &= \left\vert\cos(\theta_{\alpha}^{(t)})\sin(\theta_{\alpha}^{(t)})\right\vert\left\vert\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right)\right\vert\nonumber\\ &= \left\vert\cos(\theta_{\alpha}^{(t)})\right\vert\left\vert\sin(\theta_{\alpha}^{(t)})\right\vert\left\vert\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right)\right\vert\nonumber\\ &\leq 2\sqrt{2}\sqrt{t}\varepsilon^{\frac{\beta}{2}} \mathrm{Tr}[\sigma_{j,{\alpha}}],\label{feagxtko} \end{align}\tag{48}\] where, the last inequality follows from the facts that for all \(\alpha \in Good^{(t)}\), \(|\sin(\theta_{\alpha}^{(t)})| \leq 2\sqrt{2}\sqrt{t}\varepsilon^{\frac{\beta}{2}}, \left\vert\cos(\theta_{\alpha}^{(t)})\right\vert \leq 1\) and from ?? and ?? of Lemma 4 since \(\sigma_{j,{\alpha}} \succeq 0\). Inequality \(f\) follows from 39 (see the statement of Lemma 6) and \(g\) follows since \(8t\varepsilon^{\beta} \in (0,1]\) is arbitrarily close to zero, \(8t\varepsilon^{\beta} \leq \sqrt{8t\varepsilon^{\beta}} = 2\sqrt{2}\sqrt{t}\varepsilon^{\frac{\beta}{2}}\).

Combinining 45 46 47 , we have the following \[\begin{align} \mathrm{Tr}[\Pi^{\star}\rho] &\geq 1 - (t+1)\varepsilon^{(1 - t\beta)},\\ \mathrm{Tr}[\Pi^{\star}\sigma_{j}] &\leq 2^{-k_{j}} + c(t)\varepsilon^{\frac{\beta}{2}}, \forall j \in \{1,2,\cdots,2^{t}\}. \end{align}\]

This completes the proof of Lemma 5 using a parallel construction of \(\Pi^{\star}\).0◻

The following corollary follows straightforwardly from Lemma 5. This corollary helps us in the error analysis of [s1] of our decoding strategy for the authentication channel problem.

8.3 Proof of Lemma 6↩︎

We will prove Lemma 6 using ‘proof by induction’. We start with the collection of \(|\mathcal{S}|= 2^{t}\) projectors \({\{\Pi_i\}}_{i\in\{1,2,\cdots,|\mathcal{S}|\}}\). We then, consider the pair of projectors \(\left\{\Pi_{1},\Pi_{2}\right\}\). Thus, we have the following properties for the pair \(\left\{\Pi_{1},\Pi_{2}\right\}\), \[\begin{align} &\mathrm{Tr}[\Pi_{1}\rho] \geq 1- \varepsilon,\\ &\mathrm{Tr}[\Pi_{1}\sigma_{1}] \leq 2^{-k_{1}},\\ &\mathrm{Tr}[\Pi_{2}\rho] \geq 1- \varepsilon,\\ &\mathrm{Tr}[\Pi_{2}\sigma_{2}] \leq 2^{-k_{2}}. \end{align}\] By replacing \(\Pi_1\) as \(\Pi_2\) and \(\Pi_2\) as \(\Pi_1\) in the proof of Lemma 1 and replacing the set \(Good\) defined in 3 with the set \(Good^{(1)}\) defined in 34 , we can construct an intersection projector \(\Pi_{\{1,2\}}\) corresponding to \(\left\{\Pi_{1},\Pi_{2}\right\}\), which satisfies the following properties, \[\begin{align} \mathrm{Tr}[\Pi_{\{1,2\}}\rho] &\geq 1 - 2\varepsilon^{(1 - \beta)}, \\ \mathrm{Tr}[\Pi_{\{1,2\}}\sigma_{1}] &\leq 2^{-k_{1}} + 4\sqrt{2}.\varepsilon^{\frac{\beta}{2}}\\ \mathrm{Tr}[\Pi_{\{1,2\}}\sigma_{2}] &\leq 2^{-k_{2}}. \end{align}\] We can combine the last two of the above equations as follows, \[\begin{align} \mathrm{Tr}[\Pi_{\{1,2\}}\sigma_{j}] &\leq 2^{-k_{j}} + d(j,2)\varepsilon^{\frac{\beta}{2}}, \forall j \in \{1,2\}, \end{align}\] where, \(d(1,2) = 4\sqrt{2}\) and \(d(2,2) = 0\). This gives the proof for the base case. In the next step we again construct intersection projectors \(\Pi_{\{1,2,3\}}\) corresponding to the pair \(\left\{\Pi_{\{1,2\}},\Pi_{3}\right\}\). We keep doing the same for \(\left\vert\mathcal{S}\right\vert-2 = (2^t-2)\) times and at each \(k\)-th step we consider \(Good^{(k)}\) as defined in 35 for the corresponding pair of projectors.

Finally, we are left with the pair \(\left\{\Pi_{\{1,\cdots,2^{t}-1\}},\Pi_{2^{t}}\right\}\). We assume that for (\(2^t-2\))-th step the statement of Lemma 6 holds i.e. \(\Pi_{\{1,\cdots,2^{t}-1\}}\) satisfies the following: \[\begin{align} \mathrm{Tr}[\Pi_{\{1,\cdots,2^{t}-1\}}\rho] &\geq 1 - 2\varepsilon^{1-(2^t-2)\beta},\tag{49}\\ \mathrm{Tr}[\Pi_{\{1,\cdots,2^{t}-1\}}\sigma_u] &\leq 2^{-k_u} + d(u,2^t-1)\varepsilon^{\frac{\beta}{2}}, \forall u \in \{1,\cdots,2^t-1\}\tag{50}, \end{align}\] where, \(\forall u \in [2^t-2], d(u,2^t-1) = 4\sqrt{2}\sum_{j=u}^{2^t-2}\sqrt{j}\) and \(d(2^t-1,2^t-1) =0\). For simplicity of notations, we denote \(\Pi_{2^{t}}\) and \(\Pi_{\{1,\cdots,2^{t}-1\}}\) as \(\Pi_{A}\) and \(\Pi_{B}\). We will apply Fact 2 on the pair \(\{\Pi_A, \Pi_B\}.\) Consider \(\left\{\mathbf{P}_{\alpha}\right\}_{{\alpha}=1}^{{\bar{k}}}\) (where \(\bar{k}\) is some natural number depending on \(\Pi_A,\Pi_B\)) as the set of orthogonal projectors obtained by Fact 2 applied with respect to the pair \(\{\Pi_A, \Pi_B\}.\) Thus, \(\sum_{{\alpha} =1}^{{\bar{k}}}\mathbf{P}_{\alpha} = \mathbb{I}.\) Furthermore, for every \({\alpha} \in [1:{\bar{k}}]\) we define \(\Pi_{A,{\alpha}} := \mathbf{P}_{\alpha}\Pi_A\mathbf{P}_{\alpha}\) as the following one dimensional projector: \[\begin{align} \Pi_{A,{\alpha}} := |v_{\alpha} \rangle\langle v_{\alpha}|\nonumber, \end{align}\] for some \(|v_{\alpha} \rangle\) in the range of \(\mathbf{P}_{\alpha}.\) Similarly, for every \({\alpha} \in [1:{\bar{k}}]\), we have \[\begin{align} \Pi_{B,{\alpha}} := |w_{\alpha} \rangle\langle w_{\alpha}|\nonumber, \end{align}\] for some \(|w_{\alpha} \rangle\) in the range of \(\mathbf{P}_{\alpha}.\) Thus, it now follows from the property of \(\{|v_{\alpha} \rangle\}_{{\alpha}=1}^{\bar{k}}\) and \(\{|w_{\alpha} \rangle\}_{{\alpha}=1}^{\bar{k}}\) that \[\begin{align} \Pi_A &:= \sum_{{\alpha} =1}^{{\bar{k}}} |v_{\alpha} \rangle\langle v_{\alpha}|, \end{align}\] \[\begin{align} \Pi_B&:= \sum_{{\alpha} =1}^{{\bar{k}}} |w_{\alpha} \rangle\langle w_{\alpha}|. \end{align}\]

Further, for every \({\alpha} \in [1:{\bar{k}}],\) let \[\begin{align} \rho_{\alpha} &:= \mathbf{P}_{\alpha} \rho \mathbf{P}_{\alpha},\label{rhoalphaseq}\\ \sigma_{j,{\alpha}} &:= \mathbf{P}_{\alpha} \sigma_j \mathbf{P}_{\alpha}, \forall j \in {1,\cdots,\left\vert\mathcal{S}\right\vert}. \end{align}\tag{51}\]

From Jordan’s lemma (Fact 2) we have that for every \({\alpha} \in [1:\bar{k}]\) the vectors \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in either a two-dimensional subspace or one-dimensional subspace. For the blocks where both \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in a two-dimensional subspace we have the following, \[\label{valphatilda95gub95seq} |v_{\alpha} \rangle = \cos(\theta^{(2^t-1)}_{\alpha})|w_{\alpha} \rangle + \sin(\theta^{(2^t-1)}_{\alpha})|w^{\perp}_{\alpha} \rangle.\tag{52}\]

For the blocks, where both \(|w_{\alpha} \rangle\) and \(|v_{\alpha} \rangle\) lie in one dimensional subspace then in that case \(\cos(\theta^{(2^t-1)}_{\alpha})=1,\) i.e., \(|w_{\alpha} \rangle = |v_{\alpha} \rangle\) for these cases. Now we consider the following set \[\begin{align} Good^{(2^t-1)}&:= \left\{{\alpha}: \cos^2(\theta^{(2^t-1)}_{\alpha}) \geq 1- 8(2^t-1)\varepsilon^{\beta}\right\},\label{good195gub95seq} \end{align}\tag{53}\] where, \(\cos^2(\theta^{(2^t-1)}_{\alpha})= {|\langle v_{\alpha}| w_{\alpha}\rangle|}^2\). Then, from Lemma 3, fixing \(\varepsilon_1 = \varepsilon, \varepsilon_2 = 2\varepsilon^{1 -(2^t-2)\beta}\) and \(\delta = 8(2^t-1)\varepsilon^{\beta}\), the probability of the set \(Good^{(2^t-1)}\) (defined in 53 ) under the distribution \(\{\mathrm{Tr}[\rho_\alpha]\}\) has the following lowerbound,

\[\begin{align} \sum_{{\alpha}\inGood^{(2^t-1)}}\mathrm{Tr}[\rho_{\alpha}] = \Pr\left\{Good^{(2^t-1)}\right\} &\geq 1 - \frac{4(\varepsilon+ 2\varepsilon^{1 -(2^t-2)\beta})}{8(2^t-1)\varepsilon^{\beta}}\nonumber\\ &\geq 1 - \frac{4(3\varepsilon^{1 -(2^t-2)\beta})}{8(2^t-1)\varepsilon^{\beta}}\nonumber\\ &\geq 1 - \frac{3\varepsilon^{1 -(2^t-1)\beta}}{2(2^t-1)}\nonumber\\ &\geq 1 - \varepsilon^{1 -(2^t-1)\beta}. \label{Good95prob95gub95seq} \end{align}\tag{54}\]

We now construct \(\Pi^{\star}\) as follows, \[\label{tilda95gub95seq} \Pi^{\star}:= \sum_{{\alpha} \in Good^{(t)}} |v_{\alpha} \rangle\langle v_{\alpha}|.\tag{55}\]

In the following discussion, we will show that \(\Pi^\star\) satisfies ?? and ?? .

Proof of ??↩︎

Consider the following set of inequalities,

\[\begin{align} \mathrm{Tr}[\Pi^{\star}\rho] &\overset{a}=\sum_{{\alpha}\in Good^{(2^t-1)}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}]\nonumber\\ &= \sum_{{\alpha}=1}^{{\bar{k}}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] - \sum_{{\alpha}\notin Good^{(2^t-1)}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] \nonumber\\ &\overset{b} \geq 1- \varepsilon- \sum_{{\alpha}\notinGood^{(2^t-1)}}\mathrm{Tr}[\rho_{\alpha}]\nonumber\\ &\overset{c} \geq 1-\varepsilon-\varepsilon^{1-(2^t-1)\beta}\geq 1 - 2\varepsilon^{1-(2^t-1)\beta},\label{gub95lowb95seq} \end{align}\tag{56}\] where, \(a\) follows from the definition of 44 , \(b\) follows from the fact that \(\sum_{{\alpha}=1}^{{\bar{k}}}\mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \rho_{\alpha}] = \mathrm{Tr}[\Pi_A \rho] = \mathrm{Tr}[\Pi_{2^t} \rho] \geq 1 - \varepsilon\) (where the last inequality follows from the definition of \(\Pi_{2^t}\) mentioned in the statement of Lemma 6) and \(c\) follows from 54 .

Proof of ??↩︎

We provide the proof of ?? under two cases. We first consider the state \(\sigma_{2^t}\). Then the following set of inequalities holds, \[\begin{align} \mathrm{Tr}[\Pi^{\star}\sigma_{2^t}] &\overset{a}= \sum_{{\alpha}\in Good^{(2^t-1)}} \mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \sigma_{2^t,{\alpha}} ]\nonumber\\ &\overset{b}{\leq} \sum_{\alpha=1}^{\bar{k}} \mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}| \sigma_{2^t,{\alpha}} ]\nonumber\\ &= \mathrm{Tr}[\Pi_{A}\sigma_{2^t}]\nonumber\\ &= \mathrm{Tr}[\Pi_{2^t}\sigma_{2^t}]\nonumber\\ &\overset{c}{\leq} 2^{-k_{2^t}},\label{gub95case195seq} \end{align}\tag{57}\] where, \(a\) follows from the definition of of \(\Pi^{\star}\) in \(\eqref{tilda95gub95seq},\) \(b\) follows from the fact that \(Good^{(2^t-1)} \subseteq \{1,\cdots,\bar{k}\}\) and \(c\) follows from the the definition of \(\Pi_{2^t}\) mentioned in the statement of Lemma 6.

We now consider a state \(\sigma_j\), where \(j \in \{1,\cdots,2^t-1\}\). Then the following set of inequalities holds, \[\begin{align} \mathrm{Tr}[\Pi^{\star}\sigma_j] &\overset{a}= \sum_{{\alpha}\in Good^{(2^t-1)}} \mathrm{Tr}[|v_{\alpha} \rangle\langle v_{\alpha}|\sigma_{j,{\alpha}}] \nonumber\\ &\overset{b}=\sum_{{\alpha} \in Good^{(2^t-1)}}\bigg(\cos^2(\theta^{(2^t-1)}_{\alpha})\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}|\sigma_{j,{\alpha}}] + \sin^2(\theta^{(2^t-1)}_{\alpha})\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] \nonumber\\ &+ \cos(\theta^{(2^t-1)}_{\alpha})\sin(\theta^{(2^t-1)}_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right) \bigg) \nonumber\\ &\overset{c} \leq \sum_{{\alpha} \in Good^{(2^t-1)}}\bigg(\mathrm{Tr}[|w_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}] + \sin^2(\theta^{(2^t-1)}_{\alpha})\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] \nonumber\\ &+ \cos(\theta^{(2^t-1)}_{\alpha})\sin(\theta^{(2^t-1)}_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right) \bigg)\nonumber \end{align}\] \[\begin{align} &\overset{d}{\leq}\mathrm{Tr}[\Pi_B\sigma_j] + \sum_{{\alpha} \in Good^{(2^t-1)}}\bigg(8(2^t-1)\varepsilon^{\beta}\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] \nonumber\\ &+ \cos(\theta^{(2^t-1)}_{\alpha})\sin(\theta^{(2^t-1)}_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right) \bigg) \nonumber\\ &\overset{e}{\leq}\mathrm{Tr}[\Pi_B\sigma_j] + \sum_{{\alpha} \in Good^{(2^t-1)}}\bigg(8(2^t-1)\varepsilon^{\beta}\mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] \nonumber + 2\sqrt{2}\sqrt{2^t-1}\varepsilon^{\frac{\beta}{2}}\left(\mathrm{Tr}[\sigma_{j,{\alpha}}] \right) \bigg) \nonumber\\ &\overset{f}{\leq} 2^{-{k_j}} + d(j,2^t-1)\varepsilon^{\frac{\beta}{2}} + \sum_{{\alpha} \in Good^{(2^t-1)}}\bigg(8(2^t-1)\varepsilon^{\beta}\mathrm{Tr}[\sigma_{j,{\alpha}}] + 2\sqrt{2}\sqrt{2^t-1}\varepsilon^{\frac{\beta}{2}}\mathrm{Tr}[\sigma_{j,{\alpha}}] \bigg) \nonumber\\ &\leq 2^{-{k_j}}+ d(j,2^t-1)\varepsilon^{\frac{\beta}{2}} + 2\sqrt{2}\sqrt{2^t-1}\varepsilon^{\frac{\beta}{2}} + 8(2^t-1)\varepsilon^{\beta}\nonumber\\ &\overset{g}{\leq} 2^{-{k_j}}+ d(j,2^t-1)\varepsilon^{\frac{\beta}{2}} + 4\sqrt{2}\sqrt{2^t-1}\varepsilon^{\frac{\beta}{2}}\nonumber\\ &\leq 2^{-{k_j}}+ d(j,2^t)\varepsilon^{\frac{\beta}{2}},\label{gub95case295seq} \end{align}\tag{58}\] where, \(a\) follows from the definition of \(\Pi^{\star}\) (see 55 ), \(b\) follows from 52 , \(c\) follows because \(\cos^2({\theta^{(2^t-1)}_{\alpha}}) \leq 1\), \(d\) follows from the fact that from 53 , for all \(\alpha \in Good^{(2^t-1)}\), \(\sin^{2}(\theta^{(2^t-1)}_{\alpha}) \leq 8(2^t-1)\varepsilon^{\beta}\) , \(e\) follows from the following series of inequalities: \[\begin{align} &\cos(\theta^{(2^t-1)}_{\alpha})\sin(\theta^{(2^t-1)}_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right)\nonumber\\ &\leq\left\vert\cos(\theta^{(2^t-1)}_{\alpha})\sin(\theta^{(2^t-1)}_{\alpha})\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right)\right\vert\nonumber\\ &= \left\vert\cos(\theta^{(2^t-1)}_{\alpha})\sin(\theta^{(2^t-1)}_{\alpha})\right\vert\left\vert\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right)\right\vert\nonumber\\ &= \left\vert\cos(\theta^{(2^t-1)}_{\alpha})\right\vert\left\vert\sin(\theta^{(2^t-1)}_{\alpha})\right\vert\left\vert\left(\mathrm{Tr}[|w_{\alpha} \rangle\langle w^{\perp}_{\alpha}| \sigma_{j,{\alpha}}] + \mathrm{Tr}[|w^{\perp}_{\alpha} \rangle\langle w_{\alpha}| \sigma_{j,{\alpha}}]\right)\right\vert\nonumber\\ &\leq 2\sqrt{2}\sqrt{2^t-1}\varepsilon^{\frac{\beta}{2}} \mathrm{Tr}[\sigma_{j,{\alpha}}],\label{xmsftguw} \end{align}\tag{59}\] where, the last inequality follows from the facts that for all \(\alpha \in Good^{(2^t-1)}\), \(|\sin(\theta^{(2^t-1)}_{\alpha})| \leq 2\sqrt{2}\sqrt{2^t-1}\varepsilon^{\frac{\beta}{2}},\) \(\left\vert\cos(\theta^{(2^t-1)}_{\alpha})\right\vert \leq 1\) and from ?? and ?? of Lemma 4 since \(\sigma_{j,{\alpha}} \succeq 0\). Inequality \(f\) follows from 50 (see the statement of Lemma 6) and \(g\) follows since \(8(2^t-1)\varepsilon^{\beta} \in (0,1]\) is arbitrarily close to zero, \(8(2^t-1)\varepsilon^{\beta} \leq \sqrt{8(2^t-1)\varepsilon^{\beta}} = 2\sqrt{2}\sqrt{2^t-1}\varepsilon^{\frac{\beta}{2}}\).

Combinining 56 57 58 , we have the following \[\begin{align} \mathrm{Tr}[\Pi^{\star}\rho] &\geq 1 - 2\varepsilon^{(1 - (2^t-1)\beta)},\\ \mathrm{Tr}[\Pi^{\star}\sigma_{j}] &\leq 2^{-{k_j}}+ d(j,\left\vert\mathcal{S}\right\vert)\varepsilon^{\frac{\beta}{2}}, \forall j \in \{1,2,\cdots,2^{t}\}. \end{align}\]

This completes the proof of Lemma 6 using a sequential construction of \(\Pi^{\star}\).0◻

8.4 Proof of Lemma 10↩︎

8.5 Proof of Corollary 1↩︎

The proof follows techniques similar to the one used in the proof of Lemma 2. However, we give its proof for completeness. Let \(\Pi^{(1)}_n:=\{\sigma^{\otimes n} \succeq 2^{-n(D(\rho\| \sigma)+\delta)}\rho^{\otimes n}\}\) and consider \(n\) large enough such that \(\mathrm{Tr}[\Pi^{(1)}_n \rho^{\otimes n}] \geq 1-\varepsilon\) (this is guaranteed by Fact 4). Further, consider \(\left\{\mathbf{P}_{n,\alpha}\right\}_{{\alpha}=1}^{{k}}\) as the orthogonal projectors obtained by Fact 2 with respect to the pair \(\left\{\Pi^{(1)}_n,\Pi^{(2)}_n\right\}\). For every \(\alpha \in [1:k]\) we define \(\Pi^{(1)}_{n,\alpha}:= \mathbf{P}_{n,\alpha}\Pi^{(1)}_n \mathbf{P}_{n,\alpha}\) and \(\Pi^{(2)}_{n,\alpha}:= \mathbf{P}_{n,\alpha}\Pi^{(2)}_n \mathbf{P}_{n,\alpha}\) as the following one dimensional projectors, \[\begin{align} \Pi^{(1)}_{n,\alpha} &= |v_{n,\alpha} \rangle\langle v_{n,\alpha}|,\\ \Pi^{(2)}_{n,\alpha} &= |w_{n,\alpha} \rangle\langle w_{n,\alpha}|, \end{align}\] for some \(|v_{n,\alpha} \rangle, |w_{n,\alpha} \rangle\) in the subspace spanned by the eigen vectors of \(\mathbf{P}_{n,\alpha}\). Thus, it is now follows from the property of \(\{|v_{n,\alpha} \rangle\}_{{\alpha}=1}^k\) and \(\{|w_{n,\alpha} \rangle\}_{{\alpha}=1}^k\) that \[\begin{align} \Pi^{(1)}_{n} &:= \sum_{{\alpha} =1}^k |v_{n,\alpha} \rangle\langle v_{n,\alpha}|,\nonumber \end{align}\] \[\begin{align} \Pi^{(2)}_{n}&:= \sum_{{\alpha} =1}^k |w_{n,\alpha} \rangle\langle w_{n,\alpha}|.\label{pi95295corollary1} \end{align}\tag{60}\]

Further, for every \({\alpha} \in [1:k],\) let \[\begin{align} \rho^{n}_{\alpha} &:= \mathbf{P}_{n,\alpha}\rho^{\otimes n} \mathbf{P}_{n,\alpha},\\ \sigma^{n}_{\alpha} &:= \mathbf{P}_{n,\alpha} \sigma^{\otimes n} \mathbf{P}_{n,\alpha}. \end{align}\]

Now for \({\alpha} \in [1:k],\) \(|w_{n,\alpha} \rangle\) can be defined in the following way, \[|w_{n,\alpha} \rangle = \cos(\theta_{n,\alpha})|v_{n,\alpha} \rangle + \sin(\theta_{n,\alpha})|v^{\perp}_{n,\alpha} \rangle.\label{v95n95alpha}\tag{61}\]

Similar to 19 , in the proof of Lemma 2, we define \(Good\) as follows, \[\begin{align} {Good}&:=\left\{{\alpha}: \cos^2(\theta_{\alpha}) \geq 1- 8\varepsilon^{\frac{1}{2}}\right\},\label{good95lb95corollary} \end{align}\tag{62}\] where, \(\cos^2(\theta_{n,\alpha}) = {|\langle v_{n,\alpha}| w_{n,\alpha}\rangle|}^2.\)

We now prove the corollary using the following set of inequalities, \[\begin{align} &\mathrm{Tr}[\Pi^{(2)}_n\sigma^{\otimes n}] \overset{a}= \sum_{\alpha=1}^k\mathrm{Tr}[|w_{n,\alpha} \rangle\langle w_{n,\alpha}| \sigma^{n}_{\alpha}] \\ & \overset{b}\geq \sum_{\alpha \in Good}\mathrm{Tr}[|w_{n,\alpha} \rangle\langle w_{n,\alpha}| \sigma^{n}_{\alpha}]\\ &\overset{c}{=} \sum_{\alpha \in Good}\bigg(\cos^2(\theta_{n,\alpha})\mathrm{Tr}[|v_{n,\alpha} \rangle\langle v_{n,\alpha}| \sigma^{n}_{\alpha}] + \sin^2(\theta_{n,\alpha}) \mathrm{Tr}[|v^{\perp}_{n,\alpha} \rangle\langle v^{\perp}_{n,\alpha}| \sigma^{n}_{\alpha}] \\ &+ \cos(\theta_{n,\alpha})\sin(\theta_{n,\alpha}) ( \mathrm{Tr}[|v_{n,\alpha} \rangle\langle v^\perp_{n,\alpha}| \sigma^{n}_{\alpha}] +\mathrm{Tr}[|v^\perp_{n,\alpha} \rangle\langle v_{n,\alpha}| \sigma^{n}_{\alpha}]) \bigg)\\ &\overset{d}{\geq} \sum_{\alpha \in Good}\bigg((1-8\varepsilon^{\frac{1}{2}})\mathrm{Tr}[|v_{n,\alpha} \rangle\langle v_{n,\alpha}| \sigma^{n}_{\alpha}] + \cos(\theta_{n,\alpha})\sin(\theta_{n,\alpha}) ( \mathrm{Tr}[|v_{n,\alpha} \rangle\langle v^\perp_{n,\alpha}| \sigma^{n}_{\alpha}] +\mathrm{Tr}[|v^\perp_{n,\alpha} \rangle\langle v_{n,\alpha}| \sigma^{n}_{\alpha}]) \bigg)\\ &\overset{e}{\geq} \sum_{\alpha \in Good}\bigg((1-8\varepsilon^{\frac{1}{2}})\mathrm{Tr}[|v_{n,\alpha} \rangle\langle v_{n,\alpha}| \sigma^{n}_{\alpha}] - \left\vert \cos(\theta_{n,\alpha})\sin(\theta_{n,\alpha}) ( \mathrm{Tr}[|v_{n,\alpha} \rangle\langle v^\perp_{n,\alpha}| \sigma^{n}_{\alpha}] +\mathrm{Tr}[|v^\perp_{n,\alpha} \rangle\langle v_{n,\alpha}| \sigma^{n}_{\alpha}])\right\vert \bigg)\\ &\overset{f}{\geq} \sum_{\alpha \in Good}\bigg((1-8\varepsilon^{\frac{1}{2}})\mathrm{Tr}[|v_{n,\alpha} \rangle\langle v_{n,\alpha}| \sigma^{n}_{\alpha}] - 2\sqrt{2}\varepsilon^{\frac{1}{4}}\mathrm{Tr}[\sigma^{n}_{\alpha}]\bigg) \end{align}\] \[\begin{align} &\overset{g}\geq \sum_{\alpha \in Good}\bigg(2^{-n(D(\rho\| \sigma)+\delta)}(1-8\varepsilon^{\frac{1}{2}})\mathrm{Tr}[|v_{n,\alpha} \rangle\langle v_{n,\alpha}| \rho^{n}_{\alpha}]\bigg) -2\sqrt{2}\varepsilon^{\frac{1}{4}} \\ &= 2^{-n(D(\rho\| \sigma)+\delta)}(1-8\varepsilon^{\frac{1}{2}})\sum_{\alpha \in Good}\left(\mathrm{Tr}[|v_{n,\alpha} \rangle\langle v_{n,\alpha}| \rho^{n}_{\alpha}]\right) - 2\sqrt{2}\varepsilon^{\frac{1}{4}}\\ &\overset{h}\geq 2^{-n(D(\rho\| \sigma)+\delta)}(1-8\varepsilon^{\frac{1}{2}})(1-2\varepsilon^{\frac{1}{2}}) - 2\sqrt{2}\varepsilon^{\frac{1}{4}}\\ &= 2^{-n(D(\rho\| \sigma)+\delta)}(1-10\varepsilon^{\frac{1}{2}}) - 2\sqrt{2}\varepsilon^{\frac{1}{4}}, \end{align}\] where, \(a\) follows from the definition of 60 , \(b\) follows because each term in the summation is non-negative, \(c\) follows from 61 , \(d\) follows from \(\cos(\theta_{n,\alpha}) \geq 1-8\varepsilon^{\frac{1}{2}}\) for every \(\alpha \in Good\) due to 62 and the trivial bound \(\sin^2(\theta_{n,\alpha}) \mathrm{Tr}[|v^{\perp}_{n,\alpha} \rangle\langle v^{\perp}_{n,\alpha}| \sigma^{n}_{\alpha}] \geq 0\), \(e\) follows from facts that for any real number \(x\), \(x \geq -\left\vert x\right\vert\) and \(\cos(\theta_{n,\alpha})\sin(\theta_{n,\alpha}) ( \mathrm{Tr}[|v_{n,\alpha} \rangle\langle v^\perp_{n,\alpha}| \sigma^{n}_{\alpha}] +\mathrm{Tr}[|v^\perp_{n,\alpha} \rangle\langle v_{n,\alpha}| \sigma^{n}_{\alpha}])\) is a real number, \(f\) follows from 6 , \(g\) follows from 17 and \(\sum_{{\alpha} \in {Good}}\mathrm{Tr}[\sigma^{n}_{\alpha}] \leq \sum_{\alpha = 1}^{k}\mathrm{Tr}[\sigma^{n}_{\alpha}] = 1\) and \(h\) follows from the fact that \(\sum_{\alpha \in Good}\mathrm{Tr}[|v_{n,\alpha} \rangle\langle v_{n,\alpha}| \rho^{n}_{\alpha}] \geq 1-2\varepsilon^{\frac{1}{2}}\) due to 22 . This completes the proof of Corollary 1.0◻

8.6 Proof of Corollary 2↩︎

We consider a collection of states \(\left\{{\rho^{(s)}}^{\otimes n}\right\}_{s \in \mathcal{S}\setminus\{s_0\}}\) and a state \({\rho^{(s_0)}}^{\otimes n}\), where \(\forall s \in \mathcal{S}\) \({\rho^{(s)}}^{\otimes n} = \mathbb{E}_{X^n}\left[\rho^{(s)}_{X^n}\right]\). From the statement of Corollary 2, for each \(s \in \mathcal{S}\), \(\Pi^{(s)}_{(n)}\), satisfies the following properties, \[\begin{align} \mathrm{Tr}\left[\Pi^{(s)}_{(n)} {\rho^{(s_0)}}^{\otimes n}\right] &= \mathbb{E}_{X^n}\left[\mathrm{Tr}\left[\Pi^{(s)}_{(n)}\rho_{X^n}^{(s_0)}\right]\right] \geq 1 - \varepsilon,\\ \mathrm{Tr}\left[\Pi^{(s)}_{(n)} {\rho^{(s)}}^{\otimes n}\right] &= \mathbb{E}_{X^n}\left[\mathrm{Tr}\left[\Pi^{(s)}_{(n)}\rho_{X^n}^{(s)}\right]\right] \leq 2^{-n(D(\rho^{(s_0)} || \rho^{(s)}) - \delta)}. \end{align}\]

Now we can directly apply Lemma 5 on \(\left\{{\rho^{(s)}}^{\otimes n}\right\}_{s \in \mathcal{S}\setminus\{s_0\}}\) and \({\rho^{(s_0)}}^{\otimes n}\) and we get the following result \[\begin{align} \mathbb{E}_{X^n}\left[\mathrm{Tr}\left[\Pi_{(n)}^{\neg{\perp}}\rho_{X^n}^{(s_0)}\right]\right] &\geq 1 -\left(\left\lceil \log{(|\mathcal{S}| -1)} \right\rceil+1\right)\varepsilon^{\left({1 - \left\lceil \log(|\mathcal{S}|-1) \right\rceil}\beta\right)},\nonumber\\ \mathbb{E}_{X^n}\left[\mathrm{Tr}\left[\Pi_{(n)}^{\neg{\perp}}\rho_{X^n}^{(s)}\right]\right] &\leq 2^{-n\left(D(\rho^{(s_0)} || \rho^{(s)}) - \delta\right)} + c\left(\left\lceil \log(|\mathcal{S}|-1) \right\rceil\right)\varepsilon^{\frac{\beta}{2}}, \forall s \in \mathcal{S}\setminus\{s_0\},\nonumber\\ &\overset{a}{\leq} 2^{-n\left(D(\rho^{(s_0)} || \rho^{(s)}) - \delta\right)} + O\left(\left(\left\lceil \log(|\mathcal{S}|-1) \right\rceil\right)^\frac{3}{2}\right)\varepsilon^{\frac{\beta}{2}}, \forall s \in \mathcal{S}\setminus\{s_0\},\nonumber\\\label{decode95so95proof951} \end{align}\tag{63}\] where, \(a\) follows from the fact that \(c\left(\left\lceil \log(|\mathcal{S}|-1) \right\rceil\right) := \sum_{i=1}^{\left\lceil \log(|\mathcal{S}|-1) \right\rceil}\sqrt{i} = O(\left(\left\lceil \log(|\mathcal{S}|-1) \right\rceil\right)^\frac{3}{2})\) and since \(|\mathcal{S}|-1\) may not be in the form of \(2^{t}\) (for \(t > 0\)), we have used the term \(\left\lceil \log(|\mathcal{S}|-1) \right\rceil\) in the above two inequalities, as discussed in the paragraph below Lemma 9 (mentioned in bold font). Finally, we can rewrite 63 as follows, \[\begin{align} \mathbb{E}_{X^n}\left[\mathrm{Tr}\left[\Pi_{(n)}^{\neg{\perp}}\rho_{X^n}^{(s)}\right]\right] &\leq 2^{-n\left(\underset{\substack{s \in \mathcal{S}: s \neq s_0}}{\min}D(\rho^{(s_0)} || \rho^{(s)}) - \delta\right)} + O\left(\left(\left\lceil \log(|\mathcal{S}|-1) \right\rceil\right)^\frac{3}{2}\right)\varepsilon^{\frac{\beta}{2}}, \forall s \in \mathcal{S}\setminus\{s_0\}. \end{align}\]

This completes the proof of Corollary 2.0◻

References↩︎