Why does Fourier sampling allow to efficiently recover hidden subgroups?

Question

The hidden subgroup problem is often cited as a generalisation of many problems for which efficient quantum algorithms are known, such as factoring/period finding, the discrete logarithm problem, and Simon's problem.

The problem is the following: given a function $f$ defined over a group $G$ such that, for some subgroup $H\le G$, $f$ is constant over the cosets of $H$ in $G$, find $H$ (through a generating set). In this context, $f$ is given as an oracle, which means that we don't care about the cost of evaluating $f(x)$ for different $x$, but we only look at the number of times $f$ must be evaluated.

It is often stated that a quantum computer can solve the hidden subgroup problem efficiently when $G$ is abelian. The idea, as stated for example in the wiki page, is that one uses the oracle to get the state $\lvert gH\rangle\equiv\sum_{h\in H} \lvert gh\rangle$ for some $g\in G$, and then the QFT is used to efficiently recover from $\lvert gH\rangle$ a generating set for $H$.

Does this mean that sampling from $\operatorname{QFT}\lvert gH\rangle$ is somehow sufficient to efficiently reconstruct $H$, for a generic subgroup $H$? If yes, is there an easy way to see how/why, in the general case?

Answer 1

The question is whether taking the Fourier transform $\operatorname{QFT}|gH\rangle$ followed by sampling allows to efficiently recover generators of the hidden subgroup $H\leq G$. While the problem is wide open for non-abelian groups (see this paper for a discussion of the limitations of the Fourier sampling method for instances in case of $G=S_n$, $G=PSL(2,\mathbb{F}_q)$ and other non-abelian groups), for abelian groups $G$ the PO is correct that Fourier sampling solves the abelian hidden subgroup problem.

The basic idea is to perform several measurements $\operatorname{QFT}|gH\rangle$ and to note that a result $z$ can be sampled if and only if $z\in H^\perp$ holds, where $H^\perp = \{ g \in G : \chi_g(h)=1 \; \forall h \in H\}$. Here we (non-canonically) identified the characters $\chi \in \hat{G}$ with the elements of $G$ (which is possible if and only if $G$ is abelian). One can prove that doing this procedure $\log^2(|G|)$ times will with constant probability uniquely characterize $H$ from the measurement results $z_1, z_2, \ldots$.

What is more, if the group $G$ is explicitly known (i.e., one knows an isomorphism to a direct product of cyclic groups), then one can efficiently compute $H$ from $H^\perp$ using classical post-processing which essentially is linear algebra. A good reference for this is Brassard and Hoyer. If the group $G$ is abelian, but the structure is not known, then one can first discover the structure of $G$ and then find $H$ in a subsequent step. This was described in Cheung and Mosca. However, all this assumes at a minimum that $G$ has the structure of a black-box group with unique encoding. As shown by Ivanyos et al, even in case of non-unique encodings, one can recover the hidden subgroup, provided certain additional assumptions hold such as the existence of oracles for identity and membership test.