Quantum Property Testing of Group Solvability

Yoshifumi Inui, François Le Gall

Ron

Yoshifumi Inui

Property testing has been extensively studied and its target is to determine whether a given object satisfies a certain property or it is far from the property. In this paper, we construct an efficient quantum algorithm which tests if a given quantum oracle performs the group multiplication of a solvable group. Our work is strongly based on the efficient classical testing algorithm for Abelian groups proposed by Friedl, Ivanyos and Santha. Since every Abelian group is a solvable group, our result is in a sense a generalization of their result.

Sebastian Dörn, Thomas Thierauf

Katalin Friedl, Frédéric Magniez, Miklós Sántha +1 more

John Watrous

In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. Several other problems, such as testing membership in solvable groups, testing equality of subgroups in a given solvable group, and testing normality of a subgroup in a given solvable group, reduce to computing orders of solvable groups and therefore admit polynomial-time quantum algorithms as well. Our algorithm works in the setting of black-box groups, wherein none of these problems can be computed classically in polynomial time. As an important byproduct, our algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which yields a natural way to apply existing quantum algorithms to factor groups of solvable groups.