What is the intuitive reason for why Abelian HSPs are much easier than Non-Abelian HSPs?

Question

I think I roughly understand the quantum algorithm for the general Abelian Hidden Subgroup Problem (HSP). We begin by constructing a uniform superposition, calculating the function over that superposition in another register, then measure it to yield a coset state (i.e. a state whose nonzero components all lie in the same coset). Applying the Quantum Fourier Transform will then yield an element that is "orthogonal," or in the kernel, of the hidden subgroup. Repeating this only polynomially many times, we can be certain with arbitrarily high probability that we have produced the hidden subgroup.

My question is, where does this go wrong for non-Abelian subgroups? And what exactly about being Abelian is so important for this algorithm to work correctly? If someone could provide an intuitive explanation, that would be even better! Thanks.

Answer 1

I will begin by saying that first of all the HSP quantum algorithm works on any group, regardless of whether it is abelian or not. The problem is that when the group is not abelian (or the hidden subgroup isn't normal), the algorithm fails to find a description of the hidden subgroup in a polynomial number of steps.

Now, in an abelian group, each element composes its conjugacy class and therefore the group elements are in one-to-one correspondence with the characters (functions on the group). So near the end of the algorithm for HSP, in an abelian group when we measure after applying the QFT we always get a character with the desired kernel, and we can show that repeating this sampling always gets us a description of the hidden subgroup in a polynomial number of steps. However, in a non-abelian group, the characters are no longer in one-to-one correspondence with the elements (because the conjugacy classes are no longer singletons) and so it's not clear how to obtain an efficient polynomial time sampling routine to get the description of the subgroup.

This sampling I've mentioned is known in the literature as weak Fourier sampling. The idea is that weak Fourier sampling is sufficient to deduce the structure of the hidden subgroup in certain cases (like when the group is abelian), however, it is known to fail for HSP in non-abelian groups like the symmetric group.

The notes on Quantum Algorithms by Andrew Childs (https://www.cs.umd.edu/~amchilds/qa/) seem to be the most detailed on this subject if you are interested in reading more.