Now consider the quantity S(P;Q).It is clear that S(P;Q)=S(P;Q,M)since M is independent of P and Q.We also have S(P;Q,M)>S(P';Q',M')since the measurement only apply to the system QM,it does not increase the mutual information between P and QM.Finally observe that S(P;Q',M)>S(P;M')since discarding system does not increase mutual information.So we have the inequality S(P:Q)≥S(P';M'). We claim that S(P;M)=I(X;Y)and S(P;Q)=S(p)-pS(pz).The first one follows by the fact pp=∑Pzl⑧∑Pkl刨=Pzgl⑧l)刨 工，y For the second one,by definition we have S(P;Q)=S(pp)+S(pQ)-S(ppo).Observe that S(pp)= H(X),S(po)=S(p)and by the inequality for von Neumann entropy,we have S(ppQ)=H(X)+ pS(p).Putting all together yields the equality S(P:Q)-S(p)-PS(p)and hence complete the proof. 11.2 Application:quantum random access codes The Holevo's bound says that sending n bits of classical information requires n qubits.However,in some cases we are not very interested in knowing every bit of X(for instance when we are querying some entries in a database).Note that Holeve's bound does not say we need many qubits as I(X;Yi)is small(which is at most 1)for each fixed i.Classically,it is known that the codeword must have at least (1-H())m bits where m is the length of the original message and s is the success probability (this bound is almost tight as there exists classical random access code of length (1-H())m+O(log m)). Can we do better using quantum mechanics?It turns out that the answer is no.Nayak gave a very simple proof using Holevo's bound.First let us define what a quantum random access code is. Definition 11.2 (Quantum random access code).Let m,n be positive integers,>0,a (m,n,s)- quantum random access code is a function C that maps a m-bit string to a quantum state of dimension 2n such that for each 1 i<m,there exists a measurement {Mo,MI}such that the probability that the measurement outcome is b is at least s when the i-th bit of the string is b. Theorem 11.3 (Nayak's bound).Let eE [1/2,1],if (m,n,e)-quantum random access code erists,then n2(1-H(e)m. Proof.We use the following lemma,which follows from Holevo's bound and Fano's inequality: Lemma 11.4.Let p=(po +p1),if there erists measurement {Mo,Mi}such that Tr(Mopu)>EE [1/2,1],them S(p)(1-H(e))+(S(po)+S(p)). Now,suppose we have a(m,n,s)-quantum random access code.Let pr be the encoding of x and =(po+pi)where pP.By the definition of quantum random access code,there exists measurement {M,MI}such that for every Pa with xi =b,we have Tr(MoP)>E. It follows by the linearity of trace that Tr(Mbpb)>.So by Lemma 11.4,we have S(p)>(1-H(e))+ (S(Po)+S(p1)).And it is not difficult to see po still satisfy the condition of Lemma 11.4 and we have Sp)≥21-He》+1(SpPo)+S(po)+S(po)+Sp》 and by induction we have S(p)>m(1-H(e))+S(pb)>m(1-H(e)),as desired. L11-2Now consider the quantity S(P; Q). It is clear that S(P; Q) = S(P; Q, M) since M is independent of P and Q. We also have S(P; Q, M) ≥ S(P 0 ; Q0 , M0 ) since the measurement only apply to the system QM, it does not increase the mutual information between P and QM. Finally observe that S(P 0 ; Q0 , M0 ) ≥ S(P 0 ; M0 ) since discarding system does not increase mutual information. So we have the inequality S(P; Q) ≥ S(P 0 ; M0 ). We claim that S(P 0 ; M0 ) = I(X; Y ) and S(P; Q) = S(ρ)− P x pxS(ρx). The first one follows by the fact ρP 0M0 = X x px|xihx| ⊗X y py|x|yihy| = X x,y px,y|xihx| ⊗ |yihy|. For the second one, by definition we have S(P; Q) = S(ρP ) + S(ρQ) − S(ρP Q). Observe that S(ρP ) = P H(X), S(ρQ) = S(ρ) and by the inequality for von Neumann entropy, we have S(ρP Q) = H(X) + x pxS(ρx). Putting all together yields the equality S(P; Q) = S(ρ) − P x pxS(ρx) and hence complete the proof. 11.2 Application: quantum random access codes The Holevo’s bound says that sending n bits of classical information requires n qubits. However, in some cases we are not very interested in knowing every bit of X (for instance when we are querying some entries in a database). Note that Holeve’s bound does not say we need many qubits as I(X; Yi) is small (which is at most 1) for each fixed i. Classically, it is known that the codeword must have at least (1 − H(ε))m bits where m is the length of the original message and ε is the success probability (this bound is almost tight as there exists classical random access code of length (1 − H(ε))m + O(log m)). Can we do better using quantum mechanics? It turns out that the answer is no. Nayak gave a very simple proof using Holevo’s bound. First let us define what a quantum random access code is. Definition 11.2 (Quantum random access code). Let m, n be positive integers, ε > 0, a (m, n, ε)- quantum random access code is a function C that maps a m-bit string to a quantum state of dimension 2n such that for each 1 ≤ i ≤ m, there exists a measurement {M0 i , M1 i } such that the probability that the measurement outcome is b is at least ε when the i-th bit of the string is b. Theorem 11.3 (Nayak’s bound). Let ε ∈ [1/2, 1], if (m, n, ε)-quantum random access code exists, then n ≥ (1 − H(ε))m. Proof. We use the following lemma, which follows from Holevo’s bound and Fano’s inequality: Lemma 11.4. Let ρ = 1 2 (ρ0 + ρ1), if there exists measurement {M0, M1} such that Tr(Mbρb) ≥ ε ∈ [1/2, 1], then S(ρ) ≥ (1 − H(ε)) + 1 2 ￾ S(ρ0) + S(ρ1)
. Now, suppose we have a (m, n, ε)-quantum random access code. Let ρx be the encoding of x and ρ = P x 1 2m ρx = 1 2 (ρ0 + ρ1) where ρb = P x:x1=b 1 2m−1 ρx. By the definition of quantum random access code, there exists measurement {M0 1 , M1 1 } such that for every ρx with x1 = b, we have Tr(Mbρx) ≥ ε. It follows by the linearity of trace that Tr(Mbρb) ≥ ε. So by Lemma 11.4, we have S(ρ) ≥ (1 − H(ε)) + 1 2 ￾ S(ρ0) + S(ρ1)
. And it is not difficult to see ρb still satisfy the condition of Lemma 11.4 and we have S(ρ) ≥ 2(1 − H(ε)) + 1 4 ￾ S(ρ00) + S(ρ01) + S(ρ10) + S(ρ11)
, and by induction we have S(ρ) ≥ m(1 − H(ε)) + 1 2m P b S(ρb) ≥ m(1 − H(ε)), as desired. L11-2