dorsal/arxiv
View SchemaThe Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
| Authors | Cristopher Moore, Daniel Rockmore, Alexander Russell, Leonard Schulman |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0211124 |
| URL | https://arxiv.org/abs/quant-ph/0211124 |
Abstract
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a subgroup H of a group G must be determined from a quantum state y uniformly supported on a left coset of H. These hidden subgroup problems are then solved by Fourier sampling: the quantum Fourier transform of y is computed and measured. When the underlying group is non-Abelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups of semidirect products of Z_p by Z_q, where q divides (p-1) and q = p / polylog(p), can be efficiently determined by the strong standard method. Furthermore, the weak standard method and the ``forgetful'' Abelian method are insufficient for these groups. We extend this to an information-theoretic solution for the hidden subgroup problem over semidirect products of Z_p by \Z_q where q divides (p-1) and, in particular, the Affine groups A_p. Finally, we prove a closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.
{
"annotation_id": "4752e595-dcee-4b8a-bfa6-c961af2be665",
"date_created": "2026-03-02T18:01:56.119000Z",
"date_modified": "2026-03-02T18:01:56.119000Z",
"file_hash": "7b982cae2959d5e41c35d5aea6ee88b1a40faef5547a539d027eda7d7d6faf45",
"private": false,
"record": {
"abstract": "Many quantum algorithms, including Shor\u0027s celebrated factoring and discrete\nlog algorithms, proceed by reduction to a hidden subgroup problem, in which a\nsubgroup H of a group G must be determined from a quantum state y uniformly\nsupported on a left coset of H. These hidden subgroup problems are then solved\nby Fourier sampling: the quantum Fourier transform of y is computed and\nmeasured. When the underlying group is non-Abelian, two important variants of\nthe Fourier sampling paradigm have been identified: the weak standard method,\nwhere only representation names are measured, and the strong standard method,\nwhere full measurement occurs. It has remained open whether the strong standard\nmethod is indeed stronger, that is, whether there are hidden subgroups that can\nbe reconstructed via the strong method but not by the weak, or any other known,\nmethod. In this article, we settle this question in the affirmative. We show\nthat hidden subgroups of semidirect products of Z_p by Z_q, where q divides\n(p-1) and q = p / polylog(p), can be efficiently determined by the strong\nstandard method. Furthermore, the weak standard method and the ``forgetful\u0027\u0027\nAbelian method are insufficient for these groups. We extend this to an\ninformation-theoretic solution for the hidden subgroup problem over semidirect\nproducts of Z_p by \\Z_q where q divides (p-1) and, in particular, the Affine\ngroups A_p. Finally, we prove a closure property for the class of groups over\nwhich the hidden subgroup problem can be solved efficiently.",
"arxiv_id": "quant-ph/0211124",
"authors": [
"Cristopher Moore",
"Daniel Rockmore",
"Alexander Russell",
"Leonard Schulman"
],
"categories": [
"quant-ph"
],
"title": "The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling",
"url": "https://arxiv.org/abs/quant-ph/0211124"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "00465a6f-c16f-410d-988c-7e8484739c85",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}