<p>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 <a href="http://www.google.de/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;sqi=2&amp;ved=0CCAQFjAA&amp;url=http%3A%2F%2Farxiv.org%2Fabs%2F1210.3637&amp;ei=je_IU6mDHqHk4QSc04DgCA&amp;usg=AFQjCNENQ3VoHCYPqSkSQpb_PWvCtQtsSQ&amp;sig2=aKgejGGsMb03WVbjvyapdg&amp;bvm=bv.71198958,d.bGE" rel="nofollow">here [1]</a>; other good sources to read about are [<a href="http://arxiv.org/abs/quantph/0411037" rel="nofollow">2</a>, <a href="http://arxiv.org/abs/0812.0380" rel="nofollow">3</a>, <a href="http://arxiv.org/abs/1201.4867" rel="nofollow">4</a>].</p>

<p>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.</p>

<p>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.</p>

<hr>

<p><strong>Character Theory</strong></p>

<p>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.</p>

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

<ol>
<li><p>First of all, $H^*$ is also subgroup of $G$; </p></li>
<li><p>It is <strong>dual</strong> 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.</p></li>
</ol>

<hr>

<p><strong>Linear Equations over Groups</strong></p>

<p>Now, a <strong>key observation</strong> that we can use is the following (I will follow  <a href="http://www.google.de/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;sqi=2&amp;ved=0CCAQFjAA&amp;url=http%3A%2F%2Farxiv.org%2Fabs%2F1210.3637&amp;ei=je_IU6mDHqHk4QSc04DgCA&amp;usg=AFQjCNENQ3VoHCYPqSkSQpb_PWvCtQtsSQ&amp;sig2=aKgejGGsMb03WVbjvyapdg&amp;bvm=bv.71198958,d.bGE" rel="nofollow">[1]</a> for this part): the former systems of equations can be re-written as a ''<em>system of linear equations over finite Abelian groups</em>''. 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) &amp; a_2(1) &amp; \cdots &amp; a_n(1)\\
a_1(2) &amp; a_2(2) &amp; \cdots &amp; a_n(2)\\
\vdots &amp; \vdots &amp; \cdots &amp; \vdots\\
a_1(m) &amp; a_2(m) &amp; \cdots &amp; 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}}$. </p>

<p>The final key observation is that there exist <strong>efficient classical algorithms</strong> to decide whether these systems admit solutions, count them and <em>find them</em> (we survey some in <a href="http://www.google.de/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;sqi=2&amp;ved=0CCAQFjAA&amp;url=http%3A%2F%2Farxiv.org%2Fabs%2F1210.3637&amp;ei=je_IU6mDHqHk4QSc04DgCA&amp;usg=AFQjCNENQ3VoHCYPqSkSQpb_PWvCtQtsSQ&amp;sig2=aKgejGGsMb03WVbjvyapdg&amp;bvm=bv.71198958,d.bGE" rel="nofollow">[1]</a>). 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 <a href="http://www.google.de/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;ved=0CCIQFjAA&amp;url=http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSmith_normal_form&amp;ei=yvbIU5T3OImQ4gSrxIGgBg&amp;usg=AFQjCNGZnnnG5rMEDLTYmiwsBoQcK5fN5A&amp;sig2=4yI42tTFkTUSv1BWv9g7Tg&amp;bvm=bv.71198958,d.bGE" rel="nofollow">Smith Normal Forms</a> to rewrite the system in an almost diagonal form (some other intermediate steps are necessary, but that should give you the intuitive picture).</p>

<p>The system of equations that you obtain in your case encodes the <strong>hidden subgroup</strong> $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.</p>

CC BY-SA 3.0
2014-07-18T10:31:51.623Z
2014-07-19T13:18:42.547Z
2014-07-19T13:18:42.547Z
Juan Bermejo Vega
<p>After your step 4, measuring $I_m$ in the computational basis will randomly give us one $\chi \in G^*$.</p>

<p>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^*$.</p>

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

<p>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).</p>

CC BY-SA 3.0
2014-07-17T15:24:30.973Z
2014-07-17T15:24:30.973Z
W. J. Zeng
<p>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$.</p>

<p>Here are the steps of the algorithm </p>

<ol>
<li><p>First prepare the state, </p>

<p>$\qquad \displaystyle I=\frac{1}{|G|} \sum_{g \in G} |g\rangle|0\rangle$.</p></li>
<li><p>Then apply the quantum oracle which evaluates $f$ on $I$, we get </p>

<p>$\qquad \displaystyle I'=\sum_{g \in G} |g\rangle|f(g)\rangle$.</p></li>
<li><p>Now measure the the second qubit of $I'$, we get </p>

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

<p>for some $r \in G$.</p></li>
<li><p>Now we  apply the quantum fourier transform on the first qubit, we get </p>

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

<p>where $H^*= \{\chi \in G^*: \chi(h)=1 ,\forall h \in H\}$.</p></li>
</ol>

<p>Now from the state $I_m$ how can we get generators of the group $H$?</p>

CC BY-SA 3.0
2014-07-19T13:32:59.473Z
I strongly recommend reading Andrew Childs' lecture notes on AHSP. They're available at http://www.math.uwaterloo.ca/~amchilds/teaching/w13/qic823.html
Robin Kothari
<ds.algorithms><quantum-computing><gr.group-theory>
Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem
user774025
# Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem

(Asked by: username_0 on 2013-09-15)

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$?

**Tags:** ds.algorithms, quantum-computing, gr.group-theory

> **Comments:**
> **username_1**: I strongly recommend reading Andrew Childs' lecture notes on AHSP. They're available at http://www.math.uwaterloo.ca/~amchilds/teaching/w13/qic823.html  

---

## 2 answers

### Answer by username_2 on 2014-07-18. Score: 6

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]](http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&sqi=2&ved=0CCAQFjAA&url=http%3A%2F%2Farxiv.org%2Fabs%2F1210.3637&ei=je_IU6mDHqHk4QSc04DgCA&usg=AFQjCNENQ3VoHCYPqSkSQpb_PWvCtQtsSQ&sig2=aKgejGGsMb03WVbjvyapdg&bvm=bv.71198958,d.bGE); other good sources to read about are [[2](http://arxiv.org/abs/quantph/0411037), [3](http://arxiv.org/abs/0812.0380), [4](http://arxiv.org/abs/1201.4867)].

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]](http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&sqi=2&ved=0CCAQFjAA&url=http%3A%2F%2Farxiv.org%2Fabs%2F1210.3637&ei=je_IU6mDHqHk4QSc04DgCA&usg=AFQjCNENQ3VoHCYPqSkSQpb_PWvCtQtsSQ&sig2=aKgejGGsMb03WVbjvyapdg&bvm=bv.71198958,d.bGE) 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]](http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&sqi=2&ved=0CCAQFjAA&url=http%3A%2F%2Farxiv.org%2Fabs%2F1210.3637&ei=je_IU6mDHqHk4QSc04DgCA&usg=AFQjCNENQ3VoHCYPqSkSQpb_PWvCtQtsSQ&sig2=aKgejGGsMb03WVbjvyapdg&bvm=bv.71198958,d.bGE)). 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](http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCIQFjAA&url=http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSmith_normal_form&ei=yvbIU5T3OImQ4gSrxIGgBg&usg=AFQjCNGZnnnG5rMEDLTYmiwsBoQcK5fN5A&sig2=4yI42tTFkTUSv1BWv9g7Tg&bvm=bv.71198958,d.bGE) 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 by username_3 on 2014-07-17. Score: 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).


---

