  Part I of this paper showed that the hidden subgroup problem over the
symmetric group--including the special case relevant to Graph
Isomorphism--cannot be efficiently solved by strong Fourier sampling, even if
one may perform an arbitrary POVM on the coset state. In this paper, we extend
these results to entangled measurements. Specifically, we show that the hidden
subgroup problem on the symmetric group cannot be solved by any POVM applied to
pairs of coset states. In particular, these hidden subgroups cannot be
determined by any polynomial number of one- or two-register experiments on
coset states.
