Some Recent Progress on Quantum Information Complexity (Penghui Yao)

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

Speaker

Room