01168nas a2200133 4500008004100000245004200041210004200083260001400125520078800139100001900927700002200946700002300968856004300991 2005 eng d00aStrong Fourier Sampling Fails over Gn0 aStrong Fourier Sampling Fails over Gn c11/7/20053 a
We present a negative result regarding the hidden subgroup problem on the powers Gn of a fixed group G. Under a condition on the base group G, we prove that strong Fourier sampling cannot distinguish some subgroups of Gn. Since strong sampling is in fact the optimal measurement on a coset state, this shows that we have no hope of efficiently solving the hidden subgroup problem over these groups with separable measurements on coset states (that is, using any polynomial number of single-register coset state experiments). Base groups satisfying our condition include all nonabelian simple groups. We apply our results to show that there exist uniform families of nilpotent groups whose normal series factors have constant size and yet are immune to strong Fourier sampling.
1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/0511054