arXiv:2609.40062
A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
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.
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.
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.