Apparaît dans la collection : 2017 - T3 - WS3 - Quantum information theory

In this talk, we will consider memoryless quantum communication protocols, where the two parties do not possess any memory besides their classical input and they take turns performing unitary operations on a pure quantum state that they exchange between them. Most known quantum protocols are of this type and recently a deep connection between memoryless protocols and Bell inequality violations has been explored by Buhrman et al (2016). We study the information cost of such protocols by looking at a canonical problem: bounded-round quantum communication for the one-bit AND function. We prove directly a tight lower bound of Theta (log(k) / k ) for the information cost of AND for k-round memoryless quantum protocols and for the input distribution needed for the Disjointness function.