Quantum Isomorphism Testing for Semidirect Product Groups

摘要

The group isomorphism problem asks whether two given groups are isomorphic or not, a problem closely connected to the graph isomorphism problem. In this paper, we give an efficient quantum algorithm solving this problem for a class of solvable groups, including the class of semidirect product groups of the form Z_(p~r) × Z_q where p and q are distinct primes. The running time of this algorithm is polylogarithmic in the orders of the input groups.