Revisiting finite Abelian hidden subgroup problem and its distributed exact quantum algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914223134605312 |
|---|---|
| author | Dong, Ziyuan Fan, Xiang Zhong, Tengxun Qiu, Daowen |
| author_facet | Dong, Ziyuan Fan, Xiang Zhong, Tengxun Qiu, Daowen |
| contents | We revisit the finite Abelian hidden subgroup problem (AHSP) from a mathematical perspective and make the following contributions. First, by employing amplitude amplification, we present an exact quantum algorithm for the finite AHSP, our algorithm is more concise than the previous exact algorithm and applies to any finite Abelian group. Second, utilizing the Chinese Remainder Theorem, we propose a distributed exact quantum algorithm for finite AHSP, which requires fewer qudits, lower quantum query complexity, and no quantum communication. We further show that our distributed approach can be extended to certain classes of non-Abelian groups. Finally, we develop a parallel exact classical algorithm for finite AHSP with reduced query complexity; even without parallel execution, the total number of queries across all nodes does not exceed that of the original centralized algorithm under mild conditions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_22959 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Revisiting finite Abelian hidden subgroup problem and its distributed exact quantum algorithm Dong, Ziyuan Fan, Xiang Zhong, Tengxun Qiu, Daowen Quantum Physics Distributed, Parallel, and Cluster Computing We revisit the finite Abelian hidden subgroup problem (AHSP) from a mathematical perspective and make the following contributions. First, by employing amplitude amplification, we present an exact quantum algorithm for the finite AHSP, our algorithm is more concise than the previous exact algorithm and applies to any finite Abelian group. Second, utilizing the Chinese Remainder Theorem, we propose a distributed exact quantum algorithm for finite AHSP, which requires fewer qudits, lower quantum query complexity, and no quantum communication. We further show that our distributed approach can be extended to certain classes of non-Abelian groups. Finally, we develop a parallel exact classical algorithm for finite AHSP with reduced query complexity; even without parallel execution, the total number of queries across all nodes does not exceed that of the original centralized algorithm under mild conditions. |
| title | Revisiting finite Abelian hidden subgroup problem and its distributed exact quantum algorithm |
| topic | Quantum Physics Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2512.22959 |