Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1805.04179 · Lecture notes in computer science

The Hidden Subgroup Problem and Post-quantum Group-Based Cryptography

Kelsey Horan, Delaram Kahrobaei

Published Jan 1, 2018• 13 citations
arXivHTMLPDF
DOI
10.1007/978-3-319-96418-8_26

Related papers

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups

Gábor Ivanyos, Luc Sanselme, Miklós Sántha

arXiv:quant-ph/0701235•Lecture notes in computer science•Jan 1, 2007•24 citations

Post-quantum Cryptography: An Overview

Syed Ismail Abdul Lathif, Priya Saxena, Priyanshi Singh

Blockchain technologies•Jan 1, 2025•0 citations

Statistical indistihguishability and lower bounds for HSP over the symmetric group

Sergey B. Kuznetsov

We study the Hidden Subgroup Problem in the symmetric group Sn with a pairwise independent hiding function. An exponential lower bound on the complexity is proved: for a polynomial number of queries to the oracle, the problem is unsolvable by both classical and quantum algorithms. The key result is the statistical indistinguishability of the oracle response distributions for different subgroups, which makes it impossible to distinguish them even for powerful algorithms. It is shown that Fourier sampling methods are ineffective for this problem. The paper extends the class of “hard” subgroups and has important applications in post-quantum cryptography for constructing systems resistant to quantum attacks.

PRIKLADNAYa DISKRETNAYa MATEMATIKA•Sep 25, 2026•0 citations

On Quantum Algorithms for Noncommutative Hidden Subgroups

Mark Ettinger, Peter Høyer

arXiv:quant-ph/9807029•Advances in Applied Mathematics•Oct 1, 2000•135 citations

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

Yalla Jnan Devi Satya Prasad

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.

•Jan 2, 2026•0 citations

A Panorama of Post-quantum Cryptography

Paulo S. L. M. Barreto, Felipe P. Biasi, Ricardo Dahab +5 more

Springer eBooks•Jan 1, 2014•12 citations
We study the Hidden Subgroup Problem in the symmetric group Sn with a pairwise independent hiding function. An exponential lower bound on the complexity is proved: for a polynomial number of queries to the oracle, the problem is unsolvable by both classical and quantum algorithms. The key result is the statistical indistinguishability of the oracle response distributions for different subgroups, which makes it impossible to distinguish them even for powerful algorithms. It is shown that Fourier sampling methods are ineffective for this problem. The paper extends the class of “hard” subgroups and has important applications in post-quantum cryptography for constructing systems resistant to quantum attacks.
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.