Abstract
Quantum information complexity (QIC) is one of the most powerful methods to study the lower bound on quantum communication complexity (QCC). Compressing a protocol with low QIC is a central task in communication complexity. In this talk, I will survey three recent results towards this direction. (1). There is no quantum analog of Huffman coding. (2). A quantum analog of Braverman-Rao protocol, which meanwhile gives an operational interpretation of quantum relative entropy. (3). There exists a boolean function whose QCC is exponentially larger than QIC.
The talk is based on the following three papers.
https://arxiv.org/pdf/1605.04601v1.pdf
https://arxiv.org/pdf/1404.1366v4.pdf
A.Anshu, D.Touchette, P.Yao and N.Yu. An exponential separation between quantum communication complexity and classical information complexity. (To appear)
Time
2016-12-21 14:50 ~ 15:35Speaker
Penghui Yao, University of MarylandRoom
Room 102, No.100 Wudong Road, School of Information Management & Engineering, Shanghai University of Finance & Economics
