Paper 2026/2678
From Quantum Mechanics to the Hidden Subgroup Problem: an Overview from Finite to Infinite Groups
Abstract
The Hidden Subgroup Problem (HSP for short) is an important problem in quantum computing and computational group theory, which has connections with several quantum algorithms, including Shor's algorithm for integer factorization and the discrete logarithm problem. The HSP can be stated as follows: given a function on a group that is constant and distinct on cosets of a hidden subgroup, determine the hidden subgroup efficiently. The problem captures the essence of exploiting group structures for computational advantage and provides insights into the power of quantum algorithms over classical approaches. While abelian instances of HSP are well-understood and efficiently solvable using the quantum Fourier transform, non-abelian cases remain challenging and are active areas of research. The goal of this survey is to put together all the basic background needed to understand well the Hidden Subgroup Problem in groups, reviewing recent results and discussing open problems.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Post-quantum cryptographyHidden subgroup problem
- Contact author(s)
- mnoce @ unisa it
- History
- 2026-10-31: approved
- 2026-10-29: received
- See all versions
- Short URL
- https://ia.cr/2026/2678
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2678,
author = {Federico Di Concilio and Ramón Flores and Delaram Kahrobaei and Marialaura Noce},
title = {From Quantum Mechanics to the Hidden Subgroup Problem: an Overview from Finite to Infinite Groups},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2678},
year = {2026},
url = {https://eprint.iacr.org/2026/2678}
}
