Exact Coset Sampling for
Quantum Lattice Algorithms

The Problem: An Erroneous Step

Recent work by Chen et al. (2024) introduced a powerful quantum algorithm for lattice problems. However, a critical subroutine, Step 9, which is responsible for enforcing a modular linear constraint, contained an error. The original step attempts a “domain extension” that misuses amplitude periodicity, leading to a quantum state with support of the incorrect size and hence an incorrect Fourier sampling distribution. The goal is to produce a random vector $\mathbf{u}$ that satisfies: $$ \langle \mathbf{b}^*, \mathbf{u} \rangle \equiv 0 \pmod{P} $$

Our Solution: Step $9^\dagger$

Our replacement is a self‑contained unitary. The core idea is to synthesize a uniform cyclic coset by coherently shifting along the $\mathbf b^*$ direction and taking a difference that cancels offsets. We emphasize a J‑free default realization that avoids re‑evaluating the state‑preparation on superpositions and uses only classical reversible arithmetic.

Figure: Corrected Step $9^\dagger$. The procedure factors the state and yields an exactly uniform superposition over a CRT‑coset; a QFT then enforces the modular relation. (A re‑evaluation variant with an auxiliary copy is also supported.)

Key Advantages

• Correctness: Provably enforces the intended modular hyperplane via character orthogonality.
• Exact Offset Cancellation: The unknown offsets $\mathbf{v}^*$ are removed identically by the pair‑shift difference; no knowledge of $\mathbf{v}^*$ is required.
• No Reliance on Amplitude Periodicity: Our subroutine does not use any arguments based on amplitude periodicity or phase flattening, which were the source of the original error.
• Efficiency: Uses only $\mathrm{poly}(\log M_2)$ gates and is fully reversible; asymptotics are preserved.
• Simplicity: Built from standard primitives (QFT, modular arithmetic, CNOT) with phase‑free classical reversible arithmetic.
• Mild Assumption: A residue‑accessibility condition is needed only for coherent cleanup (to erase the coset label); all other steps are unconditional.

The corrected Step $9^{\dagger}$ is a drop‑in replacement for the original subroutine. We recommend the J‑free default path summarized below.

Algorithm: Step 9_dagger — Pair-shift difference (J-free) and QFT

Input: Affine-register block X (mod M₂); cached Δ := X(1) − X(0) from basis harvest.

1. Prepare T ← uniform over Z_P (e.g., per-prime QFTs + CRT wiring).
2. Compute Z ← − T · Δ  (mod M₂) via reversible double-and-add (Δ read-only).
3. Cleanup (required for interference):
   a. For each p_η | P, choose i(η) with Δ_{i(η)} ≠ 0 (mod p_η);
      set T'_η ← − Δ_{i(η)}^{-1} · Z_{i(η)} (mod p_η); CRT-recombine T'.
   b. Set T ← T − T' (so T = 0) and uncompute T' by inverting its construction.
4. Apply QFT_{Z_{M₂}}^{⊗ n} to Z and measure u.

Output: u satisfies ⟨b*, u⟩ ≡ 0 (mod P), uniformly over the solution set.

Note. A re‑evaluation variant (with auxiliary copy $Y$ and label $J\equiv j\ (\bmod P)$) is also supported; it yields the same $Z$ and final distribution.

The correctness of the algorithm stems from creating a uniform superposition over a CRT-coset. After applying the QFT, the amplitude $A(\mathbf{u})$ for measuring a state $\mathbf{u}$ becomes a geometric sum that evaluates to zero unless the desired condition is met:

$A(\mathbf{u}) = \frac{1}{\sqrt{M_2^n P}} \sum_{T=0}^{P-1} \left( \exp\left( \frac{2\pi i}{P} \cdot (-2)\,\langle \mathbf{b}^*, \mathbf{u}\rangle \right) \right)^T$

Since $P$ is odd, this sum is non‑zero if and only if $\langle \mathbf{b}^*, \mathbf{u} \rangle \equiv 0 \pmod{P}$. The measurement outcomes are therefore uniformly distributed over the solution space, exactly as required.

Residue accessibility. This condition is used only in cleanup to coherently erase $T$ from $(\mathbf Z \bmod P)$; without cleanup, QFT on $\mathbf Z$ alone is uniform over $(\mathbb Z_{M_2})^n$ and does not enforce the constraint.

If you find this work useful in your research, please cite our paper:

@article{zhang2025exact,
  title={Exact Coset Sampling for Quantum Lattice Algorithms},
  author={Yifan Zhang},
  journal={arXiv preprint arXiv:2509.12341},
  year={2025}
}