Polynomial-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Polynomial-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Definitions and mathematical statement

Use the convention $D_N=\langle r,s:r^N=s^2=e,\ srs=r^{-1}\rangle$, a group of order $2N$. An oracle $f:D_N\to\mathcal Y$ hides $H$ when its fibers are the left cosets of $H$, and a quantum algorithm may query the oracle coherently. The target is a bounded-error algorithm outputting generators for $H$ with time and workspace both polynomial in $\log N$, under the standard succinct group encoding. Measuring polynomial complexity in $N$ instead would weaken the claim exponentially. A subexponential algorithm or a polynomial-query procedure whose nonquery processing is expensive does not meet the selected time requirement.

Formulation and concept references: [S1].

Short English statement

Can a quantum computer recover a hidden subgroup of a dihedral group using time and memory polynomial in the group's logarithmic size?

Research attempt

Current frontier.

Kuperberg's sieve gives a subexponential-time algorithm [S1]; Regev obtains polynomial space with subexponential time [E1]. The optimal-measurement analysis of Bacon--Childs--van Dam separates sufficiently many coset samples from an efficient implementation of the measurement [E2], Sections 3--5 and 8. This distinction is central: a polynomial number of oracle queries does not establish polynomial running time.

There is also a 2026 claim requiring particular caution. Simon's [E3] claims a polynomial-time dihedral-coset algorithm and acknowledges a correction involving the distribution used in an independence argument. Guo--Yang's audit [E4], Hypothesis (U) and Section V.6, identifies a needed independence of a partition from the measured string that the stated selection rule does not provide. Gupte--Ragavan--Zhandry subsequently give a preprint claiming a no-go result for that algorithm and a broader template [E5]. These are respectively a disputed positive claim, a conditional lemma audit, and a negative analysis of a specified algorithm, not an established solution or a general impossibility theorem for the present problem. The derivation below does not assume the positive claim, nor rely on unaudited formal-verification code attached to the negative analysis.

Attack route.

Try to coherently compress a superposition of subset sums without retaining information about which subset produced the sum. Unlike a classical collision search, such compression preserves the hidden phase and would enable a Fourier measurement. I derive a finite-size success bound valid for every integer $N$, including composite $N$, and then test whether ordinary reversible arithmetic, postselection, or adaptive averaging actually implements the required compression. The missing step will be stated as a uniform circuit construction, with both time and workspace charged.

Attempt.

1. The precise coherent operation. First suppose the hidden subgroup is $\{e,r^a s\}$, with $a\in{\mathbb{Z}}/N{\mathbb{Z}}$. Fourier sampling of a coset state gives a uniform known $k\in{\mathbb{Z}}/N{\mathbb{Z}}$ and a qubit $2^{-1/2}(|0\rangle+\omega^{ak}|1\rangle)$, where $\omega=e^{2\pi i/N}$. This uses the catalogue's convention that $r$ is the rotation. For $t$ independent samples, put $M=2^t$ and $\mathbf k=(k_1,\ldots,k_t)$. Then \[ |\psi_{a,\mathbf k}\rangle =\frac1{\sqrt M}\sum_{b\in\{0,1\}^t} \omega^{a(\mathbf k\cdot b)}|b\rangle. \tag{216.1} \] For $x\in{\mathbb{Z}}/N{\mathbb{Z}}$ let \[ \eta_x=\#\{b:\mathbf k\cdot b=x\},\qquad |S_x\rangle=\eta_x^{-1/2}\sum_{\mathbf k\cdot b=x}|b\rangle \quad(\eta_x>0). \] The nonempty-fiber states are orthonormal. Consequently there exists an isometry on their span sending $|S_x\rangle$ to $|x\rangle$, with ancillas included so it extends to a unitary on a full register space. Existence of this unitary is not an efficient construction. If it were efficiently available, $216.1$ would become \[ \sum_x\sqrt{\eta_x/M}\,\omega^{ax}|x\rangle. \] After the inverse Fourier transform over ${\mathbb{Z}}/N{\mathbb{Z}}$, the probability of outputting $a$ would be \[ P_{\mathbf k}=\frac1{NM}\left(\sum_x\sqrt{\eta_x}\right)^2. \tag{216.2} \] This is the subset-sum measurement framework of [E2], written here to expose the exact circuit operation rather than to claim a new measurement principle.

