Large quantum Fourier transforms are never exactly realized by braiding conformal blocks
Michael Hartley Freedman, Zhenghan Wang · Physical Review A · 2007
Fourier transform is an essential ingredient in Shor's factoring algorithm. In the standard quantum circuit model with the gate set {$\mathbb{U}(2)$, controlled-NOT}, the discrete Fourier transforms ${F}_{N}={({\ensuremath{\omega}}^{ij})}_{N\ifmmode\times\else\texttimes\fi{}N}$, $i,j=0,1,\dots{},N\ensuremath{-}1$, $\ensuremath{\omega}={e}^{2\ensuremath{\pi}i∕N}$, can be realized exactly by quantum circuits of size $O({n}^{2})$, $n=\mathrm{ln}\phantom{\rule{0.2em}{0ex}}N$, and so can the discrete sine or cosine transforms. In topological quantum computing, the simplest universal topological quantum computer is based on the Fibonacci $(2+1)$-topological quantum field theory (TQFT), where the standard quantum circuits are replaced by unitary transformations realized by braiding conformal blocks. We report here that the large Fourier transforms ${F}_{N}$ and the discrete sine or cosine transforms can never be realized exactly by braiding conformal blocks for a fixed TQFT. It follows that an approximation is unavoidable in the implementation of Fourier transforms by braiding conformal blocks.