A Lower Bound for Fourier Transform Computation in a Linear Model Over 2x2 Unitary Gates Using Matrix Entropy
A Lower Bound for Fourier Transform Computation in a Linear Model Over 2x2 Unitary Gates Using Matrix Entropy
复制标题
使用矩阵熵的 2x2 酉门线性模型中傅里叶变换计算的下界
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Nir Ailon
中科院分区：
文献类型：
--
作者：
Nir Ailon
在线性电路模型中获得非平凡（超线性）的傅里叶变换的计算下限一直是一个长期存在的开放问题。到目前为止，所有的下界都对计算模型进行了严格的限制。最著名的结果之一，Morgenstern从1973年，提供了一个$Omega（n log n）$下界的FFT {unnormalized}计算中使用的常数时，有界的。证明使用与行列式相关的势函数。非标准化傅立叶变换的行列式是$n^{n/2}$，因此通过表明它在每一步之后最多可以增长一个常数因子，得到了这个结果。
然而，这个经典的结果并没有解释为什么具有单位行列式的归一化傅立叶变换需要$Omega（nlog n）$步来计算。在这项工作中，我们表明，在一个分层的线性电路模型限制到酉$2 乘以2$门，得到一个$Omega（nlog n）$下界。众所周知的FFT工作在这个模型中。从这项工作中得出的主要论点是，一个潜在的功能，可能最终有助于证明的$Omega（nlog n）$的约束下限的计算傅立叶变换是不相关的矩阵行列式，而是矩阵熵的概念。
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 most well known results, by Morgenstern from 1973, 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 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 emph{normalized} Fourier transform, which has a unit determinant, should take $Omega(nlog n)$ steps to compute. In this work we show that in a layered linear circuit model restricted to unitary $2 imes 2$ gates, one obtains an $Omega(nlog n)$ lower bound. The well known FFT works in this model. The main argument concluded from this work is that a potential function that might eventually help proving the $Omega(nlog n)$ conjectured lower bound for computation of Fourier transform is not related to matrix determinant, but rather to a notion of matrix entropy.