English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Obtaining a non-trivial (super-linear) lower bound for computation of theFourier transform in the linear circuit model has been a long standing openproblem. All lower bounds so far have made strong restrictions on thecomputational model. One of the most well known results, by Morgenstern from1973, provides an $\Omega(n \log n)$ lower bound for the \emph{unnormalized}FFT when the constants used in the computation are bounded. The proof uses apotential function related to a determinant. The determinant of theunnormalized Fourier transform is $n^{n/2}$, and thus by showing that it cangrow by at most a constant factor after each step yields the result.  This classic result, however, does not explain why the \emph{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 modelrestricted to unitary $2\times 2$ gates, one obtains an $\Omega(n\log n)$ lowerbound. The well known FFT works in this model. The main argument concluded fromthis work is that a potential function that might eventually help proving the$\Omega(n\log n)$ conjectured lower bound for computation of Fourier transformis not related to matrix determinant, but rather to a notion of matrix entropy.

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