I had asked a question similar to this one here regarding how to handle the HSP for groups whose cyclic decomposition contains factors whose order is not a power of two. I also had some prior misunderstanding that I think I worked out. It was answered that one method for approximating the QFT over arbitrary cyclic groups is from Andrew Child's notes section 4.4 (also mentioned in more detail here section 3.4) .

Method 1: To summarize the approach, this method utilizes the ability to prepare arbitrary uniform super-positions (i.e. algorithm used by Qiskit.initialize) and controlled phase-shifts to produce the operation:

$|x, 0\rangle \mapsto |x, y\rangle$, where $|y\rangle = QFT_{p^n}(|x\rangle).$ (1)

Then given the phase-estimation applied to the cyclic-shift operator, $U_{p^n}: |x\rangle \mapsto |x + 1 \rangle $, produces the operation $|0,y\rangle \mapsto |\tilde{\frac{x}{p^n}}, y\rangle$ (where $|y\rangle$ = $QFT_{p_n}(|x\rangle)$)). Multiplying the left register by $p^n$ produces:

$|0,y\rangle \mapsto |\tilde{x}, y\rangle$ (2)

and inverting this allows us to clear out the left register containing $x$ in (1), and thus approximate $QFT_{p^n}$.

However, even in a simulator, with small examples like $p^n = 9$, the multiplication operation, with the required precision, seems to be infeasible (or just takes a really long time). I implemented this, and the algorithm I used for multiplication is the modular multiplication algorithm here

Method 2: However, I found a possible alternative mentioned here (page 9), which states quote:

If we use $F^{−1}_{p^{m_j}}$we would determine $t_j$ [an element of the dual group/character] exactly,or we could use the simpler $F^{−1}_{2^{k}}$, for some $k >log_2(p^{m_j})$, and obtain $t_j$ with high probability [...] In practice we could use $F^{−1}_{2^{k}}$ for a large enough $k$ so that the probability of error is sufficiently small.

Thus it seems this is a similar approach to Shor's: apply $QFT_{2^k}$ for large enough $k$, and then apply continued fractions. However, Shor's is for the HSP in $\mathbb{Z}$. So I'm not sure how to properly apply this method to $\mathbb{Z}_{p^n}$; I just tried to use $QFT_{2^k}$, $p^{2n} < 2^k < 2p^{2n}$ like in Shor's, which didn't seem to work. There also seems to be no proof of its validity for $\mathbb{Z}_{p^n}$. The paper mentions it briefly, and there is no reference annotated. I also couldn't find this method referenced anywhere else.

So my questions are:

  1. What is the correct way to apply 'method 2' (assuming my understanding of it is correct)?
  2. Is there any known way to speed up the multiplication required for 'method 1'?

If there is an entirely other way of going about this, please feel free to mention as well. I'm trying to implement some small examples for learning purposes that are feasible on simulators.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.