Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states

Abstract

We prove a fundamental theorem about the relative entropy of quantum states, which roughly states that if the relative entropy, S(ρ||σ)Δ=Tr ρ(log ρ-log σ), of two quantum states ρ and σ is at most c, then ρ/2^O(c) 'sits inside' σ. Using this 'substate' theorem, we give tight lower bounds for the privacy loss of bounded error quantum communication protocols for the index function problem. We also use the 'substate' theorem to give tight lower bounds for the k-round bounded error quantum communication complexity of the pointer chasing problem, when the wrong player starts, and all the log n bits of the kth pointer are desired.