Some Recent Progress on Quantum Information Complexity (Penghui Yao)


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.

A.Anshu, D.Touchette, P.Yao and N.Yu. An exponential separation between quantum communication complexity and classical information complexity. (To appear)


2016-12-21   14:50 ~ 15:35   


Penghui Yao, University of Maryland


Room 102, No.100 Wudong Road, School of Information Management & Engineering, Shanghai University of Finance & Economics