Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem

Question

I've difficulty in understanding the last steps of the AHSP algorithm. Let $G$ be an abelian group and $f$ be the function which hides the subgroup $H$. Let $G^*$ represent the dual group of $G$.

Here are the steps of the algorithm

1. First prepare the state,

   $\qquad \displaystyle I=\frac{1}{|G|} \sum_{g \in G} |g\rangle|0\rangle$.

2. Then apply the quantum oracle which evaluates $f$ on $I$, we get

   $\qquad \displaystyle I'=\sum_{g \in G} |g\rangle|f(g)\rangle$.

3. Now measure the the second qubit of $I'$, we get

   $\qquad\displaystyle I'= \left(\frac{1}{|H|}\Sigma_{g \in H} |rh\rangle\right) \otimes |f(rh)\rangle$

   for some $r \in G$.

4. Now we apply the quantum fourier transform on the first qubit, we get

   $\qquad \displaystyle I_m = \frac{1}{|H^*|}\sum_{\chi \in H^*} |\chi\rangle$,

   where $H^*= \{\chi \in G^*: \chi(h)=1 ,\forall h \in H\}$.

Now from the state $I_m$ how can we get generators of the group $H$?

Answer 1

This classical post-processing exploits several non-trivial group theoretical properties of Abelian groups. I wrote a didactic explanation of how this classical algorithm works here [1]; other good sources to read about are [2, 3, 4].

So, measuring at the end of the algorithm in the standard basis will give you elements of $H^{*}$ uniformly at random. It is not hard to check that the set $H^{*}$ is a (finite Abelian) subgroup of the character group $G^{*}$; due to, after $O(\log{|G|})$ measurement rounds a generating set of $H^{*}$ is obtained with probability exponentially close to one.

The most technical part is how to reconstruct $H$ given a generating set of $H^{*}$. Let us focus on this problem from now on. For this, we will need some rudiments from character theory.

---

Character Theory

First of all, remember that, when $G$ is finite Abelian, characters form a group isomorphic to $G$ and that they can be written as \begin{equation} \chi_g(h)=\exp{\left(2\pi i \sum_{i=1}^{m} \frac{g(i)h(i)}{d_i}\right)}. \end{equation} The label $g$ of the character $\chi_g$ is an element of $G$. The map $g\rightarrow \chi_g$ defines an isomorphism between $G^*$ and $G$, so that we can identify both groups.

Now, given $H$, the set $H^*$ you describe is calle the orthogonal subgroup of $H$ or, depending on the source, the annihilator of $H$. This subgroup has some important mathematical properties:

1. First of all, $H^*$ is also subgroup of $G$;

2. It is dual to $H$, in the sense that, if we consider the double annihilator subgroup $H^{**}$, this subgroup is isomorphic to $H$: i.e., $H\cong H^{**}$. This guarantees that the solutions to the system of equations $$\chi_g(h)=1,\quad \textrm{ for every } g\in H^*$$ are precisely the elements of the subgroup $H$ that you want.

---

Linear Equations over Groups

Now, a key observation that we can use is the following (I will follow [1] for this part): the former systems of equations can be re-written as a ''system of linear equations over finite Abelian groups''. By that, I mean a problem where the input are to finite Abelian groups $X$, $Y$; an element $b\in Y$; a group homomorphism$ \alpha:X\rightarrow Y$ and the task is to find the solutions of the equation $$\alpha(x)=b$$ You can show that any homomorphisms can be written as a matrix $A$, in such a way that the problem above can be re-expressed as \begin{equation} A x= \begin{pmatrix} a_1(1) & a_2(1) & \cdots & a_n(1)\\ a_1(2) & a_2(2) & \cdots & a_n(2)\\ \vdots & \vdots & \cdots & \vdots\\ a_1(m) & a_2(m) & \cdots & a_n(m) \end{pmatrix} \begin{pmatrix} x(1)\\ x(2)\\ \vdots\\ x(n) \end{pmatrix} = \begin{pmatrix} b(1) \\ b(2) \\ \vdots\\ b(m) \end{pmatrix} \begin{matrix} \mod d_1\\ \mod d_2\\ \vdots\\ \mod d_m \end{matrix} = b \end{equation} where we assume $Y=\mathbb{Z}_{d_{1}}\times\cdots\times \mathbb{Z}_{d_{m}}$.

The final key observation is that there exist efficient classical algorithms to decide whether these systems admit solutions, count them and find them (we survey some in [1]). The set of solutions is always of the form $x_0+\ker{\alpha}$, where $x_0$ is a particular solution and $\ker{\alpha}$ is the kernel of $\alpha$ (a subgroup of $X$). These classical algorithms can find a particular solution of the system and compute a generating set of $\ker{\alpha}$. These classical algorithms make crucial use of Smith Normal Forms to rewrite the system in an almost diagonal form (some other intermediate steps are necessary, but that should give you the intuitive picture).

The system of equations that you obtain in your case encodes the hidden subgroup $H$. In particular is of the form $\Omega x = 0$, for some group homomorphism $\Omega$. The kernel of $\Omega$ is precisely the hidden subgroup. A particular solution in that case is 0, the trivial one.

Answer 2

After your step 4, measuring $I_m$ in the computational basis will randomly give us one $\chi \in G^*$.

We then repeat all the steps you have given $n$ times to get a list of $n$ characters in the dual group of $G$. This list of characters generates a subgroup $K$ of the dual group $G^*$.

We then check through (classically) all the possible subgroups $H$ to find one where $H^*$ is $K$.

For fixed $n$ this isn't always a unique match, so when there is degeneracy we would just pick the largest match (as the trivial subgroup will match all lists of characters).