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 that you have read and understand our privacy policy and code of conduct.