Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$? I am considering ideas about exact quantum algorithms. In particular, I am considering likely limitations of $\mathsf{EQP}$, which consists of languages exactly decideable by polytime-uniform quantum circuit families over an arbitrary finite gate set.

The quantum Fourier transform (QFT), given by
$$ F_N = {\frac{1}{\sqrt N} \begin{bmatrix} 1 &amp; 1 &amp; 1 &amp; 1&amp;  \cdots &amp; 1 \\ 1 &amp; \omega &amp; \omega^2 &amp; \omega^3 &amp; \cdots &amp; \omega^{N-1} \\ 1 &amp; \omega^2 &amp; \omega^4 &amp; \omega^6 &amp;  \cdots &amp; \omega^{N-2} \\ 1 &amp; \omega^3 &amp; \omega^6 &amp; \omega^9 &amp; \cdots &amp; \omega^{N-3} \\ \vdots &amp; \vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ 1 &amp; \omega^{N-1} &amp; \omega^{N-2} &amp; \omega^{N-3} &amp; \cdots &amp; \omega^{(N-1)^2} \end{bmatrix}} \quad\text{for $\omega = \mathrm e^{2\pi i/N}$},$$
is a celebrated part of quantum computational theory.
In the case of $N = 2^n$, there is well-known decomposition of $F_N$ into Hadamards, SWAP gates, and diagonal gates $$\mathrm{CZ}_{2^T} = \mathrm{diag}(1,1,1,\mathrm e^{2\pi i/2^T\!})$$ for various $T \geqslant 1$, which is due to Coppersmith. If $\mathsf{EQP} \smallsetminus \mathsf{P}$ is to contain any problems, one might hope that one of these would make use of the QFTs $F_{2^n}$, in which case one would require the family of operations $F_{2^n}$ to decompose into some particular finite gate set. Using the recursive decomposition of the QFT, this is equivalent to there being a decomposition of all gates $\mathrm{CZ}_{2^n}$ into a single finite gate set.

Obviously, by the Solovay&ndash;Kitaev theorem, we may approximate the gates $F_{2^n}$ or $\mathrm{CZ}_{2^n}$ arbitrarily well with any approximately universal gate set which is closed under inverses. What I would like to know is whether there is a finite gate-set which may exactly realise these families of operators &mdash; or, what I suspect is more likely, whether there is a proof that no such finite gate-set exists. 

Question. 
Is there either a decomposition of $\{ F_{2^n} \}_{n \geqslant 1}$ as a polytime-uniform circuit family on a finite gate-set, or a proof that this is impossible?
No, there is no decomposition of the entire family $\{F_{2^n}\}_{n\geqslant1}$ into a single finite gate-set. Here's why.

The QFTs involve only coefficients over $\overline{\mathbb Q}$, the complex algebraic closure of the rational numbers. In analogy to [Adleman+Demarrais+Huang&ndash;1997], if we involved any gates which included any transcendental numbers, we could choose a minimal set of transcendentals $\{\tau_1, \tau_2, \ldots\}$ and describe the gate-coefficients essentially as rational functions $\overline{\mathbb Q}(\tau_1, \tau_2, \ldots)$. To obtain the QFT as a product of such gates, we must arrange for all of the transcendental components to cancel (a similar thing must occur to ensure each of the gates are unitary); but then we might as well replace all of the transcendentals with $0$, so that all of the coefficients are algebraic. So we restrict ourselves to algebraic gate-sets without loss of generality.

The coefficients of a finite gate set over $\overline{\mathbb Q}$ can all be contained in a finite-degree extension of $\mathbb Q$, which one may construct by extending $\mathbb Q$ by those very coefficients. However, the gates $\mathrm{CZ}_{2^n}$ obviously have coefficients belonging to field extensions over $\mathbb Q$ of degree $2^{n-1}$, i.e.&nbsp;of unbounded degree.
Thus the family of QFTs of order $2^n$ does not decompose into any finite gate-set.

As a corollary, we cannot hope to have any algorithms in $\mathsf{EQP}$ which relies on QFTs over cyclic rings of unbounded size &mdash; note that the same problem occurs for any family of circuits which might use QFTs of arbitrary order.