### Volume 2013

#### A Lower Bound for Fourier Transform Computation in a Linear Model Over 2x2 Unitary Gates Using Matrix Entropy

Nir Ailon
Department of Computer Science
Technion Israel Institute of Technology
Haifa, Israel
nailon AT cs DOT technion DOT ac DOT il

October 18, 2013

#### Abstract

Obtaining a non-trivial (super-linear) lower bound for computation of the Fourier transform in the linear circuit model has been a long standing open problem. All lower bounds so far have made strong restrictions on the computational model. One of the best known results, by Morgenstern from 1973, provides an $\Omega(n \log n)$ lower bound for the unnormalized FFT when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The determinant of the unnormalized Fourier transform is $n^{n/2}$, and thus by showing that it can grow by at most a constant factor after each step yields the result. This classic result, however, does not explain why the normalized Fourier transform, which has a unit determinant, should take $\Omega(n\log n)$ steps to compute. In this work we show that in a layered linear circuit model restricted to unitary $2\times 2$ gates, one obtains an $\Omega(n\log n)$ lower bound. The well known FFT works in this model. The main conclusion from this work is that a potential function that might eventually help proving the $\Omega(n\log n)$ conjectured lower bound for computation of Fourier transform is not related to matrix determinant, but rather to a notion of matrix entropy.

• The article: PDF (152 KB)
• Source material: ZIP (68 KB)