A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
A no-go theorem shows Regev-style dihedral coset algorithms fail if they discard too many Fourier-label bits.
The paper proves that quantum algorithms for the dihedral coset problem following Regev's 2004 Fourier-sampling and subset-sum-measurement template cannot succeed if, after measuring the lower n−1 subset-sum bits, they discard ω(log n) bits from each Fourier label. Algorithms in this class must therefore use the Fourier labels extensively. The authors show that Simon's August 2026 algorithm (IACR ePrint 2026/1591) can be implemented, up to exponentially small error, using only the most-significant third of those labels and so does not solve the problem. Lean 4 proofs are released for verification.
- No-go theorem covers Regev's Fourier-sampling and subset-sum template for the dihedral coset problem.
- Discarding more than ω(log n) Fourier-label bits after the subset-sum measurement blocks success.
- Simon's August 2026 algorithm uses only the top third of labels and does not solve DCP.
- The authors release Lean 4 code to support verification.
- Organizations
- IACR
From the original article
1 min read at arxiv.orgWe 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.
By Aparna Gupte · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.