Source-linked AI summary
Exact Coset Sampling for Quantum Lattice Algorithms
Yifan Zhang
TL;DR
The paper addresses how to obtain modular linear samples from Chen’s post-Step 7 state despite its run-dependent affine offset and chirp. It replaces Steps 8–9 with a run-local correction and direct QFT; under stated front-end conditions, the samples satisfy the desired dual relation and support chosen-secret LWE recovery in the same qualitative parameter regime.
Problem
The post-processing needs non-zero Fourier samples satisfying a homogeneous dual relation so O(n) samples can recover b mod Q and the hidden data.
Source: §1 · p. 2Method
Step 9† uses the affine structure, run-local chirp cancellation, and direct QFT, without requiring a fixed offset across runs or a special factorization of Q.
Source: §1 · p. 3, §5 · p. 23Results
Under AC1–AC4 and AC5, outcomes satisfy ⟨b, u⟩ ≡ 0 (mod Q) except with negligible failure probability, and reduced resonant samples are exactly uniform on the dual hyperplane.
Source: §1 · p. 3, §5 · p. 24Takeaways & Limitations
The reduced samples support linear-algebraic recovery over ZQ, and the resulting algorithm solves Chen’s chosen-secret LWE problem in the same qualitative parameter regime under the stated conditions.
Source: §5 · p. 24Correctness is conditional on a re-tuned front end satisfying Definition 2.1 and AC1–AC5, or the stated Gaussian-envelope hypotheses that imply AC5.
Source: §2 · p. 5
Abstract
from arXiv · showhide
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\Delta + v^{\ast}(E) + M_2 k \bmod M : j \in \mathbb{Z},\ k \in \mathcal{K} \,\}$, with $\Delta = 2D^2 b$, $M = 2M_2 = 2D^2 Q$, and $Q$ odd. The amplitudes include a quadratic Karst-wave chirp $\exp(-2\pi 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 $\tau := 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 \,\}$.
1 Introduction
The introduction proposes replacing Chen’s Steps 8–9 with a direct Step 9† that uses run-local chirp cancellation and a QFT on the coordinate registers. Under the stated conditions, it yields modular linear relations and supports recovery of the planted vector and chosen-secret LWE data.
1 Introduction
- After measuring τ = X1 mod D2, the routine obtains v1,Q from τ and a run-local gauge value to remove the Karst-wave chirp.The access model supplies this gauge value; AC1 alone does not imply it.Source: §1 · p. 2
- The goal is to obtain non-zero Fourier samples whose reductions satisfy a homogeneous dual relation, then use O(n) samples and linear algebra modulo Q to recover b mod Q and the hidden data.The passage identifies Q as odd and b1 = −1.Source: §1 · p. 2
- Step 9† uses the affine structure, b1 = −1, first-coordinate chirp cancellation, and a direct QFT, without requiring a special factorization of Q or a fixed offset across runs.The routine needs the run-local class v1,Q, not the full offset.Source: §1 · pp. 2–3
- Under AC1–AC4 and AC5, Fourier outcomes satisfy ⟨b, u⟩ ≡ 0 (mod Q) except with negligible failure probability.For the stated Gaussian-envelope regime, Proposition 2.6 establishes AC5 under its spectral hypotheses.Source: §1 · pp. 2–3
- Step 9† recovers the planted shortest vector and hence the LWE secret and error in Chen’s chosen-secret regime, yielding an algorithm in the same parameter regime conditional on the stated conditions.Recovery is combined with Chen’s classical reductions.Source: §1 · p. 3
2 Background and Access Model
This section defines the single-run access model, run-local information, and front-end conditions for chirp correction and exact post-processing. It states correctness conditional on AC1–AC5, including loop-envelope spectral concentration and exact uniformity of the reduced Fourier outcome on the dual hyperplane conditioned on resonance.
2 Background and Access Model
- Because the transcript-dependent offset cannot be reproduced by resetting the experiment, post-processing must use the single quantum state output by a successful run.The experiment cannot query chosen loop-index inputs to obtain X(j) classically or in an extra register.Source: §2 · p. 5
- Correctness is conditional on a re-tuned front end satisfying AC1–AC5; in the Gaussian-envelope regime, AC5 follows when σ_J ≳ Q log n under Proposition 2.6’s phase and perturbation hypotheses.The loop-envelope width σ_J is distinct from the geometric width σ_geom.Source: §2 · pp. 5–6
2.1 Front-end properties and additional conditions
- Under AC1, the transcript-conditioned post-Step 7 state lies on an affine grid line, and measuring X_1 mod D^2 yields a deterministic residue without disturbing its coherent superposition.The first-coordinate offset information is run-local; the preparation oracle supplies v_1,Q as side information for subsequent cancellation.Source: §2.1 · pp. 7–8
2 Background and Access Model
- The post-processing requires Q to be odd but permits arbitrary composite Q, while exact QFTs and phase gates can be approximated to 2^-poly(n) precision with negligible total-variation error.The unitary approximation discussion cites standard treatments.Source: §2 · p. 4, §2.1 · p. 7
2.1 Front-end properties and additional conditions
- AC4 uses v_1,Q to compute a first-coordinate-dependent diagonal phase that cancels the quadratic chirp, and the correction remains well-defined when formal labels collide physically.The first-coordinate congruence and b_1 = −1 force colliding loop labels to agree modulo Q.Source: §2.1 · p. 8
- AC5 requires factorization of chirp-free amplitudes across loop and grid labels plus concentration of the periodized loop envelope’s Q-point Fourier mass at zero.The factorization is imposed on formal coefficients after parity regrouping; without it, the one-dimensional leakage bound does not control the full Fourier distribution.Source: §2 · p. 4, §2.1 · pp. 8–9
- AC4 requires the exact run-local residue v1,Q, which AC1 alone does not provide; using it, a diagonal unitary on X1 cancels the loop chirp, and τ = X1 mod D^2 is deterministic.The residue is obtained as explicit side information or through canonical-gauge compilation.Source: §2.1 · pp. 10, 12
- AC1 is Chen’s offset-coherence invariant, AC2–AC3 are enforced by definition, AC4 supplies run-local gauge access, and AC5 is the spectral condition used by the direct-QFT step.In the Gaussian regime, Proposition 2.6 establishes AC5; outside it, AC5 remains an explicit requirement.Source: §2.1 · pp. 10, 12
- Conditioned on resonance, u mod Q is exactly uniform on H = {v in Z_Q^n : ⟨b, v⟩ ≡ 0 mod Q}, assuming AC1–AC4.The result applies when the resonance event has positive probability.Source: §2.1 · pp. 10–11
2.2 Access model
- The oracle returns one post-Step 7 state copy and classical E with the run-local gauge residue; offsets can vary by run, and the model does not provide same-offset copies or the full offset.The only offset information used in post-processing is v1,Q.Source: §2.2 · pp. 15–16
- Conditioned on E, the post-Step 7 coordinate state is supported on an affine grid line with offset v*(E) independent of the loop index j; reducing modulo M2 removes the grid-label term.The offset may change across invocations, while the modulo-M2 coordinates satisfy X(j) ≡ 2D^2 j b + v*(E) (mod M2).Source: §2.2 · p. 16
- The routine outputs the reduced sample uQ = u mod Q in ZQ^n.Source: §2.2 · p. 16
- One oracle query supplies a copy of |eφ7⟩ on coordinate registers X and run-local side information E.Source: §2.2 · p. 16
- The routine obtains v1,Q from E directly or computes it using E and v̄1, then applies the v1,Q-dependent diagonal unitary to X1.Source: §2.2 · p. 16
3 The new Step 9†
Step 9† uses direct Fourier sampling to obtain dual samples under AC1–AC5. With overwhelming probability, those samples recover the planted vector and, under the stated LWE conditions, the secret and error.
3 The new Step 9†
- The recovery system solves Wz ≡ y (mod Q) from accepted samples, and the centered lift recovers b before divisibility and LWE-consistency checks certify s and e.The correct vector’s centered lift is valid under the stated bound on its coordinates; the checks certify any returned solution.Source: §3 · pp. 18–19, §3.1 · p. 22
- Only the correct norm guess is guaranteed to produce the dual samples used in the theorem; incorrect guesses may fail sampling or rank recovery.The algorithm uses a polynomial trial budget and returns failure if it finds no verified solution within that budget.Source: §3 · p. 19
3.1 Correctness under Additional Conditions
- Step 9† uses direct QFT sampling; conditioned on resonance, reduced outcomes are exactly uniform on the dual hyperplane H.The proof applies the chirp correction before sampling and establishes resonance except with negligible probability.Source: §3.1 · pp. 19, 21
- With overwhelming probability, accepted samples are nonzero and resonant, uniquely recover b mod Q, and yield the verified LWE secret and error in polynomial time.The theorem’s guarantee is conditional on AC1–AC5 and the correct norm-guessing iteration.Source: §3.1 · p. 21
- Under the Gaussian-envelope hypotheses implying AC5, the method yields a quantum-polynomial-time solution to chosen-secret LWE and, via Chen’s classical reductions, standard LWE in the same parameter regime.The conclusion remains conditional on AC1–AC4 and the Gaussian-envelope hypotheses.Source: §3.1 · p. 22
4 Related Work
The related work spans classical lattice algorithms and quantum Fourier-sampling approaches to lattice problems. The paper places its post-processing contribution in the Karst-wave line of work by specifying the access promise needed for exact processing in the LWE regime.
Classical lattice algorithms
- Worst-case lattice hardness frameworks and LWE reductions underpin cryptographic constructions including lattice trapdoors and fully homomorphic encryption [Peikert, 2009, Brakerski et al., 2013].The cited work includes Regev’s quantum worst-case reductions from GapSVP and SIVP to LWE.Source: §4 · p. 23
- Classical worst-case SVP algorithms typically use sieving or discrete Gaussians, while discrete-Gaussian sampling is also a broader lattice-algorithm tool [Aggarwal et al., 2015].Source: §4 · p. 23
Quantum Fourier sampling
- Quantum lattice methods use coset- or line-supported states followed by Fourier sampling; related models include Regev’s unique-SVP reduction and the extrapolated dihedral coset problem.Source: §4 · p. 23
Karst-wave post-processing
- Chen’s Karst-wave construction uses complex-Gaussian windowing to create a shifted grid-line state with a quadratic chirp, and the present work isolates run-local access to v1,Q as an exact-post-processing promise.For Gaussian loop envelopes, one-dimensional Fourier decay supplies the needed resonance condition AC5.Source: §4 · p. 23
5 Conclusion
The paper presents a replacement post-processing step that uses run-local chirp cancellation and direct Fourier sampling. Under the stated conditions, it yields uniform reduced resonant samples and a conditional route to solving chosen-secret LWE in Chen’s qualitative parameter regime.
Conclusion
- Under AC1–AC4 and Gaussian spectral hypotheses implying AC5, Step 9† uses first-coordinate chirp cancellation and direct Fourier sampling to turn unknown affine offsets into harmless Fourier phases.Source: §5 · p. 23
- Reduced resonant samples are exactly uniform on the dual hyperplane, supporting linear-algebraic recovery over the composite ring ZQ.Source: §5 · p. 24
- The corresponding conditional instantiation with Chen’s parameters and lattice L⊥q(A) provides a direct path from a superposition supported on {jΔ + v*} to samples from the dual lattice.Source: §5 · p. 24
- Under AC1–AC4 and Gaussian-envelope hypotheses implying AC5, the resulting algorithm solves Chen’s chosen-secret LWE problem in the same qualitative parameter regime.Source: §5 · p. 24