No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912942936555520 |
|---|---|
| author | Kothari, Robin O'Donnell, Ryan Wu, Kewen |
| author_facet | Kothari, Robin O'Donnell, Ryan Wu, Kewen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_07515 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore Kothari, Robin O'Donnell, Ryan Wu, Kewen Quantum Physics Computational Complexity Cryptography and Security Data Structures and Algorithms 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. |
| title | No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore |
| topic | Quantum Physics Computational Complexity Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.07515 |