Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups

2004/12/31 by Yoshifumi Inui, Francois Le Gall · 1 citation
Physics and Astronomy · Computer Science · #quant-ph #cs.DS

paper · pdf · doi:10.26421/qic7.5-6-9

published as Quantum Information and Computation, Vol. 7, No. 5&6 (2007), 559-570 · 10 pages, final version. Algorithms modified to work with black-box groups too

arxiv created 2007/12/03 · arxiv updated 2021/10/05

Abstract

In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups ℤ_p^r\rtimesℤ_q, for p and q prime. We first present a classification of these groups in five classes. Then, we describe a polynomial-time quantum algorithm solving the HSP over all the groups of one of these classes: the groups of the form ℤ_p^r\rtimesℤ_p, where p is an odd prime. Our algorithm works even in the most general case where the group is presented as a black-box group with not necessarily unique encoding. Finally, we extend this result and present an efficient algorithm solving the HSP over the groups ℤ^m_p^r\rtimesℤ_p.

Cited by

• The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups