In the hidden subgroup problem for finite Abelian groups, where does the state $\frac{1}{\sqrt{|G|}}\sum_{g\in G} |g,0\rangle$ come from?

Question

I am new to the concept of HSP. Previously, I saw how to solve hidden subgroup problem over $\mathbb{Z}_2^n$, which was Simon's algorithm. Over there the first step was to apply $H^{\otimes n}$, which was indeed the Fourier transform over $\mathbb{Z}_2^n$.

Now for any general finite abelian group, the course notes I have been following and in many other materials, the starting step is given as to form equal superposition over all the basis vectors i.e.,

$$\frac{1}{\sqrt{|G|}}\sum_{g\in G} | g,0\rangle$$

Here $G$ is the finite abelian group. The pair of register contains $|0,0\rangle$ at the beginning where the first register $|0\rangle$ means log$(|G|)$ qubits(Why?).

In case of Hadamard in Simon's algorithm it was easy to see this step, but in this case can anyone show me how do we get here? We have to apply Fourier transform I know, but the whole steps I am not getting.

Answer 1

With the Hidden Subgroup Problem, abelian or otherwise, we have a function $f$ from elements of $g\in G$ to an arbitrary set $X$, that is constant on cosets of $H\le G$ and is distinct on different cosets of $H$.

Conventionally and at a high level of abstraction, this function $f$ is described with an oracle that maps elements of $g\in G$ to elements $x\in X$. Elements $g\in G$ are described just as elements of $G$ (while elements $x\in X$ are often called colors as there may or may not be an ordering among elements of $X$).

However it can be convenient to think of $g$ as integers or bit-strings $\mathbb{Z}^n_2$, with $n=\log_2 \vert G\vert$. But then we will need to envision a bijection mapping $g$ (as abstract group elements) to/from integers/bit-strings in $\mathbb{Z}^n_2$ (as more concrete states of qubits on which we work).

One of the first steps in HSP algorithms is to prepare a first input register into the uniform superposition over all elements of $G$; later we evaluate our oracle $f$ on the second output register representing elements of $X$.

Hence once we can conceptualize the inputs $g$ as integers/bit-strings, this can be accomplished in a straightforward manner, by performing Hadamard transforms on the input qubits.

This works for nonabelian groups too. For example in the symmetric group $S_n$, elements $g\in S_n$ may be permutations $\pi$. So a first step would be to find a good bijection between integers in $[n!]$ and elements of $S_n$, that enables evaluation of an oracle $f$ into the second register. I believe (although I've not studied it too much) that there are many efficiently-evaluated bijections between integers in $[n!]$ and permutations $\pi\in S_n$.