# Why does Fourier sampling allow to efficiently recover hidden subgroups?

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?

• A reference: arxiv.org/abs/quant-ph/0411037 It looks like you want the classical post processing part after you measure the representation $\rho$ from a state with amplitudes depending on $H$. – AHusain Oct 18 '18 at 19:59

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.