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:2609.40062

A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms

Aparna Gupte, Seyoon Ragavan, Mark Zhandry

quant-phcs.CRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template proposed by Regev (SIAM Journal on Computing, 2004), which is one of the main approaches to solving DCP. Suppose that, after measuring the lower $n-1$ bits of the subset sum, the algorithm discards any $ω(\log n)$ bits from each of the Fourier labels. Then we prove that the algorithm cannot succeed in solving DCP. This shows that any algorithm following this template must make extensive use of the Fourier labels, and thus serves as a useful guide for developing algorithms for DCP. As a main application, we show that the recent algorithm by Simon (IACR ePrint:2026/1591, August 11 2026) does not solve DCP. We show that after the subset-sum measurement, this algorithm can be implemented (up to exponentially-small error) using only the most-significant third of the Fourier labels, and is therefore subject to our general no-go theorem. To help with verifiability, we release Lean 4 code for our results.

AI Summary

The paper asks how much classical Fourier-label information must remain available in algorithms for the dihedral coset problem (DCP) that follow Regev’s Fourier-sampling and subset-sum-measurement template. It studies the state after measuring the lower $n-1$ bits of the subset sum, for modulus $N=2^n$ and $m$ Fourier samples. The main theorem permits retaining arbitrary fixed coordinatewise digests $H_i:\mathbb Z_N\to[K]$, together with the subset-sum measurement outcome and the remaining quantum state. Any subsequent algorithm, even computationally unbounded, distinguishes even from odd secrets with advantage at most $m\sqrt{K/N}$. For polynomial $m$, discarding $\omega(\log n)$ bits per label therefore makes this advantage negligible. The proof bounds the trace-norm change from dephasing each control qubit by $\sqrt{K/N}$, using a rank-one decomposition and Cauchy–Schwarz. A hybrid argument then compares the state with a fully dephased state independent of the secret’s parity. The application concerns a recent claimed polynomial-time DCP algorithm. Its blockwise summaries can be reconstructed using only approximately the most-significant third of each label, with error $\operatorname{poly}(n)2^{-n/3}$. The theorem consequently bounds one run’s distinguishing advantage by the same order; retries and amplification cannot yield efficient recovery. The barrier is specific to this measurement template and fixed, separate digests of each label, not a general DCP lower bound. Retaining and meaningfully using fuller label information lies outside its scope. The paper also supplies accompanying Lean 4 code.

No sign of AI-generated textAI use disclosed
The authors then found a generalized no-go in conversation with GPT-5.6 Sol Pro and Ultra, and then used the same models to produce accompanying Lean 4 formalization.

Central claim may not hold: The abstract states an unrestricted information-loss barrier, whereas the theorem proves it only for fixed, sample-independent, coordinatewise digests of the Fourier labels, leaving adaptive retention and joint compression outside its scope.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

The dihedral hidden subgroup problem

Imin Chen, David I. Sun

Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.

arXiv:2106.09907•Journal of Mathematical Cryptology•Jan 1, 2024•4 citations

A reduction from LWE problem to dihedral coset problem

Fada Li, Wan‐Su Bao, Xiang-Qun Fu +2 more

Learning with Errors (LWE) problems are the foundations for numerous applications in lattice-based cryptography and are provably as hard as approximate lattice problems in the worst case. Here we present a reduction from LWE problem to dihedral coset problem(DCP). We present a quantum algorithm to generate the input of the two point problem which hides the solution of LWE. We then give a new reduction from two point problem to dihedral coset problem on D_{{({n^{13})}^{n\log n}}}. Our reduction implicate that any algorithm solves DCP in subexponential time would lead a quantum algorithm for LWE.

arXiv:1305.3769•May 16, 2013•2 citations

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•1 citation

Rigorous Statements and Proofs of the Lemmas in Simon's Algorithm for the Dihedral Coset Problem and Their Underlying Hypothesis

Yuchen Guo, Shuo Yang

In a recent preprint, Simon proposed a polynomial-time quantum algorithm for the Dihedral Coset Problem and rested the analysis on four lemmas. Three of them carry only proof sketches, and this paper gives each of those three a statement that admits a single reading together with a complete proof. Lemma 1 follows from an exact second-moment computation for the subset-sum counts, and it holds with probability tending to one in place of the constant originally claimed. The amplitude bound of Lemma 3 follows from an exact Parseval identity on the cube of measurement outcomes and holds at every threshold with no well-behavedness hypothesis, so that predicate leaves the argument entirely. For Lemma 4, we compute both balls-in-bins covariances exactly and find that the second carries a term a fixed ball count leaves out. The assumption that the distinguished group contains no faulty samples can also be dropped. The two branch amplitudes share a signed prefactor, so the counting estimates control their difference and not the ratio the lemma states. We prove the additive form and show that the closing argument consumes nothing more than that. A single hypothesis survives all of this. It asks that the partition into the two sides be fixed independently of the measured string, and the rule the algorithm gives for choosing that partition does not supply it. Establishing these four lemmas therefore does not by itself establish the correctness of the algorithm.

