dorsal/arxiv
View SchemaEfficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups
| Authors | Yoshifumi Inui, Francois Le Gall |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0412033 |
| URL | https://arxiv.org/abs/quant-ph/0412033 |
| DOI | 10.26421/QIC7.5-6-9 |
| Journal | Quantum Information and Computation, Vol. 7, No. 5&6 (2007), 559-570 |
Abstract
In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_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 $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_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 $\mathbb{Z}^m_{p^r}\rtimes\mathbb{Z}_p$.
{
"annotation_id": "7425356c-4b7b-4480-8767-fd16ff14fb69",
"date_created": "2026-03-02T18:02:13.321000Z",
"date_modified": "2026-03-02T18:02:13.321000Z",
"file_hash": "0ac83a09ec3be8d34c696227d180f32a01f9ec86c8af9c2fe204500bbaea4652",
"private": false,
"record": {
"abstract": "In this paper, we consider the hidden subgroup problem (HSP) over the class\nof semi-direct product groups $\\mathbb{Z}_{p^r}\\rtimes\\mathbb{Z}_q$, for p and\nq prime. We first present a classification of these groups in five classes.\nThen, we describe a polynomial-time quantum algorithm solving the HSP over all\nthe groups of one of these classes: the groups of the form\n$\\mathbb{Z}_{p^r}\\rtimes\\mathbb{Z}_p$, where p is an odd prime. Our algorithm\nworks even in the most general case where the group is presented as a black-box\ngroup with not necessarily unique encoding. Finally, we extend this result and\npresent an efficient algorithm solving the HSP over the groups\n$\\mathbb{Z}^m_{p^r}\\rtimes\\mathbb{Z}_p$.",
"arxiv_id": "quant-ph/0412033",
"authors": [
"Yoshifumi Inui",
"Francois Le Gall"
],
"categories": [
"quant-ph",
"cs.DS"
],
"doi": "10.26421/QIC7.5-6-9",
"journal_ref": "Quantum Information and Computation, Vol. 7, No. 5\u00266 (2007),\n 559-570",
"title": "Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups",
"url": "https://arxiv.org/abs/quant-ph/0412033"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b861f0de-b546-40a1-9568-07e1a1fd0718",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}