A Classical Quadratic Speedup for Planted $k$XOR
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_ | 1866913990560448512 |
|---|---|
| author | Gupta, Meghal He, William O'Donnell, Ryan Singer, Noah G. |
| author_facet | Gupta, Meghal He, William O'Donnell, Ryan Singer, Noah G. |
| contents | A recent work of Schmidhuber et al (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted $k$XOR problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant $k$. Thus for such $k$, the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09422 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Classical Quadratic Speedup for Planted $k$XOR Gupta, Meghal He, William O'Donnell, Ryan Singer, Noah G. Data Structures and Algorithms Cryptography and Security Quantum Physics A recent work of Schmidhuber et al (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted $k$XOR problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant $k$. Thus for such $k$, the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration. |
| title | A Classical Quadratic Speedup for Planted $k$XOR |
| topic | Data Structures and Algorithms Cryptography and Security Quantum Physics |
| url | https://arxiv.org/abs/2508.09422 |