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

References in corpus (2)

• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
• Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem

Cited by in corpus (24)

• Quantum algorithms: an overview
• 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
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• Quantum Computation Beyond the Circuit Model
• Optimal measurements for the dihedral hidden subgroup problem
• The Optimal Single Copy Measurement for the Hidden Subgroup Problem
• Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups
• Easy and hard functions for the Boolean hidden shift problem
• Ancilla-free Quantum Adder with Sublinear Depth
• On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
• Normalizer Circuits and Quantum Computation
• Improved Low-qubit Hidden Shift Algorithms
• Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups
• Abelian Hypergroups and Quantum Computation
• How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
• Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity
• Quantum pattern matching fast on average
• An Improved Query for the Hidden Subgroup Problem
• A new quantum algorithm for the hidden shift problem in ${\mathbb{Z}}_{2^t}^n$
• Three-state quantum walk on the Cayley Graph of the Dihedral Group
• Pre- and post-quantum Diffie-Hellman from groups, actions, and isogenies
• Permutation groups, minimal degrees and quantum computing