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:quant-ph/0211017 · Journal of Mathematical Physics

Phase space localization of antisymmetric functions

L. L. Salcedo

Published Jan 1, 2009• 9 citations
arXivHTMLPDF

Abstract

Upper and lower bounds are written down for the minimum information entropy in phase space of an antisymmetric wave function in any number of dimensions. Similar bounds are given when the wave function is restricted to belong to any of the proper subspaces of the Fourier transform operator.
DOI
10.1063/1.3054279

Related papers

Localizing quantum information

Fahimeh Bayeh, Andre Kornell

The idea that information can be localized is pervasive in physics. In thermodynamics, entropy flows from one reservoir to another, and in quantum gravity, the entropy content of some spatial regions is bounded. In quantum information theory, information is transmitted from one place to another, and entanglement can provide an advantage when there are constraints on such transmission. Shannon entropy quantifies localizable information in the sense that marginalization defines an outer measure on the set of parts of a classical multipartite system. In contrast, von Neumann entropy does not quantify localizable information in this sense. However, a variant of von Neumann entropy, which originates in noncommutative geometry, does. We prove that this adjusted von Neumann entropy is the minimum quantum entropy that quantifies localizable information. We also prove that this is the unique quantum entropy that characterizes Bell states in terms of redundant information, directly generalizing the classical case. We work with finite-dimensional $C^*$-algebras throughout, modeling finite quantum systems that may have superselection sectors.

quant-pharXiv:2609.01966•Sep 3, 2026•0 citations

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

Phase Space Bounds for Quantum Mechanics on a Compact Lie Group

Brian C. Hall

Communications in Mathematical Physics•Feb 1, 1998•18 citations

An n\log n Lower Bound for Fourier Transform Computation in the 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 $Ω(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".

arXiv:1403.1307•Mar 6, 2014•7 citations

On the classical limit of phase-space formulation of quantum mechanics: Entropy

Lipo Wang

The classical limits of phase-space formulation of quantum mechanics are studied. As a special example, some properties of both quantum mechanical and classical entropies are discussed in detail.

Journal of Mathematical Physics•Feb 1, 1986•9 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
The idea that information can be localized is pervasive in physics. In thermodynamics, entropy flows from one reservoir to another, and in quantum gravity, the entropy content of some spatial regions is bounded. In quantum information theory, information is transmitted from one place to another, and entanglement can provide an advantage when there are constraints on such transmission. Shannon entropy quantifies localizable information in the sense that marginalization defines an outer measure on the set of parts of a classical multipartite system. In contrast, von Neumann entropy does not quantify localizable information in this sense. However, a variant of von Neumann entropy, which originates in noncommutative geometry, does. We prove that this adjusted von Neumann entropy is the minimum quantum entropy that quantifies localizable information. We also prove that this is the unique quantum entropy that characterizes Bell states in terms of redundant information, directly generalizing the classical case. We work with finite-dimensional C∗C^*C∗-algebras throughout, modeling finite quantum systems that may have superselection sectors.
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 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 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.”