2. A quantitative bound with only four extra qubits. For distinct bit strings $b,c$, at least one coordinate of $b-c$ equals $1$ or $-1$. Conditional on all other $k_i$, the value $\mathbf k\cdot(b-c)$ is therefore uniform modulo $N$. No primality assumption is used. Counting ordered pairs gives the exact second moment \[ {\mathbb{E}}_{\mathbf k}\sum_x\eta_x^2 =M+\frac{M(M-1)}N. \tag{216.3} \] Put $p_x=\eta_x/M$ and $X=N\sum_xp_x^2-1\ge0$. Then ${\mathbb{E}} X=(N-1)/M$. Hölder's inequality gives \[ 1=\sum_x (\sqrt{p_x})^{2/3}(p_x^2)^{1/3} \le\left(\sum_x\sqrt{p_x}\right)^{2/3} \left(\sum_xp_x^2\right)^{1/3}. \] Combining this with $216.2$ and Jensen's inequality yields \[ P_{\mathbf k}\ge\frac1{1+X},\qquad {\mathbb{E}}_{\mathbf k}P_{\mathbf k} \ge\frac{M}{M+N-1}. \tag{216.4} \] Thus $t=\lceil\log_2N\rceil+4$ gives average success at least $16/17$. The average is over fresh independent Fourier labels, and the bound holds for each fixed secret $a$. It is not an average over favorable secrets. The reproduction script enumerates all label tuples for selected small prime and composite $N$, checking $216.3$ exactly and $216.2$--$216.4$ numerically; the inequalities themselves have the proof above.

Here is an explicit sufficient computational hypothesis. For this value of $t$, suppose one uniform algorithm constructs, from $N,\mathbf k$, a circuit using $\operatorname{poly}(\log N)$ gates and ancilla qubits, whose action differs from the compression isometry by at most $\delta=1/100$ in operator norm on the entire fiber-state span, except for at most a fraction $\beta=1/100$ of the uniform label tuples. Uniformity includes the classical circuit-generation cost. The loss of success probability on a good tuple is at most $2\delta$; bad tuples lose at most one each. An approximate Fourier transform with another fixed small error then leaves success above $2/3$. Thus this unproved compression hypothesis implies a bounded-error polynomial-time, polynomial-space solution of the reflection case.

3. Returning from reflections to every subgroup. Restricting the oracle to $\langle r\rangle$ is an abelian hidden-subgroup problem and recovers $H\cap\langle r\rangle=\langle r^h\rangle$, where $h\mid N$, with high probability. This subgroup is normal in $D_N$ and contained in $H$. The oracle descends to the quotient $D_h$, in which the hidden subgroup is either trivial or generated by one reflection. Use the preceding routine there. A proposed reflection is checked by comparing its oracle value with $f(e)$. In the trivial case no proposed reflection can pass; in the nontrivial case the correct one passes with the derived constant probability. Repetition and verification bound the error. Together with $r^h$, a passing reflection gives generators of the original $H$. The constant-size cases are handled directly. This is the usual reduction explained in [E2], Section 3, and ensures the conditional result is not only for one subgroup type or powers of two.

4. Why computing the subset sum is not compression. Reversible arithmetic easily implements \[ |b\rangle|0\rangle\longmapsto|b\rangle|\mathbf k\cdot b\rangle. \] After this operation, $216.1$ gives \[ \frac1{\sqrt M}\sum_b\omega^{a(\mathbf k\cdot b)} |b\rangle|\mathbf k\cdot b\rangle. \tag{216.5} \] Discarding the first register leaves exactly $\sum_xp_x|x\rangle\langle x|$, independent of $a$. The phase information is lost, not transferred to a Fourier-readable register. Also, a map erasing every basis string in a many-to-one fiber cannot be unitary: it would identify orthogonal vectors. The permissible isometry acts only on the uniform fiber states; constructing it requires coherent control of those states and their orthogonal complements.

Starting with the uniform superposition on all bit strings, computing the sum and postselecting a specified value $x$ succeeds with probability $\eta_x/M$. For nearly uniform fibers this is approximately $1/N$, even when $M$ is much larger than $N$. Repeating this preparation costs order $N$, and generic amplitude amplification costs order $\sqrt N$. Both are exponential in $\log N$. This rejects a particular preparation method, not every possible efficient construction of the isometry.

