Proof of Lemma 11.4.Let X be a uniform random bit,and let Y be the measurement outcome after applying the measurement {Mo,Mi}to the state p=(po+P1).Then by Holevo's bound,we have S(p)2 I(X;Y)+(S(po)+S(p)). Since we have Tr(Mbpb)>E,Pr[X =Y]>E and hence I(X;Y)=H(X)-H(XY)=1-H(XY).By Fano's inequality,let p Pr[XY],we have H(X Y)<H(p)+plog2(-1)<H(e)since =2 and p>s>1/2.It follows that I(X;Y)>1-H(e)and the proof is completed. For completeness,we also give a proof of Fano's inequality.The following proof is quite standard that can be found in many textbooks on information theory such as[?]. Lemma 11.5 (Fano's inequality).Let X,Y be random variables with support A,if Pr[X Y]=p, then H(X Y)<H(p)+plog2(-1). Proof.Let 2 be a random variable that 1,if X =Y. 0,fX≠Y. Now,let us consider H(XY).Since H(ZX,Y)=0,we have H(XY)=H(X,ZY) H(ZY)+H(X Y,Z) ≤H(Z)+H(XIY,Z) H(p)+pH(X Y,Z=0)+(1-p)H(X Y,Z=1) =H(p)+pH(X Y,Z=0) ≤H(p)+plog2X1-1) where the first inequality follows since conditioning does not increase entropy,and the second inequality follows by the fact that if XY then the number of possible outcomes of X is at most-1. 11.3 Source coding theorems 11.3.1 Classical source coding theorem Suppose Alice have an information source(a random variable)X that generates symbol x with proba- bility pr.For the purpose of efficient storage or transmission,she would want to encode the information using some short codes.So that when she sends the codeword to Bob,Bob can decode it and extract the information back.Ideally,Alice would want to have such a encoding and decoding scheme so that the probability that Bob can get back the symbol x is arbitrarily close to 1.Intuitively,H(X)bits seem to be sufficient since the entropy of X is just H(X).However,for any fix X,it is impossible to achieve arbitrarily small error probability if the codeword is shorter than log2.Nevertheless,if we consider the asymptotic version of this problem,i.e.Alice has n independent copies of X,namely X",whose generates symbol z"=1...n with probability IIp,and she want to assign a codeword for each z"so that Bob can decode the codeword to get back x with probability tends to 1 as n-oo.It turns out that we can achieve it with rate (defined by the length of the codeword divided by n)arbitrarily close to H(X).And moreover,it is also necessary. Theorem 11.6 (Shannon's source coding theorem).Let Xn be n i.i.d.copies of X.Then the following holds: L11-3Proof of Lemma 11.4. Let X be a uniform random bit, and let Y be the measurement outcome after applying the measurement {M0, M1} to the state ρ = 1 2 (ρ0 + ρ1). Then by Holevo’s bound, we have S(ρ) ≥ I(X; Y ) + 1 2 ￾ S(ρ0) + S(ρ1)
. Since we have Tr(Mbρb) ≥ ε, Pr[X = Y ] ≥ ε and hence I(X; Y ) = H(X) − H(X|Y ) = 1 − H(X|Y ). By Fano’s inequality, let p = Pr[X 6= Y ], we have H(X|Y ) ≤ H(p) + p log2 (|X | − 1) ≤ H(ε) since X = 2 and p ≥ ε ≥ 1/2. It follows that I(X; Y ) ≥ 1 − H(ε) and the proof is completed. For completeness, we also give a proof of Fano’s inequality. The following proof is quite standard that can be found in many textbooks on information theory such as [?]. Lemma 11.5 (Fano’s inequality). Let X, Y be random variables with support X , if Pr[X 6= Y ] = p, then H(X|Y ) ≤ H(p) + p log2 (|X | − 1). Proof. Let Z be a random variable that Z = ( 1, if X = Y, 0, if X 6= Y. Now, let us consider H(X|Y ). Since H(Z|X, Y ) = 0, we have H(X|Y ) = H(X, Z|Y ) = H(Z|Y ) + H(X|Y, Z) ≤ H(Z) + H(X|Y, Z) = H(p) + pH(X|Y, Z = 0) + (1 − p)H(X|Y, Z = 1) = H(p) + pH(X|Y, Z = 0) ≤ H(p) + p log2 (|X | − 1) where the first inequality follows since conditioning does not increase entropy, and the second inequality follows by the fact that if X 6= Y then the number of possible outcomes of X is at most |X | − 1. 11.3 Source coding theorems 11.3.1 Classical source coding theorem Suppose Alice have an information source (a random variable) X that generates symbol x with proba￾bility px. For the purpose of efficient storage or transmission, she would want to encode the information using some short codes. So that when she sends the codeword to Bob, Bob can decode it and extract the information back. Ideally, Alice would want to have such a encoding and decoding scheme so that the probability that Bob can get back the symbol x is arbitrarily close to 1. Intuitively, H(X) bits seem to be sufficient since the entropy of X is just H(X). However, for any fix X, it is impossible to achieve arbitrarily small error probability if the codeword is shorter than log2 |X |. Nevertheless, if we consider the asymptotic version of this problem, i.e. Alice has n independent copies of X, namely Xn, whose generates symbol x n = x1 . . . xn with probability Qn i=1 pxi , and she want to assign a codeword for each x n so that Bob can decode the codeword to get back x n with probability tends to 1 as n → ∞. It turns out that we can achieve it with rate (defined by the length of the codeword divided by n) arbitrarily close to H(X). And moreover, it is also necessary. Theorem 11.6 (Shannon’s source coding theorem). Let Xn be n i.i.d. copies of X. Then the following holds: L11-3