{"ID":2859015,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.07515","arxiv_id":"2510.07515","title":"No exponential quantum speedup for $\\mathrm{SIS}^\\infty$ anymore","abstract":"In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case $\\ell_\\infty$-Short Integer Solution ($\\mathrm{SIS}^\\infty$) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since $\\mathrm{SIS}^\\infty$ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups. We present efficient classical algorithms for all of the $\\mathrm{SIS}^\\infty$ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore.","short_abstract":"In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case $\\ell_\\infty$-Short Integer Solution ($\\mathrm{SIS}^\\infty$) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciti...","url_abs":"https://arxiv.org/abs/2510.07515","url_pdf":"https://arxiv.org/pdf/2510.07515v3","authors":"[\"Robin Kothari\",\"Ryan O'Donnell\",\"Kewen Wu\"]","published":"2025-10-08T20:28:47Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CC\",\"cs.CR\",\"cs.DS\"]","methods":"[]","has_code":false}