loading...
Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States
Vancouver, BC, Canada November 16-November 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181967The 43rd Annual IEEE Symposium on Fou ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Rahul Jain, STCS, Tata Institute of Fundamental Research
Jaikumar Radhakrishnan, STCS, Tata Institute of Fundamental Research
Pranab Sen, Université de Paris-Sud
We prove a fundamental theorem about the relative entropy of quantum states, which roughly states that if the relative entropy, S(\rho \left\| \sigma \right.) \triangleq Tr \rho (\log \rho - \log \sigma ), of two quantum states \rho and \sigma is at most c, then \frac{\rho }{{2^0 (c)}} ?sits inside? \sigma. 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.
Citation:
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen, "Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States," focs, pp.429, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.