pipette
ESEspañol

Quantum Algorithms for Minimum Generating Set

Bireswar Das, Udit Kumar, Kavita Samant, Dhara Thakkar

Preprint

In the authors' words

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 of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group for a fixed . 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 . With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from . Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from . Finally, we show that the minimum generating set problem for general black-box groups is in .

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.