4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – AHusain Oct 18 '18 at 19:59
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.