  We establish a general method for proving bounds on the information that can
be extracted via arbitrary entangled measurements on tensor products of hidden
subgroup coset states. When applied to the symmetric group, the method yields
an Omega(n log n) lower bound on the number of coset states over which we must
perform an entangled measurement in order to obtain non-negligible information
about a hidden involution. These results are tight to within a multiplicative
constant and apply, in particular, to the case relevant for the Graph
Isomorphism problem.
  Part of our proof was obtained after learning from Hallgren, Roetteler, and
Sen that they had obtained similar results.
