# Exact Coset Sampling for Quantum Lattice Algorithms

arXiv: https://arxiv.org/abs/2509.12341 · HTML: https://mlsanity.com/paper/2509.12341/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 39 references that are in the map.
- First posted on arXiv 15 Sep 2025.

## Builds on (most cited first, 4 of 4)

- [Classical Hardness of Learning with Errors](https://mlsanity.com/paper/1306.0281/) (2013)
- [Learning With Errors and Extrapolated Dihedral Cosets](https://mlsanity.com/paper/1710.08223/) (2017)
- [Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering](https://mlsanity.com/paper/2108.11015/) (2021)
- [LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling](https://mlsanity.com/paper/2310.00644/) (2023)

## Abstract (arXiv)

We revisit the post-processing phase of Chen's Karst-wave quantum lattice algorithm (Chen, 2024) in the Learning with Errors (LWE) parameter regime. Conditioned on a transcript E, the post-Step 7 coordinate state on (mathbbZM)n is supported on an affine grid line , jDelta + vast(E) + M2 k bmod M : j ∈ mathbbZ, k ∈ K ,, with Delta = 2D2 b, M = 2M2 = 2D2 Q, and Q odd. The amplitudes include a quadratic Karst-wave chirp exp(-2π i j2 / Q) and an unknown run-dependent offset vast(E). We show that Chen's Steps 8-9 can be replaced by a single exact post-processing routine: measure the deterministic residue τ := X1 bmod D2, obtain the run-local class v1,Q := v1ast(E) bmod Q as explicit side information in our access model, apply a v1,Q-dependent diagonal quadratic phase on X1 to cancel the chirp, and then apply QFT_mathbbZMotimes n to the coordinate registers. The routine never needs the full offset vast(E). Under Additional Conditions AC1-AC5 on the front end, a measured Fourier outcome u ∈ mathbbZMn satisfies the resonance langle b, u rangle equiv 0 pmod Q with probability 1 - o(1). Moreover, conditioned on resonance, the reduced outcome u bmod Q is exactly uniform on the dual hyperplane H = , v ∈ mathbbZQn : langle b, v rangle equiv 0 pmod Q ,.