Quantum limits found for key dihedral coset problem algorithms
A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
Cryptography and Security
Summary
Some quantum algorithms try to solve a math puzzle called the dihedral coset problem, which is important for understanding quantum computing power. The authors found a barrier: if these algorithms ignore certain key parts of the quantum data too much, they just can’t solve the problem. This includes a recent algorithm that was thought to work but actually fails under this new rule. Their work helps guide which quantum methods are unlikely to succeed, saving time for future research.
What this means in practice
- •For quantum algorithm designers: Avoid designing dihedral coset algorithms that discard large portions of Fourier label data, focusing efforts on comprehensive data use.
- •For quantum software developers: Prevent implementation of quantum solvers for the dihedral coset problem that rely only on partial Fourier label information, ensuring correctness.
A theory result. No direct application yet.
Authors
Aparna Gupte, Seyoon Ragavan, Mark Zhandry
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.