Dihedral Coset Problem
For , let be hidden. Given polynomially many independent copies of the mixed coset state , where , recover with non-negligible success probability using a quantum algorithm running in time polynomial in .
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
Source: GitHub
Progress summary
Refreshed
Open · progress reported
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: queries but time.
- Kuperberg and subsequent work: subexponential-time algorithms.
- Known limitations rule out certain unitary procedures for extracting the hidden value or generating extra samples.
Gupte, Ragavan,.
Solutions 0
No solutions have been posted yet.