Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1403.1307

An n\log n Lower Bound for Fourier Transform Computation in the Well Conditioned Model

Nir Ailon

Published Mar 6, 2014• 3 citations
arXivHTMLPDF

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 for over 40 years. An early result by Morgenstern from 1973, provides an $Ω(n \log n)$ lower bound for the unnormalized Fourier transform when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The result does not explain why the normalized Fourier transform (of unit determinant) should be difficult to compute in the same model. Hence, the result is not scale insensitive. More recently, Ailon (2013) showed that if only unitary 2-by-2 gates are used, and additionally no extra memory is allowed, then the normalized Fourier transform requires $Ω(n\log n)$ steps. This rather limited result is also sensitive to scaling, but highlights the complexity inherent in the Fourier transform arising from introducing entropy, unlike, say, the identity matrix (which is as complex as the Fourier transform using Morgenstern's arguments, under proper scaling). In this work we extend the arguments of Ailon (2013). In the first extension, which is also the main contribution, we provide a lower bound for computing any scaling of the Fourier transform. Our restriction is that, the composition of all gates up to any point must be a well conditioned linear transformation. The lower bound is $Ω(R^{-1}n\log n)$, where $R$ is the uniform condition number. Second, we assume extra space is allowed, as long as it contains information of bounded norm at the end of the computation. The main technical contribution is an extension of matrix entropy used in Ailon (2013) for unitary matrices to a potential function computable for any matrix, using Shannon entropy on "quasi-probabilities".

DOI
10.48550/arxiv.1403.1307

Related papers

A Lower Bound for Fourier Transform Computation in a Linear Well Conditioned Model

Nir Ailon

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 for over 40 years. An early result by Morgenstern from 1973, provides an $\Omega(n \log n)$ lower bound for the unnormalized Fourier transform when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The result does not explain why the normalized Fourier transform (of unit determinant) should be difficult to compute in the same model. Hence, the result is not scale insensitive. More recently, Ailon (2013) showed that if only unitary 2-by-2 gates are used, and additionally no extra memory is allowed, then the normalized Fourier transform requires $\Omega(n\log n)$ steps. This rather limited result is also sensitive to scaling, but highlights the complexity inherent in the Fourier transform arising from introducing entropy, unlike, say, the identity matrix (which is as complex as the Fourier transform using Morgenstern's arguments, under proper scaling). In this work we extend the arguments of Ailon (2013). In the first extension, which is also the main contribution, we provide a lower bound for computing any scaling of the Fourier transform. Our restriction is that, the composition of all gates up to any point must be a well conditioned linear transformation. The lower bound is $\Omega(R^{-1}n\log n)$, where $R$ is the uniform condition number. Second, we assume extra space is allowed, as long as it contains information of bounded norm at the end of the computation. The main technical contribution is an extension of matrix entropy used in Ailon (2013) for unitary matrices to a potential function computable for any matrix, using Shannon entropy on quasi-probabilities.

•Mar 6, 2014•0 citations

An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model

Nir Ailon

Obtaining a nontrivial (superlinear) lower bound for computation of the Fourier transform in the linear circuit model has been a long-standing open problem for more than 40 years. An early result by Morgenstern from 1973, provides an Ω( n log n ) lower bound for the unnormalized Fourier transform when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. That result does not explain why the normalized Fourier transform (of unit determinant) should be difficult to compute in the same model. Hence, it is not scale insensitive. More recently, Ailon [2013] showed that if only unitary 2-by-2 gates are used, and additionally no extra memory is allowed, then the normalized Fourier transform requires Ω( n log n ) steps. This rather limited result is also sensitive to scaling, but highlights the complexity inherent in the Fourier transform arising from introducing entropy, unlike, say, the identity matrix (which is as complex as the Fourier transform using Morgenstern’s arguments, under proper scaling). This work improves on Ailon [2013] in two ways: First, we eliminate the scaling restriction and provide a lower bound for computing any scaling of the Fourier transform. Second, we allow the computational model to use extra memory. Our restriction is that the composition of all gates up to any point must be a well- conditioned linear transformation. The lower bound is Ω( R −1 n log n ), where R is the uniform condition number. Well-conditioned is a natural requirement for algorithms accurately computing linear transformations on machine architectures of bounded word size. Hence, this result can be seen as a tradeoff between speed and accuracy. The main technical contribution is an extension of matrix entropy used in Ailon [2013] for unitary matrices to a potential function computable for any invertible matrix, using “quasi-entropy” of “quasi-probabilities.”

ACM Transactions on Computation Theory•Feb 3, 2016•6 citations

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

Nir Ailon

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 $Ω(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 $Ω(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 $Ω(n\log 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 $Ω(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.

arXiv:1305.4745•Chicago Journal of Theoretical Computer Science•May 21, 2013•1 citation

The Complexity of Computing (Almost) Unitary Matrices With $\eps$-Copies of the Fourier Transform

Nir Ailon, Gal Yehuda

The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numerical ill-condition. The papers also quantify this tradeoff. The main method for proving these results is via a potential function called quasi-entropy, reminiscent of Shannon entropy. The quasi-entropy method opens new doors to understanding the computational complexity of the important Fourier transformation. However, it suffers from various obvious limitations. This paper, motivated by one such limitation, partly overcomes it, while at the same time sheds llight on new interesting, and problems on the intersection of computational complexity and group theory. The paper also explains why this research direction, if fruitful, has a chance of solving much bigger questions about the complexity of the Fourier transform.

arXiv:1604.02557•Apr 9, 2016•0 citations

The complexity of computing (almost) orthogonal matrices with ε-copies of the Fourier transform

Nir Ailon, Gal Yehuda

The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numerical ill-condition. The papers also quantify this tradeoff. The main method for proving these results is via a potential function called quasi-entropy, reminiscent of Shannon entropy. The quasi-entropy method opens new doors to understanding the computational complexity of the important Fourier transformation. However, it suffers from various obvious limitations. This paper is motivated by one such limitation, related to the computation of near-orthogonal matrices that have the Fourier transform ‘hidden’ in low-order bits. While partly overcoming this limitation, the paper sheds light on new interesting, open problems on the intersection of computational complexity and group theory. The paper also explains why this research direction, if fruitful, has a chance of solving much bigger questions about the complexity of the Fourier transform.

Information Processing Letters•Sep 14, 2020•0 citations

Communication Complexity of Distributed Unitary Synthesis

Longcheng Li, Xiaoming Sun, Jialin Zhang +1 more

We study space-bounded communication complexity for unitary implementation in distributed quantum processors, where we restrict the number of qubits per processor to ensure practical relevance and technical non-triviality. We model distributed quantum processors using distributed quantum circuits with nonlocal two-qubit gates, defining the distributed communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization, up to permutations of data qubit positions. Our contributions are twofold. First, for general $n$-qubit unitaries, we improve upon the trivial $O(4^n)$ communication bound. Considering $k$ pairwise-connected processors (each with $n/k$ data qubits and $m$ ancillas), we prove the communication complexity satisfies $O\left(\max\{4^{(1-1/k)n - m}, n\}\right)$ -- for example, $O(2^n)$ when $m=0$ and $k=2$ -- and establish the tightness of this upper bound. We further extend the analysis to approximation models and general network topologies. Second, for special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity in the exact model, outperforming the trivial quadratic bounds applicable to these cases. In the approximation model, QFT's communication complexity reduces drastically from linear to logarithmic, while Clifford circuits retain a linear lower bound. These results offer fundamental insights for optimizing communication in distributed quantum unitary implementation, advancing the feasibility of large-scale DQC systems.

quant-pharXiv:2511.04250•IEEE Transactions on Information Theory•Nov 7, 2025•0 citations
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 for over 40 years. An early result by Morgenstern from 1973, provides an Ω(nlog⁡n)Ω(n \log n)Ω(nlogn) lower bound for the unnormalized Fourier transform when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The result does not explain why the normalized Fourier transform (of unit determinant) should be difficult to compute in the same model. Hence, the result is not scale insensitive. More recently, Ailon (2013) showed that if only unitary 2-by-2 gates are used, and additionally no extra memory is allowed, then the normalized Fourier transform requires Ω(nlog⁡n)Ω(n\log n)Ω(nlogn) steps. This rather limited result is also sensitive to scaling, but highlights the complexity inherent in the Fourier transform arising from introducing entropy, unlike, say, the identity matrix (which is as complex as the Fourier transform using Morgenstern's arguments, under proper scaling). In this work we extend the arguments of Ailon (2013). In the first extension, which is also the main contribution, we provide a lower bound for computing any scaling of the Fourier transform. Our restriction is that, the composition of all gates up to any point must be a well conditioned linear transformation. The lower bound is Ω(R−1nlog⁡n)Ω(R^{-1}n\log n)Ω(R−1nlogn), where RRR is the uniform condition number. Second, we assume extra space is allowed, as long as it contains information of bounded norm at the end of the computation. The main technical contribution is an extension of matrix entropy used in Ailon (2013) for unitary matrices to a potential function computable for any matrix, using Shannon entropy on "quasi-probabilities".
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 for over 40 years. An early result by Morgenstern from 1973, provides an Ω(nlog⁡n)\Omega(n \log n)Ω(nlogn) lower bound for the unnormalized Fourier transform when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The result does not explain why the normalized Fourier transform (of unit determinant) should be difficult to compute in the same model. Hence, the result is not scale insensitive. More recently, Ailon (2013) showed that if only unitary 2-by-2 gates are used, and additionally no extra memory is allowed, then the normalized Fourier transform requires Ω(nlog⁡n)\Omega(n\log n)Ω(nlogn) steps. This rather limited result is also sensitive to scaling, but highlights the complexity inherent in the Fourier transform arising from introducing entropy, unlike, say, the identity matrix (which is as complex as the Fourier transform using Morgenstern's arguments, under proper scaling). In this work we extend the arguments of Ailon (2013). In the first extension, which is also the main contribution, we provide a lower bound for computing any scaling of the Fourier transform. Our restriction is that, the composition of all gates up to any point must be a well conditioned linear transformation. The lower bound is Ω(R−1nlog⁡n)\Omega(R^{-1}n\log n)Ω(R−1nlogn), where RRR is the uniform condition number. Second, we assume extra space is allowed, as long as it contains information of bounded norm at the end of the computation. The main technical contribution is an extension of matrix entropy used in Ailon (2013) for unitary matrices to a potential function computable for any matrix, using Shannon entropy on quasi-probabilities.
Obtaining a nontrivial (superlinear) lower bound for computation of the Fourier transform in the linear circuit model has been a long-standing open problem for more than 40 years. An early result by Morgenstern from 1973, provides an Ω( n log n ) lower bound for the unnormalized Fourier transform when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. That result does not explain why the normalized Fourier transform (of unit determinant) should be difficult to compute in the same model. Hence, it is not scale insensitive. More recently, Ailon [2013] showed that if only unitary 2-by-2 gates are used, and additionally no extra memory is allowed, then the normalized Fourier transform requires Ω( n log n ) steps. This rather limited result is also sensitive to scaling, but highlights the complexity inherent in the Fourier transform arising from introducing entropy, unlike, say, the identity matrix (which is as complex as the Fourier transform using Morgenstern’s arguments, under proper scaling). This work improves on Ailon [2013] in two ways: First, we eliminate the scaling restriction and provide a lower bound for computing any scaling of the Fourier transform. Second, we allow the computational model to use extra memory. Our restriction is that the composition of all gates up to any point must be a well- conditioned linear transformation. The lower bound is Ω( R −1 n log n ), where R is the uniform condition number. Well-conditioned is a natural requirement for algorithms accurately computing linear transformations on machine architectures of bounded word size. Hence, this result can be seen as a tradeoff between speed and accuracy. The main technical contribution is an extension of matrix entropy used in Ailon [2013] for unitary matrices to a potential function computable for any invertible matrix, using “quasi-entropy” of “quasi-probabilities.”
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 Ω(nlog⁡n)Ω(n \log n)Ω(nlogn) 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 nn/2n^{n/2}nn/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 Ω(nlog⁡n)Ω(n\log n)Ω(nlogn) steps to compute. In this work we show that in a layered linear circuit model restricted to unitary 2×22\times 22×2 gates, one obtains an Ω(nlog⁡n)Ω(n\log n)Ω(nlogn) 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 Ω(nlog⁡n)Ω(n\log n)Ω(nlogn) conjectured lower bound for computation of Fourier transform is not related to matrix determinant, but rather to a notion of matrix entropy.
The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numerical ill-condition. The papers also quantify this tradeoff. The main method for proving these results is via a potential function called quasi-entropy, reminiscent of Shannon entropy. The quasi-entropy method opens new doors to understanding the computational complexity of the important Fourier transformation. However, it suffers from various obvious limitations. This paper, motivated by one such limitation, partly overcomes it, while at the same time sheds llight on new interesting, and problems on the intersection of computational complexity and group theory. The paper also explains why this research direction, if fruitful, has a chance of solving much bigger questions about the complexity of the Fourier transform.
The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numerical ill-condition. The papers also quantify this tradeoff. The main method for proving these results is via a potential function called quasi-entropy, reminiscent of Shannon entropy. The quasi-entropy method opens new doors to understanding the computational complexity of the important Fourier transformation. However, it suffers from various obvious limitations. This paper is motivated by one such limitation, related to the computation of near-orthogonal matrices that have the Fourier transform ‘hidden’ in low-order bits. While partly overcoming this limitation, the paper sheds light on new interesting, open problems on the intersection of computational complexity and group theory. The paper also explains why this research direction, if fruitful, has a chance of solving much bigger questions about the complexity of the Fourier transform.
We study space-bounded communication complexity for unitary implementation in distributed quantum processors, where we restrict the number of qubits per processor to ensure practical relevance and technical non-triviality. We model distributed quantum processors using distributed quantum circuits with nonlocal two-qubit gates, defining the distributed communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization, up to permutations of data qubit positions. Our contributions are twofold. First, for general nnn-qubit unitaries, we improve upon the trivial O(4n)O(4^n)O(4n) communication bound. Considering kkk pairwise-connected processors (each with n/kn/kn/k data qubits and mmm ancillas), we prove the communication complexity satisfies O(max⁡{4(1−1/k)n−m,n})O\left(\max\{4^{(1-1/k)n - m}, n\}\right)O(max{4(1−1/k)n−m,n}) -- for example, O(2n)O(2^n)O(2n) when m=0m=0m=0 and k=2k=2k=2 -- and establish the tightness of this upper bound. We further extend the analysis to approximation models and general network topologies. Second, for special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity in the exact model, outperforming the trivial quadratic bounds applicable to these cases. In the approximation model, QFT's communication complexity reduces drastically from linear to logarithmic, while Clifford circuits retain a linear lower bound. These results offer fundamental insights for optimizing communication in distributed quantum unitary implementation, advancing the feasibility of large-scale DQC systems.