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.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Gupte, A., Ragavan, S., & Zhandry, M. (2026). A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms. https://omanscience.com/en/articles/a-fourier-label-information-loss-barrier-for-dihedral-coset-algorithms
MLA 9
Gupte, Aparna, et al. "A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms." https://omanscience.com/en/articles/a-fourier-label-information-loss-barrier-for-dihedral-coset-algorithms.
Chicago (author–date)
Gupte, Aparna, Seyoon Ragavan, and Mark Zhandry. 2026. "A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms." https://omanscience.com/en/articles/a-fourier-label-information-loss-barrier-for-dihedral-coset-algorithms.
Harvard
Gupte, A., Ragavan, S. and Zhandry, M. (2026) 'A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms', Available at: https://omanscience.com/en/articles/a-fourier-label-information-loss-barrier-for-dihedral-coset-algorithms.
Vancouver
Gupte A, Ragavan S, Zhandry M. A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms. https://omanscience.com/en/articles/a-fourier-label-information-loss-barrier-for-dihedral-coset-algorithms
IEEE
A. Gupte, S. Ragavan, and M. Zhandry, "A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms," https://omanscience.com/en/articles/a-fourier-label-information-loss-barrier-for-dihedral-coset-algorithms.