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

Jain, R. ; Radhakrishnan, J. ; Sen, P. (2002) Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states Proceedings - Annual Symposium on Foundations of Computer Science . pp. 429-438. ISSN 0272-5428

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...

Related URL: http://dx.doi.org/10.1109/SFCS.2002.1181967

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 ρ/2O(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.

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:89509
Deposited On:27 Apr 2012 13:38
Last Modified:27 Apr 2012 13:38

Repository Staff Only: item control page