Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups

2007/03/23 by Carlos Magno Martins Cosme, Renato Portugal, Cosme, Carlos Magno M. +1 · 2 citations
Computer Science · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.quant-ph/0703223

openalex publication_date 2007/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present efficient quantum algorithms for the hidden subgroup problem (HSP) on the semidirect product of cyclic groups \Z_p^r\rtimes_ϕ\Z_p², where p is any odd prime number and r is any integer such that r>4. We also address the HSP in the group \Z_N\rtimes_ϕ\Z_p², where N is an integer with a special prime factorization. These quantum algorithms are exponentially faster than any classical algorithm for the same purpose.

Cited by

• A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective
• Quantum Computation Beyond the Circuit Model

Related

• Quantum computational algorithm for hidden symmetry subgroup problems on semi-direct product of cyclic groups
• Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups
• Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem
• An exact quantum hidden subgroup algorithm and applications to solvable groups
• Quantum Hidden Subgroup Problems: A Mathematical Perspective