The state hidden subgroup problem (StateHSP) is a recent generalization of the hidden subgroup problem. We present an algorithm that solves the non-abelian StateHSP over $N$ copies of the dihedral group of order $8$ (the symmetries of a square). This algorithm is of interest for learning non-Pauli stabilizers, as well as related symmetries relevant for the problem of Hamiltonian spectroscopy. Our algorithm is polynomial in the number of samples and computational time, and requires only constant depth circuits. This result extends previous work on the abelian StateHSP and, as a special case, provides a solution for the ordinary hidden subgroup problem on this specific non-abelian group.The state hidden subgroup problem (StateHSP) is a recent generalization of the hidden subgroup problem. We present an algorithm that solves the non-abelian StateHSP over $N$ copies of the dihedral group of order $8$ (the symmetries of a square). This algorithm is of interest for learning non-Pauli stabilizers, as well as related symmetries relevant for the problem of Hamiltonian spectroscopy. Our algorithm is polynomial in the number of samples and computational time, and requires only constant depth circuits. This result extends previous work on the abelian StateHSP and, as a special case, provides a solution for the ordinary hidden subgroup problem on this specific non-abelian group.

arXiv:2510.07872Oct 9, 20250 citations

The dihedral hidden subgroup problem

Imin Chen, David I. Sun

Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.

arXiv:2106.09907Journal of Mathematical CryptologyJan 1, 20240 citations

The state hidden subgroup problem (StateHSP) is a recent generalization of the hidden subgroup problem. We present an algorithm that solves the non-abelian StateHSP over

N

copies of the dihedral group of order

8

(the symmetries of a square). This algorithm is of interest for learning non-Pauli stabilizers, as well as related symmetries relevant for the problem of Hamiltonian spectroscopy. Our algorithm is polynomial in the number of samples and computational time, and requires only constant depth circuits. This result extends previous work on the abelian StateHSP and, as a special case, provides a solution for the ordinary hidden subgroup problem on this specific non-abelian group.