#

### 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*
#### 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)
**BibTeX** entry for this article (298 bytes)

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

Article 11
Article 13

Volume 2013
Published articles