Reviving Algebraic Structure Approaches for Hidden Subgroup Variants and Novel Quantum Speedups in the NISQ Era

The Hidden Subgroup Problem (HSP) unifies several landmark quantum algorithms, yet systematic exploration of its variants and modern applications has slowed. This paper revives HSP-based algorithm design by examining new group structures with direct relevance to post-quantum cryptography, lattice problems, and structured optimization. We classify a family of finite and continuous groups-extensions and semi-direct products of abelian groups, matrix groups, and certain non-abelian groups-according to their Fourier-theoretic properties and the feasibility of efficient quantum Fourier transforms (QFTs). For each class, we determine whether the HSP admits an efficient quantum algorithm, a subexponential-time quantum algorithm, or appears intractable even quantumly. We construct explicit algorithms for eight new problem families, including structured lattice enumeration, automorphism groups of certain graphs, and algebraic attack primitives appearing in code-based and multivariate cryptosystems. For these, we show superpolynomial quantum speedups over all known classical approaches under standard complexity assumptions. We also discuss how approximate and block-encoded QFTs can be combined with variational post-processing to make some of these HSP algorithms more NISQ-friendly. Our results demonstrate that algebraic-structure-based quantum algorithms remain a rich and underexploited direction with both theoretical depth and potential cryptanalytic and optimization applications.