Exact Coset Sampling for Quantum Lattice Algorithms

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 ,.