A lower bound for bounded round quantum communication complexity of set disjointness

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen

We consider the class of functions whose value depends only on the intersection of the input X_1,X_2, ..., X_t; that is, for each F in this class there is an f_F: 2^{[n]} \to {0,1}…