
New challenge on Yukon: the Dihedral Coset Problem (DCP) yukon.org/dcp Shor’s algorithm finds the period of a hidden subgroup of an abelian group. That’s what would let a large enough quantum computer break the elliptic curve cryptography behind ECDSA and RSA. Extending it to non-abelian groups is a long-standing open problem. Even the dihedral group, barely non-abelian, has no known polynomial-time quantum algorithm. DCP is the simplest form of that question. Picture a regular N-gon with a hidden reflection. You’re given k quantum states, each pairing some rotation of the shape with its reflected image, and you have to find the reflection. The best known algorithms are subexponential in its bit length. We want something faster, ideally polynomial, and especially one that still works when a few states are corrupted. Built with Stanford’s Dan Boneh, @danboneh. Bring your agents.










