{"ID":2871088,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.12341","arxiv_id":"2509.12341","title":"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 \\,\\}$.","short_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 \\...","url_abs":"https://arxiv.org/abs/2509.12341","url_pdf":"https://arxiv.org/pdf/2509.12341v8","authors":"[\"Yifan Zhang\"]","published":"2025-09-15T18:10:28Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CL\",\"cs.CR\"]","methods":"[]","has_code":false}