Source-linked AI summary
A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
Aparna Gupte, Seyoon Ragavan, Mark Zhandry
TL;DR
The subset-sum oracle in Regev’s DCP template is believed to require super-polynomial time, and Simon claimed to remove it. This paper proves that algorithms in the template cannot solve DCP if they discard ω(log n) bits from each Fourier label after the subset-sum measurement, and concludes that Simon’s algorithm cannot efficiently solve DCP.
Problem
Regev’s DCP template uses a subset-sum oracle believed to require super-polynomial time, while Simon claimed to remove it.
Source: §1 · p. 1Method
The paper proves a no-go theorem for Regev-template algorithms that discard ω(log n) bits from each Fourier label after measuring the lower n −1 subset-sum bits.
Source: §1 · p. 1Results
Simon’s algorithm can be simulated up to exponentially-small error by discarding approximately 2n/3 least-significant Fourier-label bits, and therefore cannot efficiently solve DCP.
Source: §1 · p. 1Takeaways & Limitations
For algorithms following Regev’s template, even discarding ω(log n) predetermined bits can hide the least-significant bit of d, making use of the Fourier labels an inherent requirement.
Source: §1 · p. 2Variants of Simon’s algorithm may superficially evade the theorem’s formal scope without salvaging correctness; the authors know of no meaningful repair approach.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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 $\omega(\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.
1 Introduction
Regev’s template addresses the dihedral coset problem (DCP), while Simon claimed to remove its expensive subset-sum oracle. This work proves that discarding more than ω(log n) bits from each Fourier label after the subset-sum measurement precludes solving DCP, and applies the result to Simon’s algorithm.
1 Introduction
- Regev [Reg04a] showed that an efficient quantum polynomial-time DCP algorithm would yield one for hard lattice problems, and proposed a template whose implementation uses a subset-sum oracle believed to require super-polynomial time.Simon claimed a QPT algorithm following this template that removes the oracle.Source: §1 · p. 1
- After measuring the lower n −1 subset-sum bits, any algorithm following Regev’s template that discards ω(log n) bits of each Fourier label cannot solve DCP.The theorem covers algorithms that start with Fourier sampling and subset-sum measurement.Source: §1 · p. 1
- Simon’s algorithm can be simulated up to exponentially-small error by discarding approximately 2n/3 least-significant bits of each Fourier label, so it cannot efficiently solve DCP.The paper concludes that it therefore does not efficiently solve hard lattice problems or undermine lattice-based cryptosystem security.Source: §1 · p. 1
- The theorem identifies extensive use of Fourier labels as an inherent requirement for algorithms following Regev’s template; discarding even ω(log n) predetermined bits can hide d’s least-significant bit.The authors present the general result as a guide for future DCP or related lattice-algorithm work.Source: §1 · p. 2
- Variants of Simon’s algorithm may superficially evade the theorem’s formal scope without salvaging correctness; the authors know of no meaningful repair approach.They acknowledge that a genuine, plausible repair path may exist.Source: §1 · p. 2
2 Overview and Main Result
The paper analyzes Regev’s Fourier-sampling and subset-sum-measurement template for DCP, proving that discarding sufficiently many bits of the Fourier labels prevents recovery of the secret’s least-significant bit. It applies this result to Simon’s algorithm and situates the no-go among prior work on hidden subgroup problems.
2.1 Recap of Regev’s Template
- Regev’s template combines Fourier samples, measures the lower n−1 bits of a subset sum, then uses a subset-sum oracle and a Hadamard-basis measurement to reveal the least-significant bit of d.After the oracle uncomputes the control register, the state depends only on that bit.Source: §2.1 · pp. 2–3
2.2 Intuition for the No-Go
- Discarding the Fourier labels suppresses off-diagonal terms in the b-register state, making it exponentially close to a diagonal state that carries no information about d except with exponentially small probability.The intuition is that preserving coherence across b values is crucial to recovering d.Source: §2.2 · p. 3
2.3 Main Result
- If fixed digest functions retain only K possible values per Fourier label, the algorithm’s advantage for distinguishing the least-significant bit of d is at most m√K/N.The functions are fixed independently of the secret and Fourier samples.Source: §2.3 · p. 4
2.4 Specializing to Simon’s Algorithm
- Simon’s algorithm can be implemented using only the most-significant third of each Fourier label, up to poly(n)2^-n/3 error, leaving its single-run distinguishing advantage at most poly(n)2^-n/3.Across retries and amplification, either the expected runtime is Ω(2n/9) for at least one secret or the eventual advantage is at most poly(n)2^-n/9.Source: §2.4 · pp. 4–6
- The no-go covers arbitrary small digests and does not require discarding the measured z value; related hidden-subgroup no-gos are incomparable because they restrict to the dihedral setting but impose different conditions.Simon’s algorithm ignores z after Step 2, while prior results cited here include algorithms using polynomially many Fourier samples that this theorem rules out under its additional restrictions.Source: §2.4 · p. 6, §2.5 · p. 6
2.5 Related Work
- Earlier hidden-subgroup results establish that polynomially many coset samples suffice for finite groups, while polynomially many individual strong Fourier samples can fail for certain symmetric-group instances.The paper describes its no-go as incomparable to those results.Source: §2.5 · p. 6
3 Preliminaries
The preliminaries define the trace distance and distinguishing advantage used to compare quantum states and algorithms. They also provide tools for bounding these quantities under dephasing and probabilistic averaging.
3 Preliminaries
- A distinguishing advantage is also the total-variation distance between the output distributions of an algorithm on two states.Source: §3 · p. 7
- The distinguishing advantage of any algorithm is bounded by the trace distance between its input states.Source: §3 · p. 7
- The norm of an average of operators is bounded using the average of their norms, yielding a corresponding bound for averaged state differences.Source: §3 · p. 7
- Dephasing measures one register while retaining the measurement result, providing the channel used to transform a quantum state.Source: §3 · p. 7
4 Proofs
The proofs bound the effect of discarding Fourier-label information by dephasing coordinates one at a time, then apply that result to reconstructing Simon’s Step-3 summaries from digests. The resulting guessing advantage is at most poly(n)2^-n/3.
4.1 Proving Theorem 2.1
- For each coordinate, the proof bounds the change from dephasing its b_i register by analyzing rank-one blocks built from vectors whose supports differ according to b_i.Source: §4.1 · pp. 7–8
- A coordinate-by-coordinate dephasing hybrid ends with identical states for d=0 and d=1, since all surviving terms have b=b′ and lose their dependence on d.Source: §4.1 · p. 9
4.2 Proving Corollary 2.2
- Simon’s digests retain the n−ℓ most-significant bits of each Fourier label, with ℓ=⌊2n/3⌋, and are used to reconstruct the Step-3 summaries.Source: §4.2 · pp. 9–10
- The exact and reconstructed summaries agree outside BAD; their trace-distance contribution is bounded by the probability of BAD, and channel contraction controls the effect of state replacement.Source: §4.2 · pp. 10–11
- poly(n)2^-n/3 bounds Simon’s algorithm’s guessing advantage after replacing its exact Step-3 summaries with summaries reconstructed from digests.Source: §4.2 · p. 11