TY - JOUR T1 - Strong Fourier Sampling Fails over Gn Y1 - 2005 A1 - Gorjan Alagic A1 - Cristopher Moore A1 - Alexander Russell AB -

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.

UR - https://arxiv.org/abs/quant-ph/0511054 ER -