An Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors

TitleAn Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors
Publication TypeJournal Article
Year of Publication2023
AuthorsLiu, Y-K
Date Published10/5/2023
Abstract

The curvelet transform is a special type of wavelet transform, which is useful for estimating the locations and orientations of waves propagating in Euclidean space. We prove an uncertainty principle that lower-bounds the variance of these estimates, for radial wave functions in n dimensions.
As an application of this uncertainty principle, we show the infeasibility of one approach to constructing quantum algorithms for solving lattice problems, such as the approximate shortest vector problem (approximate-SVP), and bounded distance decoding (BDD). This gives insight into the computational intractability of approximate-SVP, which plays an important role in algorithms for integer programming, and in post-quantum cryptosystems.
In this approach to solving lattice problems, one prepares quantum superpositions of Gaussian-like wave functions centered at lattice points. A key step in this procedure requires finding the center of each Gaussian-like wave function, using the quantum curvelet transform. We show that, for any choice of the Gaussian-like wave function, the error in this step will be above the threshold required to solve BDD and approximate-SVP.

URLhttps://arxiv.org/abs/2310.03735