Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.12341

Exact Coset Sampling for Quantum Lattice Algorithms

Zhang, Yifan

Published Sep 15, 2025• 0 citations
arXivHTMLPDF

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 \,\}$.

DOI
10.48550/arxiv.2509.12341

Related papers

Beyond LWE: Post-Quantum Assumptions under a Counterfactual Break of the Dihedral Coset Problem

Ramses Fernandez

A refuted 2026 claim of an efficient quantum algorithm for the Dihedral Coset Problem (DCP) motivates this survey of the consequences of a genuine breakthrough. We distinguish a noiseless cyclic coset-state solver, a solver with a prescribed failure exponent, and an extrapolated-state solver. Regev's rare-corruption observation already makes the first hypothesis sufficient for lattice algorithms at some polynomial approximation factors; the witnessing algorithm determines the quantitative bounds. We compose unstructured reductions with explicit sample, state-preparation and success conditions, and compare their sufficient guarantees with more than thirty lattice and non-lattice assumptions. We restate the structured state conversion of Wen and Zheng and audit its forward parameter certificate; the printed bound supplies no certificate at the ML-KEM ring and modulus. We use an explicit affine embedding for heuristic gap estimates, explain the lossiness connection from decision NTRU to search Ring-LWE, and distinguish ordinary from module uniqueness. Chen's withdrawn 2024 quantum algorithm for LWE and a proposed repair of its post-processing would, if correct, reach only a many-sample, small-noise LWE regime that the failure-exponent hypothesis already covers for exponents below $1/2$, and no deployed parameter set. Tables separate rigorous consequences, heuristic comparisons and unverified applications, and distinguish solving a proof assumption from attacking a scheme. Classical structural attacks on Classic McEliece, which do not involve DCP but put the concrete security of the scheme under revision, are summarised here and analysed in detail in a companion paper. The survey closes with open questions and a scenario-planning checklist that requires a complete efficient reduction.

arXiv:2610.36731•Oct 27, 2026•0 citations

Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli

Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems. In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let $ζ_p$ be a primitive $p$-th root of unity, let $π=ζ_p-1$, and write $q=p^t$ and $L=t(p-1)$. We work over $R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)$, where the isomorphism follows from the total ramification identity $(p)=(π)^{p-1}$. We exploit the resulting $π$-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo $π^{L},π^{L-1},\ldots,π$. For every fixed prime $p$ and modulus $q=p^t$, our algorithm solves the CCP in time and sample complexity $2^{O_p(\log n\log q)}$, using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when $q=\text{poly}(n)$. This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.

quant-pharXiv:2609.34996•Sep 29, 2026•0 citations

Measurement-dependent reduction of open dynamics in the quantum phase estimation algorithm: the visible subspace and the damped Fejér kernel

Marina O. Gordeichuk, Oleg M. Kiselev

For the quantum phase estimation (QPE) algorithm we study the minimal space of observables that is sufficient to predict the entire output distribution under open dynamics of the counting register. Building on the general Krylov theory of reduction, we compute the structure of this space explicitly for the full Fourier measurement. The outcome probabilities are determined by cyclic sums of the state matrix. If the adjoint generator is diagonal on the matrix units, the spectral classes inside the residue classes of the index difference modulo the register dimension $M$ give a constructive basis, an exact dimension formula, and attainable bounds: the dimension of the visible space lies between $M$ and $M^2-M+1$. The class includes independent qubit dephasing, and an analytically solvable reference model of Gorini--Kossakowski--Lindblad--Sudarshan (GKLS) type yields a damped Fejér kernel; two random-unitary channels with the same Ramsey contrast show that higher harmonics are distinguishable in the QPE distribution. For approximate reduction we use a finite-time Gramian and an a posteriori residual estimate, with a quadratic error order for a reducing unperturbed subspace and a compatible initial state. Numerical calculations check the consistency of the representations and the behaviour of the error under non-Toeplitz perturbations.

math-phCross-listedarXiv:2610.35332•Oct 27, 2026•0 citations

Measure Now, Mitigate Later: Virtual Error Cancellation for Logical Quantum Circuits

Oles Shtanko, Saswata Roy, Shashwat Kumar +1 more

