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.

  • 1
    $\begingroup$ I highly suggest you take a look at Andrew Childs notes on Quantum Algorithms cs.umd.edu/~amchilds/qa in particular in section 4.4 he shows how you can use phase estimation to compute the QFT (at least approximately) for an arbitrary abelian group, in particular how to do it for $\mathbb{Z}_N$. In fact the answer to your question may even lie in section 6.2. $\endgroup$ – Condo Sep 29 '20 at 19:37
  • $\begingroup$ This was very helpful. I think my confusion was thinking too much in terms of Shor's which is really for $\mathbb{Z}$. However, I really need to implement an approximation for the QFT over $\mathbb{Z}_N$. I also found this which seems helpful arxiv.org/abs/quant-ph/0212002. $\endgroup$ – dylan7 Sep 29 '20 at 21:40
  • $\begingroup$ However, I noticed that the approximations require implementing a uniform superposition over $\mathbb{Z}_N$ for N not a power of 2. I did some research, and I don't see any suggestions on how to do this. This is the closest thing I found :quantumcomputing.stackexchange.com/q/2310/8765. Is there a circuit for doing this for arbitrary $N$? Unless it's obvious, and I'm missing something. $\endgroup$ – dylan7 Sep 29 '20 at 23:34
  • $\begingroup$ I think you misread section 4.4. Childs notes that the circuit in section 4.2 only works for $N$ a power of $2$. But then (in the next sentence) he claims that phase estimation can realize the QFT for $\mathbb{Z}_N$ (approximately) using phase estimation. I would also like to mention that one can prepare a superposition over the states of any group $G$ simply using $\log|G|$ qubits. $\endgroup$ – Condo Sep 30 '20 at 12:51
  • $\begingroup$ So in regards to you comment "that one can prepare a superposition over the states of any group $𝐺$ simply using $log|𝐺|$ qubits". I couldn't find how this is typically done, but I'm guessing it's something along the lines of scaling up what was mentioned: quantumcomputing.stackexchange.com/q/2310/8765 . I did read section 4.4 (maybe I misunderstood parts), and I thought creating a superposition of the states of $G$ might be required. $\endgroup$ – dylan7 Sep 30 '20 at 22:26

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.


Your Answer

