Constructing arbitrary functions for the Abelian HSP

Question

My question might be similar to Hidden subgroup problem. However, I'm not exactly sure though. In addition, that question doesn't have an answer.

I'm trying to create some simple instances of the general abelian hidden subgroup problem to experiment with for learning purposes. This requires solving the following simpler (for small groups) 'reverse' problem:

Suppose we have a finite abelian group $G$. In addition, we have an arbitrary subgroup $H$. Find a function, $f_H : G \to S$, for some set $S$. In addition, $f_H$ is constant, and for simplicity distinct on the cosets of $H$.

I know that WLOG, we can assume $G \ge H$ is such that $G \cong \mathbb{Z}_{p^{k_1}} \oplus \mathbb{Z}_{p^{k_2}} \dots \oplus \mathbb{Z}_{p^{k_n}}$, for the same $p$. Since the abelian HSP, and thus the problem I mentioned above, can be solved separately for the relatively prime components.

My question is about when $p$ is not a power of $2$. In which can we need to instead look at $G' \cong \mathbb{Z}_{2^{r_1}} \oplus \mathbb{Z}_{2^{r_2}} \dots \oplus \mathbb{Z}_{2^{r_n}}$ where for each $k_i$, $p^{2k_{i}} \le 2^{r_i} \le 2p^{2k_{i}}$, and use the continued fractions algorithm. Given, $f_H$ for $G$ ($G \ge H$), how do we extend the support of $f_H$ to $G'$ such that we can still sample from the dual of $H$?

In the case of the order-finding/Shor's function with support $\mathbb{Z}_{\phi(N)}$ ($\phi$ is Euler's totient function), the support of $f(x) = a^k mod N$ can be naturally extended from $\mathbb{Z}_{\phi(N)}$ to $\mathbb{Z}_N$ and then $\mathbb{Z}_{2^k}$, $N^2 \le 2^k \le 2N^2$. Also Shor proved the extension is valid for this function. But what about an arbitrary $f_H$?

The set of functions I'm looking at are ones that simply assign a distinct natural number to each coset.

I was thinking something like given $f_H$ as above extend to $f'_H$:

$\quad f'_H((x_1, x_2, \dots, x_n)) = f_H((x_1 mod \mathbb{Z}_{p^{k_1}}, x_2 mod \mathbb{Z}_{p^{k_2}}, \dots, x_n mod \mathbb{Z}_{p^{k_n}}))$, $(x_1, x_2, \dots, x_n) \in \mathbb{Z}_{2^{r_1}} \oplus \mathbb{Z}_{2^{r_2}} \dots \oplus \mathbb{Z}_{2^{r_n}}$.

This doesn't seem to work; I'm not sure it actually makes sense.

Any ideas?

Update I realized I might be misunderstanding something. It seems like the setup is supposed to be the following: create a uniform superposition of the states of $G$, not $G'$, as I stated above. In which case we can apply $f_H$, as is. However, we still utilized the QFT of $G'$, which can be efficiently implemented. This seems to work for small groups, but it doesn't seem to be feasible to construct an arbitrary uniform superposition of a subset of all basis states, which is what we would need. To do this exactly, would require, to my knowledge, implementing the QFT for $G$ (or QFT for $\mathbb{Z}_r$ for arbirary $r$), which we can't do. I assume for small groups, this could be done through multiple applications of Grover to get an approximate uniform superposition.

Since, as mentioned here https://arxiv.org/pdf/quant-ph/0603140.pdf, the order-finding/Shor's function is somewhat of a special case. Since in Shor's we are actually dealing with free-abelian groups of finite rank (not finite), as the paper mentions.

I'm still not sure if this is correct. If it is, I'm not sure of an efficient way of implementing such superpositions.

Please let me know if anything isn't clear with my question.

Answer 1

I am not sure if this anwers your question but I think this all boils down to whether one can we efficiently implement $QFT_{\mathbb{Z}_N}$ when $N$ is not a power of $2$. In this case we can no longer implement the $QFT$ using the standard gate construction one sees often. However, for any $N$ we can approximately implement $QFT_{\mathbb{Z}_N}$ using the following trick (from section 4.4 of Andrew Childs notes).

Recall that $$F_N:=\frac{1}{\sqrt{N}}\sum_{x,y\in Z_N}\omega_N^{xy} |y\rangle \langle x|$$ is the QFT for $\mathbb{Z}_N$. Now, introduce the cyclic shift operator $$U:=\sum_{x\in Z_n} |{x+1}\rangle\langle x|,$$ and note that the eigenstates of $U$ are the basis for the the $QFT$, since $$F^*_NUF_N=\sum_{x\in \mathbb{Z}_N} (\omega^{x}_N)^{-1}|x\rangle\langle x|.$$ Then running phase estimation with on the unitary operator $U$ with $n=O(\log N)$ qubits performs the transformation $$|\tilde{x}\rangle |0\rangle \mapsto |\tilde{x}\rangle |\widetilde{(\omega^{x}_N)^{-1}}\rangle,$$ where $|\tilde{x}\rangle$ is an eigenstate of $U$, and $\widetilde{(\omega^{x}_N)^{-1}}$ is an $n$-bit approximation of the eigenvalue corresponding to $|\tilde{x}\rangle$. Now observe that if we run the circuit in reverse, we can effectively remove the undesired phase from the eigenstates of $U$, leaving us with the same states that would be output by the transformation $F_N$. Because the phase estimation algorithm is efficient i.e. $O(poly(n))$, it follows that this method is efficient with complexity $O(poly(\log N))$.

With this method in hand one can decompose any abelian group into a product of such cyclic groups and use this approach on each factor (see section 6 of Childs notes). This is the essence of how one could use a quantum computer to solve the discrete log problem (a variant of hidden subgroup) for a general abelian group.