Sean Hallgren

A Quantum Algorithm for Computing Some Hidden Subgroups of the Symmetric Group

An important open question in quantum algorithms is whether the ``standard method'' can be used to solve graph isomorphism. This refers to the algorithm that is the generalization of Simon's and Shor's algorithms from abelian groups to the symmetric group $S_n$, and the goal is to compute which subgroup of $S_n$ arises in the reduction from graph isomorphism. The difficulty is that the main step, computing the quantum Fourier transform over $S_n$, is not uniquely defined, as it depends on a basis choice for each representation of $S_n$, and there are an infinite number of choices. The main known result about this algorithm is negative and states that under a random basis the Fourier sampling statistics reveal an exponentially small amount of information about the hidden subgroup. In this paper we give the first positive result by presenting subgroups which can be distinguished by choosing special bases. For example, we show that there are special bases that can be used to distinguish certain exponentially large sets of small conjugate subgroups of the symmetric group, in quantum polynomial-time.