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

AI summary

Overview

Research area: Quantum algorithms and post-quantum cryptography — specifically the dihedral coset problem (DCP), the dihedral hidden subgroup problem (DHSP), and the lattice-based cryptosystems whose security Regev's 2004 work tied to DCP.

Technical level: Advanced. The paper assumes familiarity with quantum states, density matrices, trace distance, and Fourier sampling over $\mathbb{Z}_N$.

Scope: A no-go theorem showing that any quantum algorithm following Regev's Fourier-sampling and subset-sum-measurement template for DCP must retain essentially all information in the Fourier labels, together with an application ruling out a recent claimed DCP algorithm by Simon (IACR ePrint:2026/1591, August 11 2026).

What This Paper Is About

Regev (SIAM Journal on Computing, 2004) showed that an efficient quantum polynomial-time algorithm for the dihedral coset problem would break proposed lattice-based post-quantum cryptography, and proposed a template for solving DCP that relies on an expensive subset-sum oracle. Simon recently claimed a quantum polynomial-time algorithm removing that oracle. This paper proves that the template cannot work if the algorithm throws away more than $\omega(\log n)$ bits of each Fourier label $y$, and uses that barrier to show Simon's algorithm does not solve DCP.

Key Contributions

1. A general information-loss barrier (Theorem 2.1). For any fixed "digest functions" $H_1,\dots,H_m : \mathbb{Z}_N \to [K]$ chosen independently of the secret and samples, any algorithm that sees only $(H_1(y_1),\dots,H_m(y_m))$, the value $z$, and the post-measurement quantum state distinguishes the least-significant bit of $d$ with advantage at most $m\sqrt{K/N}$.

2. Refutation of Simon's algorithm (Corollary 2.2). A single run of Simon's algorithm — one run with $m$ samples outputting one of ${\mathsf{restart}, 0, 1}$ — distinguishes $\mathsf{LSB}(d)=0$ from $\mathsf{LSB}(d)=1$ with advantage at most $\mathsf{poly}(n)2^{-n/3}$.

3. A simulation argument showing Simon's algorithm fits the barrier. After the subset-sum measurement, Simon's algorithm can be implemented up to exponentially small error using only the most-significant third of each Fourier label, discarding the $\approx 2n/3$ least-significant bits (and $z$).

4. Machine-checked formalization. The authors release Lean 4 code for their results at a GitHub repository to aid verifiability.

Main Findings

• Discarding $\omega(\log n)$ bits suffices to hide $\mathsf{LSB}(d)$. The qualitative takeaway is that even discarding as few as $\omega(\log n)$ bits of each $y_i$ in a predetermined way information-theoretically hides the least-significant bit of $d$.

• Coherence in the $\mathbf{b}$ register is the bottleneck. Because the secret lives in the phase, collapsing $\mathbf{b}$ loses all information about $d$ to a global phase; maintaining coherence requires retaining almost all information about $\mathbf{y}$. Dephasing a single coordinate $b_i$ of the state $\rho_d$ changes it by at most $\sqrt{K/N}$ in trace norm (Claim 4.1).

• Pairwise independence drives the argument. Outside $\mathbf{b}=0$, the function $f^1_{\mathbf{y}}$ is pairwise independent when $\mathbf{y}$ is random, so after averaging over discarded $\mathbf{y}$, all off-diagonal terms are exponentially suppressed and the state is exponentially close to the fully decohered diagonal state.

• Simon's algorithm loses the $\approx 2n/3$ least-significant bits. It groups $\mathbf{b}$ and $\mathbf{y}$ into $L = m/(c\log n)$ blocks of $c\log n$ terms, and only uses the $\log n$ most-significant bits of each blockwise inner product $\mathbf{y}^{(i)}\cdot\mathbf{b}^{(i)} \bmod N$. Changing low-order bits of $\mathbf{y}^{(i)}$ barely perturbs the inner product, so the top third of $\mathbf{y}$ suffices, at the cost of a $\mathsf{poly}(n)2^{-n/3}$ statistical error from carry cascades.

• Restarts and amplification do not rescue the algorithm. Truncating to $2^{\lfloor 2n/9 \rfloor}$ runs yields either expected runtime $\Omega(2^{n/9})$ for at least one of two secrets with opposite $\mathsf{LSB}$, or distinguishing advantage at most $\mathsf{poly}(n)2^{-n/9}$. The algorithm cannot simultaneously have subexponential expected runtime and inverse-subexponential correctness advantage.

