A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem

02/19/2022

∙

by   Matthew Moore, et al.

∙

0

∙

share

We present a polynomial-time quantum algorithm for the Hidden Subgroup Problem over 𝔻_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^𝒪(√(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 𝔻_2^n terminating at the hidden subgroup.