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

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.

Pushing beyond the memory barrier in propagation algorithms with randomization
Manuel S. Rudolph, Ricard Puig, Slimane Thabet +1
arXiv20 Oct 2026PreprintCC BY 4.0Full textComputational physics Quantum physics & quantum informationarXiv
Information limits of photonic lantern wavefront sensing: a Fisher- and quantum-Fisher-information framework and its relation to Fourier-filtering sensitivity limits
Kalaga Madhav
arXiv16 Sep 2026PreprintarXiv licenceFull textInstrumentation & methods Optics & photonicsarXiv
Analytical modeling of LRCS for multiple scattering of Lambertian dihedral angle
Kai Liu, Yunhua Cao, Haiying Li +1
Optics Express1 Oct 2026Peer-reviewedPublisher termsApplied physics & instrumentationCrossref
Torsionator: Dihedral Parameterization and Conformer Search Made Easy.
Giorgia Brosio, Alice Triveri, Pietro Vidossich +2
Journal of chemical theory and computation1 Oct 2026Peer-reviewedCC BYFull textAtomic, molecular & optical physicsEurope PMC
Fermion mass hierarchy and flavor signals from a D₄ dihedral symmetry within a 2HDM-Tx with four-zero textures
M. A. Arroyo-Ureña, E. Díaz, J. L. Díaz-Cruz +1
arXiv4 Sep 2026PreprintCC BY 4.0Full textHigh-energy & particle physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{gupte2026fourierlabel,
  title = {{A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms}},
  author = {Aparna Gupte and Seyoon Ragavan and Mark Zhandry},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.40062},
  eprint = {2609.40062},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40062},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
AU  - Aparna Gupte
AU  - Seyoon Ragavan
AU  - Mark Zhandry
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.40062
UR  - https://arxiv.org/abs/2609.40062
AB  - 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.
ER  -

Abstract

Related

Cite