# Quantum Fourier Transform for general cyclic groups

The QFT on the group $$\mathbb{Z}_N$$ is given by $$\begin{equation} QFT\,|k\rangle =\frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} e^{2\pi i\,jk/N}|j\rangle\,. \end{equation}$$

The usual circuit implements the QFT with $$N=2^n$$ on $$n$$ qubits. Does anyone know how to realize this transformation when $$N$$ is not a power of 2? I have found an algorithm that approximates a QFT with arbitrary $$N$$, but I would like to find out if some exact circuit is known. I think that it should at least in some cases, since the problem 5.1 of Nielsen and Chuang's book is to find it when $$N=p$$ is a prime number.

I'm interested in particular on the $$\mathbb{Z}_3$$ transform, which corresponds to the matrix $$\begin{equation} \frac{1}{\sqrt{3}}\,\begin{pmatrix} 1&1&1 \\ 1&e^{2\pi i/3}&e^{-2\pi i/3} \\ 1&e^{-2\pi i/3}&e^{2\pi i/3} \end{pmatrix}\,. \end{equation}$$

Of course it acts on a 3d space, so to realize it using qubits we should extend it to a unitary operator on at least a $$2^2$$ dimensional Hilbert space. One possibility could be

$$\begin{equation} \begin{pmatrix} \frac{1}{\sqrt3 } \begin{pmatrix} 1&1&1 \\ 1&e^{2\pi i/3}&e^{-2\pi i/3} \\ 1&e^{-2\pi i/3}&e^{2\pi i/3} \end{pmatrix} & \\ & 1 \end{pmatrix}\,, \end{equation}$$ but then how can we realize it exactly? When $$N=2^n$$ we can get the $$\frac{1}{\sqrt{2^n}}$$ prefactor with the n Hadamard gates that prepare the uniform superpositions, but now that $$\sqrt{3}$$ factor is really bothering me.