2005/01/12 by Cristopher Moore, Alexander Russell, Moore, Cristopher +3
Computer Science · #Bayesian Methods and Mixture Models #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Face and Expression Recognition #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.quant-ph/0501056
openalex publication_date 2005/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 group cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. Our results apply to the special case relevant to the Graph Isomorphism problem.