Polynomial-time quantum algorithm for the Dihedral Hidden Subgroup Problem

Problem

Does the Dihedral Hidden Subgroup Problem admit a quantum algorithm whose running time is polynomial in the input length?

For a positive integer \(N\), let the dihedral group be

\begin{equation} D_N=\langle r,s\mid r^N=1,\ s^2=1,\ srs=r^{-1}\rangle , \tag{1} \end{equation}

so that \(D_N\) has order \(2N\). Consider an oracle \(f:D_N\to X\) promised to hide a subgroup generated by an unknown reflection. Equivalently, for an unknown \(a\in\mathbb Z_N\), let

\begin{equation} H_a=\{1,sr^a\}, \qquad f(x)=f(y)\iff xH_a=yH_a . \tag{2} \end{equation}

Given quantum oracle access to \(f\), the task is to recover \(a\), and hence \(H_a\) in (2). The open question is whether this can be done with bounded error using a number of elementary quantum operations polynomial in \(\log N\), where \(D_N\) is defined by (1).

Source

Implicit in the Dihedral Hidden Subgroup Problem literature, with the current-status formulation supported by Chen and Sun [CS24]. The wording above is a contributor formulation rather than a verbatim open question attributed to Kuperberg, Regev, or Chen and Sun.

Progress

Kuperberg developed subexponential-time quantum algorithms for the Dihedral Hidden Subgroup Problem; his collimation-sieve formulation runs in \(\exp(O(\sqrt{\log N}))\) quantum time, uses \(O(\log N)\) quantum space and subexponential classical space, and no polynomial-time algorithm follows from this sieve framework [Kup13].
Regev showed that an efficient solution to the relevant dihedral coset problem would yield a quantum algorithm for certain instances of unique shortest vector problems, establishing a direct link between the dihedral problem and quantum algorithms for lattice problems [Reg04].
Chen and Sun give a modern account of the Dihedral Hidden Subgroup Problem, including obstructions to standard Fourier sampling and bounds for algorithms acting on dihedral coset states; their survey treats the quantum complexity of the problem as unresolved and records subexponential algorithms as the established general algorithmic regime [CS24].
A polynomial-time algorithm for the closely related Dihedral Coset Problem was claimed in a 2026 preprint, but Gupte, Ragavan, and Zhandry proved that the proposed algorithm cannot recover even the least-significant bit of the secret with non-negligible advantage and therefore does not solve the Dihedral Coset Problem; their no-go result also indicates that successful Regev-type constructions may need to retain and exploit substantially more classical Fourier-label information during uncomputation [GRZ26].

Comment

The Dihedral Hidden Subgroup Problem is one of the central instances of non-Abelian hidden subgroup problems and, through Regev’s reduction (Progress above), is directly tied to quantum algorithms for lattice problems; the zoo’s record on a polynomial-time quantum algorithm for Learning With Errors is given a related problem link. No polynomial-time quantum algorithm is known in the standard oracle model.

References

[Kup13]: Greg Kuperberg, “Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem,” in 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), LIPIcs 22, 20–34 (2013).DOI arXiv
[Reg04]: Oded Regev, “Quantum Computation and Lattice Problems,” SIAM Journal on Computing 33, 738–760 (2004).DOI arXiv
[CS24]: Imin Chen and David Sun, “The Dihedral Hidden Subgroup Problem,” Journal of Mathematical Cryptology 18, Article 20220029 (2024).DOI arXiv
[GRZ26]: Aparna Gupte, Seyoon Ragavan, and Mark Zhandry, “The ePrint: 2026/1591 Quantum Algorithm Does Not Solve DCP,” Cryptology ePrint Archive, Paper 2026/1693 (2026). ePrint 2026/1693.link

Polynomial-time quantum algorithm for the Dihedral Hidden Subgroup Problem

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems