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

  • $\begingroup$ 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? $\endgroup$
    – glS
    Jan 24 at 17:10
  • $\begingroup$ @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. $\endgroup$ Jan 24 at 17:31

1 Answer 1


This is covered in the paper "Exact quantum Fourier transforms and discrete logarithm algorithms":

We show how the quantum fast Fourier transform (QFFT) can be made exact for arbitrary orders (first for large primes). For most quantum algorithms only the quantum Fourier transform of order 2^n is needed, and this can be done exactly. Kitaev showed how to approximate the Fourier transform for any order. Here we show how his construction can be made exact by using the technique known as "amplitude amplification". Although unlikely to be of any practical use, this construction e.g. allows to make Shor's discrete logarithm quantum algorithm exact. Thus we have the first example of an exact non black box fast quantum algorithm, thereby giving more evidence that "quantum" need not be probabilistic. We also show that in a certain sense the family of circuits for the exact QFFT is uniform. Namely the parameters of the gates can be calculated efficiently.

The Kitaev paper is "Quantum measurements and the Abelian Stabilizer Problem":

We present a polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm. Thus we extend famous Shor's results. Our method is based on a procedure for measuring an eigenvalue of a unitary operator. Another application of this procedure is a polynomial quantum Fourier transform algorithm for an arbitrary finite Abelian group. The paper also contains a rather detailed introduction to the theory of quantum computation.

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.

Example circuit:

enter image description here


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.