  We present a new example of a partial boolean function whose one-way quantum
communication complexity is exponentially lower than its one-way classical
communication complexity. The problem is a natural generalisation of the
previously studied Subgroup Membership problem: Alice receives a bit string x,
Bob receives a permutation matrix M, and their task is to determine whether
Mx=x or Mx is far from x. The proof uses Fourier analysis and an inequality of
Kahn, Kalai and Linial.

Quantum Physics;Computational Complexity