The Symmetric Group Defies Strong Fourier Sampling: Part I

Cristopher Moore, Alexander Russell, Leonard J. Schulman

We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem. Specifically, we show that the hidden subgroup problem over the symmetric gro…