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 $$ F_N = {\frac{1}{\sqrt N} \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{-1} & \omega^{-2} & \cdots & \omega \end{bmatrix}} \quad\text{where $\omega = \mathrm e^{2\pi i/N}$},$$ is a celebrated part of quantum computational theory; and 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$ due to Coppersmith. If $\mathsf{EQP} \smallsetminus \mathsf{P}$ is to contain any problems, one might hope that one of these might make use of Fourier transforms $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 same 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–Kitaev theorem, we may approximate the gates $F_{2^n}$ or $\mathrm{CZ}_{2^n}$ arbitrarily well with any approximately universal gate set. What I would like to know is whether there is a finite gate-set which may exactly realise these families of operators — 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?

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 & 1 & 1 & 1& \cdots & 1 \\ 1 & \omega & \omega^2 & \omega^3 & \cdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \omega^6 & \cdots & \omega^{N-2} \\ 1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{N-3} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{N-1} & \omega^{N-2} & \omega^{N-3} & \cdots & \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–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 — 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?