On the complexity of unitary transformations

In this paper, we suggest a method to derive lower bounds for the complexity of non-branching programs whose elementary operations are unitary transformations over two complex numbers. This method provides us with estimates of the form $\Omega(n\log n)$ for unitary operators $\mathbf C^n\to\mathbf C^n$, in particular, for the Fourier and Walsh transformations. For $n=2^k$ we find precise values of the complexity of those transformations.
This research was supported by the Russian Foundation for Basic Research, grant 00–15–96103.