О сложности унитарных преобразований

В работе предложен метод получения нижних оценок сложности неветвящихся программ, элементарными операциями в которых являются унитарные преобразования над двумя комплексными числами. Метод позволяет получать оценки вида $\Omega(n\log n)$ для унитарных операторов $\mathbf C^n\to\mathbf C^n$, в частности, для преобразований Фурье и Уолша. При $n=2^k$ найдены точные значения сложности последних.
Работа выполнена при поддержке Российского фонда фундаментальных исследований по Программе поддержки ведущих научных школ, проект 00–15–96103.