5. Stress-testing outcome-dependent averaging. An independent elementary model illustrates why a distributional premise must survive selection. Let $Z_1,\ldots,Z_m$ be independent uniform signs. Select the first index with $Z_i=+1$, or the last index if all signs are negative. Although each fixed $Z_i$ has expectation zero, the selected sign has expectation \[ {\mathbb{E}} Z_{\mathrm{selected}}=1-2^{1-m}. \tag{216.6} \] A fixed-index cancellation estimate is therefore useless for this outcome-dependent selection. In the actual 2026 audit, the concern is specifically a partition chosen using all-zero measured blocks, rather than a partition fixed independently of the measured string [E4], Hypothesis (U). Equation $216.6$ does not by itself refute that quantum algorithm; it prevents replacing the missing argument by an unjustified appeal to unbiasedness. Fixing the partition in advance may restore a formal independence premise but also changes its success probability and the subsequent algorithm, which must then be reanalyzed.

Stress test.

The second-moment calculation uses unconditioned independent $k_i$ only; it is not transferred to adaptively chosen label distributions. The compression hypothesis asks for error control on a subspace, not separate small errors on basis vectors that might accumulate coherently. Its circuit must be generated uniformly; an exponentially long table of fiber states cannot be called advice of negligible cost. The analysis includes workspace, nonempty and empty fibers, composite moduli, oracle verification, and the rotational subgroup reduction.

The connection to subset-sum state preparation is already part of the literature [E2]. The finite-size derivation identifies where the computational obstacle lies; it does not remove that obstacle or claim novelty for the general reduction. Nor does a no-go result for a particular uncomputation template [E5] rule out alternative measurements. No conclusion about $\mathrm P$ versus $\mathrm{NP}$ follows from the calculation: an average-case coherent operation in a quantum algorithm is not a classical worst-case solver for all subset-sum instances.

Outcome.

Outcome: Conditional reduction.

For every modulus, a uniform efficient fiber-compression circuit with the specified subspace error bound would solve the full dihedral hidden-subgroup problem within both requested resource bounds. The success estimate is explicit, with $\lceil\log_2N\rceil+4$ samples sufficient for ideal average success at least $16/17$. The needed circuit has not been constructed. Reversible sum evaluation, discarding the subset register, naive postselection, and unsupported adaptive-independence arguments do not supply it. The current attempt therefore does not establish a polynomial-time quantum algorithm.

Sources

• S1 G. Kuperberg, SIAM J. Comput. 35$1$:170-188, 2005. https://doi.org/10.1137/S009753970343603X. Catalogue formulation source.
• E1 O. Regev, "A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space," arXiv:quant-ph/0406151 $2004$. https://arxiv.org/abs/quant-ph/0406151.
• E2 D. Bacon, A. M. Childs and W. van Dam, "Optimal measurements for the dihedral hidden subgroup problem," arXiv:quant-ph/0501044v2 (26 April 2005), Sections 3--5 and 8, especially the subset-sum states in equations $14$--$15$. https://arxiv.org/pdf/quant-ph/0501044v2.
• E3 D. R. Simon, "A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem," IACR ePrint 2026/1591, archive record last revised 17 August 2026. Disputed positive claim; the archive notes a corrected independence argument and a subsequent objection. https://eprint.iacr.org/2026/1591.
• E4 Y. Guo and S. Yang, "Rigorous Statements and Proofs of the Lemmas in Simon's Algorithm for the Dihedral Coset Problem and Their Underlying Hypothesis," arXiv:2608.16598v1, Hypothesis (U), Sections IV and V.6. Conditional analysis, not a proof of the full algorithm. https://arxiv.org/html/2608.16598v1.
• E5 A. Gupte, S. Ragavan and M. Zhandry, "The ePrint:2026/1591 Quantum Algorithm Does Not Solve DCP," IACR ePrint 2026/1693, revised 1 September 2026. Preprint negative analysis of a specified algorithm/template; its accompanying formal code was not independently audited here. https://eprint.iacr.org/2026/1693.