Nijmegen Quantum Logic Group

home people seminar

Information cost of quantum communication protocols

01 Mar 2016 [ journal (QIC) · prequel ]

We study the notion of information cost in the quantum world.

In two-party quantum communication complexity, Alice and Bob receive some classical inputs and wish to compute some function that depends on both these inputs, while minimizing the communication. This model has found numerous applications in many areas of computer science. One notion that has received a lot of attention recently is the information cost of the protocol, namely how much information the players reveal about their inputs when they run the protocol. In the quantum world, it is not straightforward to define a notion of quantum information cost. We study two different notions and analyze their relation. We also provide new quantum protocols for the Inner Product function and for Private Information Retrieval, and show that protocols for Private Information Retrieval whose classical or quantum information cost for the user is zero can have exponentially different information cost for the server.