Quantum algorithms find smallest generator sets in special groups
Quantum Algorithms for Minimum Generating Set
Computational Complexity
Summary
Figuring out the smallest set of building blocks needed to create certain complex groups is a hard problem. The authors present quantum algorithms that can efficiently find these minimum generating sets for special kinds of groups where the structure is restricted. They also show how to break down these groups into simpler parts and solve membership problems using quantum methods. For general groups, they prove the deciding problem sits in a specific complexity class, which relates to how hard the problem might be.
What this means in practice
- •For quantum algorithm developers: Design quantum algorithms that efficiently handle group decomposition and membership problems for groups with known structural constraints.
- •For cryptographers: Use insights from group decomposition and generating set problems to analyze cryptographic schemes relying on group-theoretic hardness assumptions.
A theory result. No direct application yet.
Authors
Bireswar Das, Udit Kumar, Kavita Samant, Dhara Thakkar
Abstract
In this paper, we present a polynomial-time quantum algorithm for computing a minimum-sized generating set of solvable black-box groups. Next, we consider the class $Γ_d$ of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group $S_d$ for a fixed $d$. We design polynomial-time quantum algorithms to compute the direct product decomposition of abelian factor groups and solve the constructive membership problem for factor groups of groups from $Γ_d$. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from $Γ_d$. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from $Γ_d$. Finally, we show that the minimum generating set problem for general black-box groups is in $\textrm{NP} \cap \textrm{coAM}$.