• The barrier is broader than Simon's algorithm. It covers arbitrary small digests (not just the first few MSBs of blockwise subset sums) and does not require the algorithm to discard $z = f^1_{\mathbf{y}}(\mathbf{b})$ (Remark 2.5). Superficial fixes that merely retain or postpone measuring $\mathbf{y}$ are handled in Remark 2.3 by commuting the measurement to the end of Step 1.

Methodology in Plain English

The authors model Regev's template in two stages. First, the algorithm collects $m = kn^{c+1}$ DCP Fourier samples, giving a uniform $\mathbf{y} \in \mathbb{Z}_N^m$ and a phase state encoding $\langle \mathbf{y},\mathbf{b}\rangle$. Second, it computes the subset sum in superposition and measures the lower $n-1$ bits, obtaining $z$; the remaining state depends only on $\mathsf{LSB}(d)$ but stays coherent across all $\mathbf{b}$ consistent with $z$.

The proof then asks: what happens if the algorithm is allowed to remember only a compressed "digest" $H_i(y_i)$ of each coordinate, with output size $K$? They write down the resulting mixed state $\rho_d$, dephase one coordinate at a time to get $\rho_{d,i}$, and bound the trace distance $|\rho_d - \rho_{d,i}|_1 \le \sqrt{K/N}$. The bound comes from decomposing the difference into rank-1 blocks built from two vectors $\ket{\phi_0}$ and $\ket{\phi_1}$ whose squared norms they compute exactly, then applying Cauchy–Schwarz. Since every coordinate can be dephased without changing the state much, the $\mathbf{b}$ register becomes essentially classical and the secret is statistically hidden. Distinguishing advantage is then bounded by trace distance (Lemma 3.2).

To apply this to Simon's algorithm, the authors show the post-measurement computation depends only on the top third of each $y$, making Simon's procedure a valid digest with small $K$, and plug in.

Why This Matters

• Corrects the record on a claimed breakthrough. The paper rules out a claimed quantum polynomial-time algorithm for DCP that, if correct, would have undermined lattice-based post-quantum cryptography. It also shows Simon's algorithm does not yield efficient algorithms for hard lattice problems.

• Guides algorithm design. Because the barrier is general, it tells future researchers that any algorithm in Regev's template must make extensive use of the full Fourier labels — a concrete design constraint rather than a statement about one algorithm.

• Separates DCP from other HSP instances. Prior no-gos (Moore–Russell–Schulman; Hallgren–Moore–Rötteler–Russell–Sen) concern symmetric-group/graph-isomorphism instances; this one is specific to the dihedral setting and rules out a class of algorithms that could otherwise work with polynomially many Fourier samples.

Real-world applications (as motivations in the paper):

• Security assessment of proposed post-quantum lattice-based cryptography.
• Understanding the limits of quantum cryptanalysis against lattice schemes.
• Benchmarking claims of quantum speedups for hidden subgroup problems.
• Providing formally verified (Lean 4) reference results for the quantum algorithms community.

Industry relevance: Directly relevant to organizations deploying or standardizing lattice-based post-quantum cryptography, and to quantum-computing groups (two authors are affiliated with Google Quantum AI) evaluating which claimed quantum attacks are real.

Future Directions

• Extending the barrier beyond the template. The authors express hope that the no-go can extend beyond refuting Simon's algorithm and help guide work on DCP and related problems such as lattices.
• Identifying genuine repair paths. The authors note a "genuine and plausible repair path" circumventing Theorem 2.1 might exist, but state they are not aware of one; finding or ruling out such a path is open.
• Handling variants that evade the formal scope. Remark 2.3 sketches superficial circumventions (retaining an unused $\mathbf{y}$ register, postponing measurement) that the authors argue do not salvage correctness; characterizing all such variants remains open.
• Reconciling with sample-efficient DCP algorithms. Existing algorithms solving DHSP with polynomially many Fourier samples are ruled out only under the paper's additional restrictions, leaving the boundary between the two regimes to be sharpened.

Target Audience

Quantum algorithms and quantum-cryptography researchers, especially those working on hidden subgroup problems, DCP, and lattice-based cryptanalysis; cryptographers assessing post-quantum security claims; and formally-verification researchers interested in the accompanying Lean 4 development. Readers need graduate-level quantum computing background to follow the proofs, though the informal statements in Section 1 and the intuition in Section 2.2 are accessible to a broader technical audience.

Authors’ 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.