Exact Coset Sampling for Quantum Lattice Algorithms

Abstract

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 $(\mathbb{Z}_M)^n$ is supported on an affine grid line $\{\, jΔ+ v^{\ast}(E) + M_2 k \bmod M : j \in \mathbb{Z},\ k \in \mathcal{K} \,\}$, with $Δ= 2D^2 b$, $M = 2M_2 = 2D^2 Q$, and $Q$ odd. The amplitudes include a quadratic Karst-wave chirp $\exp(-2πi j^2 / Q)$ and an unknown run-dependent offset $v^{\ast}(E)$. We show that Chen's Steps 8-9 can be replaced by a single exact post-processing routine: measure the deterministic residue $τ:= X_1 \bmod D^2$, obtain the run-local class $v_{1,Q} := v_1^{\ast}(E) \bmod Q$ as explicit side information in our access model, apply a $v_{1,Q}$-dependent diagonal quadratic phase on $X_1$ to cancel the chirp, and then apply $\mathrm{QFT}_{\mathbb{Z}_M}^{\otimes n}$ to the coordinate registers. The routine never needs the full offset $v^{\ast}(E)$. Under Additional Conditions AC1-AC5 on the front end, a measured Fourier outcome $u \in \mathbb{Z}_M^n$ 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 \in \mathbb{Z}_Q^n : \langle b, v \rangle \equiv 0 \pmod Q \,\}$.