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

2004/06/21 by Oded Regev, Regev, Oded · 7 citations
Computer Science · Physics and Astronomy · #Coding theory and cryptography #Complexity and Algorithms in Graphs #FOS: Physical sciences #Polynomial and algebraic computation #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0406151

7 pages, 1 figure

arxiv created 2004/06/21 · openalex publication_date 2004/06/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of\n non-abelian Groups
• Noise-tolerant learning, the parity problem, and the statistical query model

Cited by

• A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective
• How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
• Improved Low-qubit Hidden Shift Algorithms
• Normalizer Circuits and Quantum Computation
• Abelian Hypergroups and Quantum Computation
• Hidden shift problem for complex functions
• Quantum Computation Beyond the Circuit Model

Related

• A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem
• The hidden subgroup problem for infinite groups
• The Hidden Subgroup Problem
• Hidden Subhypergroup Problem
• The central nature of the Hidden Subgroup problem