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

Publication Type | Journal Article |

Year of Publication | 2023 |

Authors | Liu, Y-K |

Date Published | 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. |

URL | https://arxiv.org/abs/2310.03735 |