Exact Coset Sampling for Quantum Lattice Algorithms

Code

• github.com/yifanzhang-pro/quantum-lattice
  Official★ 1

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 (Z_M)^n is supported on an affine grid line \\, jΔ+ v^(E) + M_2 k M : j Z,\ k K \,\, with Δ= 2D^2 b, M = 2M_2 = 2D^2 Q, and Q odd. The amplitudes include a quadratic Karst-wave chirp (-2πi j^2 / Q) and an unknown run-dependent offset v^(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 D^2, obtain the run-local class v_1,Q := v_1^(E) 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 QFT_Z_M^ n to the coordinate registers. The routine never needs the full offset v^(E). Under Additional Conditions AC1-AC5 on the front end, a measured Fourier outcome u Z_M^n satisfies the resonance b, u 0 Q with probability 1 - o(1). Moreover, conditioned on resonance, the reduced outcome u Q is exactly uniform on the dual hyperplane H = \\, v Z_Q^n : b, v 0 Q \,\.

Reproductions