For N=2^n, let s∈Z_N be hidden. Given polynomially many independent copies of the mixed coset state rho_s=frac1N∑_x∈Z_N|phi_s,xrangle langlephi_s,x|, where |phi_s,xrangle=frac1√2(| 0 rangle| x rangle+| 1 rangle| x+s rangle), recover s with non-negligible success probability using a quantum algorithm running in time polynomial in n.

Dihedral Coset Problem

For $N=2^n$ , let $s\in\mathbb{Z}_N$ be hidden. Given polynomially many independent copies of the mixed coset state $\rho_s=\frac{1}{N}\sum_{x\in\mathbb{Z}_N}\lvert\phi_{s,x}\rangle\langle\phi_{s,x}\rvert$ , where $\lvert\phi_{s,x}\rangle=\frac{1}{\sqrt{2}}(\lvert 0\rangle\lvert x\rangle+\lvert 1\rangle\lvert x+s\rangle)$ , recover $s$ with non-negligible success probability using a quantum algorithm running in time polynomial in $n$ .

Progress summary

Partially solved

A formalized refutation challenges a proposed fast quantum route to the problem, but the Dihedral Coset Problem itself remains open.

The problem remains open despite a recent claim of a polynomial-time quantum algorithm by Daniel R. Simon. That claim would have consequences for lattice problems, but it has not been established as a solution.

Known results

Ettinger--Hoyer: $O(\log N)$ queries but $O(N)$ time.
Kuperberg and subsequent work: subexponential-time algorithms.
Known limitations rule out certain unitary procedures for extracting the hidden value or generating extra samples.

August 2026 formalized obstruction

Gupte, Ragavan, and Zhandry presented a Lean-checked formalization of an information-theoretic obstruction to Simon’s claimed algorithm and its Regev-template consequence. This challenges the proposed polynomial-time route, not the Dihedral Coset Problem itself; the formalization and its interpretation remain subject to ordinary mathematical review.

Current status (as of August 2026): The proposed polynomial-time algorithm is challenged by a formalized obstruction, while no polynomial-time solution or proof of hardness for the Dihedral Coset Problem is established.

Sources

Sources & referencesView supporting material

Primary source

GitHub

Additional references

Refutation formalization for the claimed DCP algorithm — GitHub — Gupte, Ragavan, Zhandry
Refutation note on the claimed DCP algorithm — IACR Cryptology ePrint Archive — Gupte, Ragavan, Zhandry

2 days ago