Quantum Property Testing for Solvable Groups

Abstract

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.

References in corpus (4)

• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
• The Hidden Subgroup Problem - Review and Open Problems
• Quantum Complexity of Testing Group Commutativity