Geodesic
On the complexity of unitary transformations
Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 113-118 
D. Yu. Cherukhin. On the complexity of unitary transformations. Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 113-118. http://geodesic.mathdoc.fr/item/DM_2003_15_4_a6/
@article{DM_2003_15_4_a6,
     author = {D. Yu. Cherukhin},
     title = {On the complexity of unitary transformations},
     journal = {Diskretnaya Matematika},
     pages = {113--118},
     year = {2003},
     volume = {15},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_4_a6/}
}
TY  - JOUR
AU  - D. Yu. Cherukhin
TI  - On the complexity of unitary transformations
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 113
EP  - 118
VL  - 15
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_4_a6/
LA  - ru
ID  - DM_2003_15_4_a6
ER  - 
%0 Journal Article
%A D. Yu. Cherukhin
%T On the complexity of unitary transformations
%J Diskretnaya Matematika
%D 2003
%P 113-118
%V 15
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2003_15_4_a6/
%G ru
%F DM_2003_15_4_a6

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Sevidzh Dzh. E., Slozhnost vychislenii, Faktorial, Moskva, 1998

[2] Stin E., Kvantovye vychisleniya, NITs “Regulyarnaya i khaoticheskaya dinamika”, Izhevsk, 2000