Faster Classical and Quantum BKW for LWE
We improve classical and quantum BKW for learning with errors at Regev's parameters. Each coded round sets a separate radius limit for each earlier coordinate block. A tighter limit in a later round allows wider rounding bins when the block first enters, but makes suitable pairs harder to find. Choosing these limits together with the block sizes gives classical time $2^{0.8883n+o(n)}$ and quantum time $2^{0.8737n+o(n)}$ with Grover search. Reusing a quantum-walk state to find many pairs lowers the time to $2^{0.8643n+o(n)}$. These algorithms read fresh classical samples. From only $\Theta(n\log n)$ original samples, amplification gives classical time $2^{1.6359n+o(n)}$, quantum time $2^{1.6130n+o(n)}$ with Grover search, and $2^{1.5979n+o(n)}$ with reusable walks. Integral equations define the constants in these bounds. The running times are heuristic: we assume that the intermediate lists have the distance and filter statistics of independent random directions within each block. The walk also needs these statistics inside its filters and coherent reads and writes of working memory.
Authors
- Luis Iglesias (ORCID: https://orcid.org/0000-0003-2561-8934)
- Samuel J. Adams
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-17
- DOI
- https://doi.org/10.5281/zenodo.24309952
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- preprint