@article {3414, title = {An Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors}, year = {2023}, month = {11/7/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.\ \ 

}, url = {https://arxiv.org/abs/2310.03735}, author = {Yi-Kai Liu} } @article {3354, title = {An Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors}, year = {2023}, month = {10/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.

}, url = {https://arxiv.org/abs/2310.03735}, author = {Yi-Kai Liu} } @article {1427, title = {Universal low-rank matrix recovery from Pauli measurements}, journal = {Advances in Neural Information Processing Systems (NIPS)}, year = {2011}, month = {2011/03/14}, pages = {1638-1646}, abstract = { We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley{\textquoteright}s inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality. }, url = {http://arxiv.org/abs/1103.2816v2}, author = {Yi-Kai Liu} }