Given a finite Abelian group $G = \prod_{j=1}^n \mathbb{Z}_{m_j}$ with $m_j \geq 2$ and a function $h: G \to \mathbb{C}$ that is $s$-periodic. I have already proven that for all $\xi \in G$ we have $\hat h(\xi) = e^{2\pi i s \bullet \xi} \hat h(\xi)$, where $s \bullet \xi$ is an abbreviation for $\sum_{j=1}^n \frac{s_j\xi_j}{m_j}$. I now need to use this fact to construct a classical algorithm that could be used to find the period of $h$ given by oracle access.

I am aware of the cases for $Z_2^n $ where the best classical algorithm uses $O(\sqrt{N})$ steps where $N = 2^n$ and for $Z_N$. Can anybody point me to a right direction to how to approach this problem in the case of arbitrary $G$ using a classical approach with FFT instead of a quantum algorithm?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.