← All problems

Dihedral Coset Problem

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

References

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: O(log⁡N)O(\log N) queries but O(N)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.

Gupte, Ragavan,.

Sources

Solutions 0

No solutions have been posted yet.