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

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.