<p>No, there is no decomposition of the entire family $\{F_{2^n}\}_{n\geqslant1}$ into a single finite gate-set. Here's why.</p>

<p>The QFTs involve only coefficients over $\overline{\mathbb Q}$, the complex algebraic closure of the rational numbers. In analogy to [<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.205.8140">Adleman+Demarrais+Huang&ndash;1997</a>], 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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-12-11T08:01:07.430Z
2014-12-11T08:07:22.133Z
2014-12-11T08:07:22.133Z
Niel de Beaudrap
<p>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.</p>

<p>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.</p>

<p>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 <em>exactly</em> 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. </p>

<p><strong>Question.</strong> 
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?</p>

<quantum-computing><circuit-families>
Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?
Niel de Beaudrap
# Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?

(Asked by: username_0 on 2014-12-10)

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?

**Tags:** quantum-computing, circuit-families


---

## 1 answers

### Answer by username_0 on 2014-12-11. Score: 7 | Accepted answer

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.205.8140)], 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.


---