Early fault-tolerant quantum algorithms are a key step in scalable quantum computing, but are ultimately constrained by residual, uncorrectable logical errors. Logical quantum error mitigation can eliminate this bias, however its standard requirements include prior noise characterization, more complex experiments, and substantial sampling overhead. Although no mitigation technique can simultaneously overcome all three constraints, we demonstrate that the first two---noise learning and need for modified circuits---can be completely bypassed for logical circuits by leveraging only syndrome records. Specifically, we introduce virtual error cancellation: a method that, unlike previous bias-free approaches, operates entirely in classical post-processing on universal quantum circuits. We develop and numerically test end-to-end protocols that reduce the sampling overhead beyond fundamental limitations of existing syndrome-aware mitigation techniques, including syndrome-based postselection. In particular, we propose a scheme that pairs the low-latency decoder used in the experiment with a high-complexity decoder run in post-processing. In numerical simulations of a distance-7 rotated surface code, we show that our full-stack dual-decoder algorithm exhibits an error that diminishes as the number of samples increases, capable of reaching more than three orders of magnitude of suppression compared to the decoded logical error rate in an experimentally achievable setting. These results establish syndrome records as a resource for correcting universal computational estimates after quantum execution.

quant-pharXiv:2610.12400•Oct 9, 2026•0 citations

Lattice-Based Post Quantum Cryptography Using Variations of Learning with Error (LWE)

Parth D. Shah, Priteshkumar Prajapati, Dhaval Patel

Communications in computer and information science•Jan 1, 2025•3 citations

Self-verifying variational quantum simulation of lattice models (vol 569, pg 355, 2020)

Christian Kokail, Christine Maier, Rick van Bijnen +8 more

