I have seen Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?. This is not a duplicate.

I am familiar with the decomposition of the QFT from Nielsen&Chuang and Preskill's notes, and it requires to be able to perform n-different control phase gates. If we only allow the smallest control-phase, we can still implement all the other ones as powers but we now need to use it exponentially many times. It seems that the speedup of the quantum fourier transform is based on allowing a particularly nice (albeit reasonable) gate set.

Did I miss anything? Is there a way to decompose that circuit efficiently into a standard gate set (e.g. CNOT, H, P, and Paulis)?


1 Answer 1


Talking about efficiency here isn't exactly a fair question: as you change n, the number of qubits in the Fourier transfer, you're changing the gate that you're talking about using (because the smallest phase will be something like controlled-$Z(\pi/2^n)$). After all, if I can do controlled-$Z$ when I have two qubits, why would I suddenly lose the ability to do controlled-$Z$ (and only be able to do controlled-$\sqrt{Z}$) when I have 3 qubits?

If you use a fixed gate set rather than changing it with $n$, then whichever phase you happen to use is only a finite overhead to convert back into the standard controlled-phase, and so the whole circuit remains efficient.

  • $\begingroup$ thanks, I guess arxiv.org/abs/quant-ph/0303063 is part of what I was missing $\endgroup$ Jun 17, 2019 at 10:57

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.