Appears in collection : 2017 - T3 - WS3 - Quantum information theory

The information cost trade-off for Augmented Index in two party _classical_ communication protocols has been studied by several authors, due to its connection to streaming algorithms. Rahul Jain and I proved such a trade-off with techniques inspired by works in quantum communication complexity. We also explored notions of _quantum_ information cost, but fell short of an analogous result for quantum protocols. In this talk, we will see work with Dave Touchette on the topic. We show that the notion of quantum information cost introduced by Touchette is both powerful enough to capture the connection to streaming algorithms, _and_ supple enough to admit a strong information cost trade-off.