Nature•Jan 1, 2020•0 citations
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 EEE, the post-Step 7 coordinate state on (ZM)n(\mathbb{Z}_M)^n(ZM​)n is supported on an affine grid line { jΔ+v∗(E)+M2k mod M:j∈Z, k∈K }\{\, jΔ+ v^{\ast}(E) + M_2 k \bmod M : j \in \mathbb{Z},\ k \in \mathcal{K} \,\}{jΔ+v∗(E)+M2​kmodM:j∈Z, k∈K}, with Δ=2D2bΔ= 2D^2 bΔ=2D2b, M=2M2=2D2QM = 2M_2 = 2D^2 QM=2M2​=2D2Q, and QQQ odd. The amplitudes include a quadratic Karst-wave chirp exp⁡(−2πij2/Q)\exp(-2πi j^2 / Q)exp(−2πij2/Q) and an unknown run-dependent offset v∗(E)v^{\ast}(E)v∗(E). We show that Chen's Steps 8-9 can be replaced by a single exact post-processing routine: measure the deterministic residue τ:=X1 mod D2τ:= X_1 \bmod D^2τ:=X1​modD2, obtain the run-local class v1,Q:=v1∗(E) mod Qv_{1,Q} := v_1^{\ast}(E) \bmod Qv1,Q​:=v1∗​(E)modQ as explicit side information in our access model, apply a v1,Qv_{1,Q}v1,Q​-dependent diagonal quadratic phase on X1X_1X1​ to cancel the chirp, and then apply QFTZM⊗n\mathrm{QFT}_{\mathbb{Z}_M}^{\otimes n}QFTZM​⊗n​ to the coordinate registers. The routine never needs the full offset v∗(E)v^{\ast}(E)v∗(E). Under Additional Conditions AC1-AC5 on the front end, a measured Fourier outcome u∈ZMnu \in \mathbb{Z}_M^nu∈ZMn​ satisfies the resonance ⟨b,u⟩≡0(modQ)\langle b, u \rangle \equiv 0 \pmod Q⟨b,u⟩≡0(modQ) with probability 1−o(1)1 - o(1)1−o(1). Moreover, conditioned on resonance, the reduced outcome u mod Qu \bmod QumodQ is exactly uniform on the dual hyperplane H={ v∈ZQn:⟨b,v⟩≡0(modQ) }H = \{\, v \in \mathbb{Z}_Q^n : \langle b, v \rangle \equiv 0 \pmod Q \,\}H={v∈ZQn​:⟨b,v⟩≡0(modQ)}.
A refuted 2026 claim of an efficient quantum algorithm for the Dihedral Coset Problem (DCP) motivates this survey of the consequences of a genuine breakthrough. We distinguish a noiseless cyclic coset-state solver, a solver with a prescribed failure exponent, and an extrapolated-state solver. Regev's rare-corruption observation already makes the first hypothesis sufficient for lattice algorithms at some polynomial approximation factors; the witnessing algorithm determines the quantitative bounds. We compose unstructured reductions with explicit sample, state-preparation and success conditions, and compare their sufficient guarantees with more than thirty lattice and non-lattice assumptions. We restate the structured state conversion of Wen and Zheng and audit its forward parameter certificate; the printed bound supplies no certificate at the ML-KEM ring and modulus. We use an explicit affine embedding for heuristic gap estimates, explain the lossiness connection from decision NTRU to search Ring-LWE, and distinguish ordinary from module uniqueness. Chen's withdrawn 2024 quantum algorithm for LWE and a proposed repair of its post-processing would, if correct, reach only a many-sample, small-noise LWE regime that the failure-exponent hypothesis already covers for exponents below 1/21/21/2, and no deployed parameter set. Tables separate rigorous consequences, heuristic comparisons and unverified applications, and distinguish solving a proof assumption from attacking a scheme. Classical structural attacks on Classic McEliece, which do not involve DCP but put the concrete security of the scheme under revision, are summarised here and analysed in detail in a companion paper. The survey closes with open questions and a scenario-planning checklist that requires a complete efficient reduction.
The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems. In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let ζpζ_pζp​ be a primitive ppp-th root of unity, let π=ζp−1π=ζ_p-1π=ζp​−1, and write q=ptq=p^tq=pt and L=t(p−1)L=t(p-1)L=t(p−1). We work over Rq=Zq[ζp]≅Z[ζp]/(πL)R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)Rq​=Zq​[ζp​]≅Z[ζp​]/(πL), where the isomorphism follows from the total ramification identity (p)=(π)p−1(p)=(π)^{p-1}(p)=(π)p−1. We exploit the resulting πππ-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo πL,πL−1,…,ππ^{L},π^{L-1},\ldots,ππL,πL−1,…,π. For every fixed prime ppp and modulus q=ptq=p^tq=pt, our algorithm solves the CCP in time and sample complexity 2Op(log⁡nlog⁡q)2^{O_p(\log n\log q)}2Op​(lognlogq), using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when q=poly(n)q=\text{poly}(n)q=poly(n). This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.
For the quantum phase estimation (QPE) algorithm we study the minimal space of observables that is sufficient to predict the entire output distribution under open dynamics of the counting register. Building on the general Krylov theory of reduction, we compute the structure of this space explicitly for the full Fourier measurement. The outcome probabilities are determined by cyclic sums of the state matrix. If the adjoint generator is diagonal on the matrix units, the spectral classes inside the residue classes of the index difference modulo the register dimension MMM give a constructive basis, an exact dimension formula, and attainable bounds: the dimension of the visible space lies between MMM and M2−M+1M^2-M+1M2−M+1. The class includes independent qubit dephasing, and an analytically solvable reference model of Gorini--Kossakowski--Lindblad--Sudarshan (GKLS) type yields a damped Fejér kernel; two random-unitary channels with the same Ramsey contrast show that higher harmonics are distinguishable in the QPE distribution. For approximate reduction we use a finite-time Gramian and an a posteriori residual estimate, with a quadratic error order for a reducing unperturbed subspace and a compatible initial state. Numerical calculations check the consistency of the representations and the behaviour of the error under non-Toeplitz perturbations.
Early fault-tolerant quantum algorithms are a key step in scalable quantum computing, but are ultimately constrained by residual, uncorrectable logical errors. Logical quantum error mitigation can eliminate this bias, however its standard requirements include prior noise characterization, more complex experiments, and substantial sampling overhead. Although no mitigation technique can simultaneously overcome all three constraints, we demonstrate that the first two---noise learning and need for modified circuits---can be completely bypassed for logical circuits by leveraging only syndrome records. Specifically, we introduce virtual error cancellation: a method that, unlike previous bias-free approaches, operates entirely in classical post-processing on universal quantum circuits. We develop and numerically test end-to-end protocols that reduce the sampling overhead beyond fundamental limitations of existing syndrome-aware mitigation techniques, including syndrome-based postselection. In particular, we propose a scheme that pairs the low-latency decoder used in the experiment with a high-complexity decoder run in post-processing. In numerical simulations of a distance-7 rotated surface code, we show that our full-stack dual-decoder algorithm exhibits an error that diminishes as the number of samples increases, capable of reaching more than three orders of magnitude of suppression compared to the decoded logical error rate in an experimentally achievable setting. These results establish syndrome records as a resource for correcting universal computational estimates after quantum execution.