Testing efficiently whether a finite set Γ 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 (Γ,⋅) 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 (Γ,⋅) 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 Γ.
展开▼
