Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?

Question

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?

Answer 1

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–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. 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 — note that the same problem occurs for any family of circuits which might use QFTs of arbitrary order.