Hidden Subhypergroup Problem

2006/09/28 by Massoud Amini, Amini, Massoud, Mehrdad Kalantar +3
Computer Science · Engineering · #FOS: Physical sciences #Polynomial and algebraic computation #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.quant-ph/0609220

openalex publication_date 2006/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Hidden Subgroup Problem is used in many quantum algorithms such as Simon's algorithm and Shor's factoring and discrete log algorithms. A polynomial time solution is known in case of abelian groups, and normal subgroups of arbitrary finite groups. The general case is still open. An efficient solution of the problem for symmetric group S_n would give rise to an efficient quantum algorithm for Graph Isomorphism Problem. We formulate a hidden sub-hypergroup problem for finite hypergroups and solve it for finite commutative hypergroups. The given algorithm is efficient if the corresponding QFT could be calculated efficiently.

Citations

• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of\n non-abelian Groups

Related

• The Hidden Subgroup Problem
• Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem
• A Note on the Quantum Query Complexity of the Hidden Subgroup Problem
• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of\n non-abelian Groups
• A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective