You are here: Home :: Area NEM :: Mathematics

D. Yu. Cherukhin

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 Ω(n log n) for unitary operators Cⁿ → Cⁿ, in particular, for the Fourier and Walsh transformations. For n = 2^k we find precise values of the complexity of those transformations.

Discrete Mathematics and Applications, Walter de Gruyter

Print ISSN: 0924-9266
Volume: 13, 12/2003
Pages: 601 - 606

Show full article (external site)

Show all available items of this journal

 

Area NEM