Chicago Journal of Theoretical Computer Science

Volume 2013

Article 12

Published by the Department of Computer Science, The University of Chicago.

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


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.

Submitted June 20, 2013, revised October 11, 2013; published October 18, 2013.

DOI: 10.4086/cjtcs.2013.012

[] Article 11 [] Article 13
[back] Volume 2013 [back] Published articles
[CJCTS home]