Quantum Property Testing of Group Solvability
Testing efficiently whether a finite set Gamma with a binary operation . over it, given as an oracle, is a group is a well-known open problem in the field of property testing. Recently, Friedl, Ivanyos and Santha have made a significant step in the direction of solving this problem by showing that it is possible to test efficiently whether the input (Gamma, .) is an abelian group or is far, with respect to some distance, from any abelian group. In this paper, we make a step further and construct an efficient quantum algorithm that tests whether (Gamma, .) is a solvable group, or is far from any solvable group. More precisely, the number of queries used by our algorithm is polylogarithmic in the size of the set Gamma.
property testing quantum algorithms solvable groups