arXiv:2608.16598•Aug 17, 2026•1 citation

Explicit Multiregister Measurements for Hidden Subgroup Problems; or, Fourier Sampling Strikes Back

Cristopher Moore, Alexander C. Russell

We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses k = log 2 |G | registers, and each of the 2 k subsets of the registers contributes some information. While this does not, in general, yield an efficient algorithm, it generalizes the relationship between Subset Sum and the HSP in the dihedral group, and sheds some light on how quantum algorithms for Graph Isomorphism might work. 1

•Apr 8, 2005•10 citations
We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template proposed by Regev (SIAM Journal on Computing, 2004), which is one of the main approaches to solving DCP. Suppose that, after measuring the lower n−1n-1n−1 bits of the subset sum, the algorithm discards any ω(log⁡n)ω(\log n)ω(logn) bits from each of the Fourier labels. Then we prove that the algorithm cannot succeed in solving DCP. This shows that any algorithm following this template must make extensive use of the Fourier labels, and thus serves as a useful guide for developing algorithms for DCP.
As a main application, we show that the recent algorithm by Simon (IACR ePrint:2026/1591, August 11 2026) does not solve DCP. We show that after the subset-sum measurement, this algorithm can be implemented (up to exponentially-small error) using only the most-significant third of the Fourier labels, and is therefore subject to our general no-go theorem. To help with verifiability, we release Lean 4 code for our results.
The paper asks how much classical Fourier-label information must remain available in algorithms for the dihedral coset problem (DCP) that follow Regev’s Fourier-sampling and subset-sum-measurement template. It studies the state after measuring the lower n−1n-1n−1 bits of the subset sum, for modulus N=2nN=2^nN=2n and mmm Fourier samples.
The main theorem permits retaining arbitrary fixed coordinatewise digests Hi:ZN→[K]H_i:\mathbb Z_N\to[K]Hi​:ZN​→[K], together with the subset-sum measurement outcome and the remaining quantum state. Any subsequent algorithm, even computationally unbounded, distinguishes even from odd secrets with advantage at most mK/Nm\sqrt{K/N}mK/N​. For polynomial mmm, discarding ω(log⁡n)\omega(\log n)ω(logn) bits per label therefore makes this advantage negligible. The proof bounds the trace-norm change from dephasing each control qubit by K/N\sqrt{K/N}K/N​, using a rank-one decomposition and Cauchy–Schwarz. A hybrid argument then compares the state with a fully dephased state independent of the secret’s parity.
The application concerns a recent claimed polynomial-time DCP algorithm. Its blockwise summaries can be reconstructed using only approximately the most-significant third of each label, with error poly⁡(n)2−n/3\operatorname{poly}(n)2^{-n/3}poly(n)2−n/3. The theorem consequently bounds one run’s distinguishing advantage by the same order; retries and amplification cannot yield efficient recovery.
The barrier is specific to this measurement template and fixed, separate digests of each label, not a general DCP lower bound. Retaining and meaningfully using fuller label information lies outside its scope. The paper also supplies accompanying Lean 4 code.
Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.
Learning with Errors (LWE) problems are the foundations for numerous applications in lattice-based cryptography and are provably as hard as approximate lattice problems in the worst case. Here we present a reduction from LWE problem to dihedral coset problem(DCP). We present a quantum algorithm to generate the input of the two point problem which hides the solution of LWE. We then give a new reduction from two point problem to dihedral coset problem on D_{{({n^{13})}^{n\log n}}}. Our reduction implicate that any algorithm solves DCP in subexponential time would lead a quantum algorithm for LWE.
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.
In a recent preprint, Simon proposed a polynomial-time quantum algorithm for the Dihedral Coset Problem and rested the analysis on four lemmas. Three of them carry only proof sketches, and this paper gives each of those three a statement that admits a single reading together with a complete proof. Lemma 1 follows from an exact second-moment computation for the subset-sum counts, and it holds with probability tending to one in place of the constant originally claimed. The amplitude bound of Lemma 3 follows from an exact Parseval identity on the cube of measurement outcomes and holds at every threshold with no well-behavedness hypothesis, so that predicate leaves the argument entirely. For Lemma 4, we compute both balls-in-bins covariances exactly and find that the second carries a term a fixed ball count leaves out. The assumption that the distinguished group contains no faulty samples can also be dropped. The two branch amplitudes share a signed prefactor, so the counting estimates control their difference and not the ratio the lemma states. We prove the additive form and show that the closing argument consumes nothing more than that. A single hypothesis survives all of this. It asks that the partition into the two sides be fixed independently of the measured string, and the rule the algorithm gives for choosing that partition does not supply it. Establishing these four lemmas therefore does not by itself establish the correctness of the algorithm.
We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses k = log 2 |G | registers, and each of the 2 k subsets of the registers contributes some information. While this does not, in general, yield an efficient algorithm, it generalizes the relationship between Subset Sum and the HSP in the dihedral group, and sheds some light on how quantum algorithms for Graph Isomorphism might work. 1