# How to construct a quantum circuit for quantum Fourier transform in a prime dimensional Hilbert space?

This problem is given as a problem in Nielsen and Chuang. Consider a Hilbert space of dimension $$p$$ where $$p$$ is a prime number. Quantum Fourier transform (QFT) in this space is defined as $$|j\rangle \rightarrow \frac{1}{\sqrt{p}} \sum_{k=0}^{p-1}e^{\frac{2\pi i j k}{p}} |k\rangle.$$ How to construct a quantum circuit that performs this transformation? The standard circuit for QFT requires the dimension to be a power of 2. That's no longer possible when $$p$$ is prime.

Cross-posted on physics.SE

• I'm a bit unsure about what a "quantum circuit" would even mean here. Prime dimension means there is no possible partite structure to the space, ie you cannot think of the states as composed of a number of qubits (nor more generally qudits of any kind). So we're talking about a single $p$-dimensional qudit. Also do they specify anywhere what building blocks are allowed for decompositions of this kind? I don't see it mentioned in the book. In lack of this, one could argue the "circuit" is just a single gate implementing the QFT itself?
– glS
Jan 24 at 17:10
• @glS Use ceil(log_2(p)) qubits and require that they stay within the subspace spanned by computational basis states representing binary values less than p. Jan 24 at 17:31

I think basically how it works is that you perform phase estimation against the $$+1 \pmod{p}$$ operation, using a power-of-2 QFT with $$p + O(\lg \frac{1}{\epsilon})$$ qubits in the phase estimation register $$R$$. This causes $$R$$ to contain a superposition of frequencies, but spaced out by a scaling factor. If the frequency-mod-$$p$$ is $$k$$ then $$R$$ will end up in the state $$|2^{\text{len}(R)}/p \cdot k \rangle$$. You fix this by computing an unscaled register $$R_2 = \lfloor R \cdot p/2^{\text{len}(R)} \rfloor$$ and then uncomputing $$R$$ by reversing the phase estimation. Now $$R_2$$ contains the frequencies you want. The only remaining problem is that you still have the input register. You uncompute it by using the fact that it is the Fourier transform of $$R_2$$. Run the procedure I described so far backwards, and with the roles of the output and input register reversed, to get rid of the input.