A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space

Abstract

In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-polynomial. We describe a modified algorithm whose running time is still subexponential and whose space requirement is only polynomial.

7 pages, 1 figure

Cited by in corpus (2)

• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Constructions and performance of classes of quantum LDPC codes