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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Faster Classical and Quantum BKW for LWE

Luis Iglesias, Samuel J. Adams
1 links
Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
preprint

Faster Classical and Quantum BKW for LWE

Luis Iglesias, Samuel J. Adams
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon