Is the quantum Fourier transform efficient if only one control-phase is allowed in the gate set

Question

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 only 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)?

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.