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.


1 Answer 1


Kitaev gave an algorithm to approximate Quantum Fourier Transform over an arbitrary cyclic group.

Later, Mosca and Zalka showed how his construction can be made exact.

You can find a nice description for Kitaev algorithm in Dave Bacon lecture notes for example.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.