Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP

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.