← Back to papers
A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem
M. Moore, G. Young·February 19, 2022
Computer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We present a polynomial-time quantum algorithm for the Hidden Subgroup Problem over $\mathbb{D}_{2^n}$. The usual approach to the Hidden Subgroup Problem relies on harmonic analysis in the domain of the problem, and the best known algorithm using this approach has time complexity in $2^{\mathcal{O}(\sqrt{n})}$. By focusing on structure encoded in the codomain of the problem, we develop a polynomial-time algorithm which uses this structure to direct a"walk"down the subgroup lattice of $\mathbb{D}_{2^n}$ terminating at the hidden subgroup.