A Quantum Polynomial-Time Reduction for the Dihedral Hidden Subgroup Problem

The last century has seen incredible growth in the field of quantum computing. Quantum computation offers the opportunity to find efficient solutions to certain computational problems which are intractable on classical computers. One class of problems that seems to benefit from quantum computing is the Hidden Subgroup Problem (HSP). The HSP includes, as special cases, the problems of integer factoring, discrete logarithm, shortest vector, and subset sum - making the HSP incredibly important in various fields of research.                               

The presented research examines the HSP for Dihedral groups with order 2^n and proves a quantum polynomial-time reduction to the so-called Codomain Fiber Intersection Problem (CFIP). The usual approach to the HSP relies on harmonic analysis in the domain of the problem and the best-known algorithm using this approach is sub-exponential, but still super-polynomial. The algorithm we will present deviates from the usual approach by focusing on the structure encoded in the codomain and uses this structure to direct a “walk” down the subgroup lattice terminating at the hidden subgroup.                               

Though the algorithm presented here is specifically designed for the DHSP, it has potential applications to many other types of the HSP. It is hypothesized that any group with a sufficiently structured subgroup lattice could benefit from the analysis developed here. As this approach diverges from the standard approach to the HSP it could be a promising step in finding an efficient solution to this problem.