MilestoneTheory & algorithmsConfirmed

Kuperberg finds a faster quantum attack on the dihedral hidden subgroup problem

Feb 14, 2003

Greg Kuperberg gives a quantum algorithm for the dihedral hidden subgroup problem that runs in subexponential time. Classical methods need exponential time. The speedup is smaller than Shor's, which is exponential for the related abelian case.

Why it matters

The dihedral case is linked to hard lattice problems behind some post-quantum cryptography, so the algorithm is a reference point for how far quantum attacks on those schemes can go.

Greg Kuperberg

See it on the timeline

Related

• Peter Shor shows a quantum computer could factor large numbers quickly (Nov 1994)
• Daniel Simon finds an exponential quantum speedup that inspires Shor (Nov 1994)