dorsal/arxiv
View SchemaThe Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
| Authors | Cristopher Moore, Daniel Rockmore, Alexander Russell, Leonard J. Schulman |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0503095 |
| URL | https://arxiv.org/abs/quant-ph/0503095 |
Abstract
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a Hidden Subgroup problem, in which an unknown subgroup H of a group G must be determined from a uniform superposition on a left coset of H. These hidden subgroup problems are typically solved by Fourier sampling. When G is nonabelian, two important variants of Fourier sampling have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation, in a suitably chosen basis) occurs. It has remained open whether the strong standard method is indeed stronger. In this article, we settle this question in the affirmative. We show that hidden subgroups H of the q-hedral groups, i.e., semidirect products Z_q \ltimes Z_p where q | (p-1), and in particular the affine groups A_p, can be information-theoretically reconstructed using the strong standard method. Moreover, if |H| = p/ \polylog(p), these subgroups can be fully reconstructed with a polynomial amount of quantum and classical computation. We show that, for some q, neither the ``forgetful'' abelian method nor measuring in a random basis succeeds, even information-theoretically. Thus, at least for some groups, it is crucial to use the full power of representation theory: namely, to measure the high-dimensional representations in an adapted basis that respects the group's subgroup structure. We apply our algorithm for the hidden subgroup problem to new families of cryptographically motivated Hidden Shift problems, generalizing work of van Dam, Hallgren and Ip on shifts of multiplicative characters.
{
"annotation_id": "87b1bb8e-5047-4dcb-97d0-3a022184731e",
"date_created": "2026-03-02T18:02:13.795000Z",
"date_modified": "2026-03-02T18:02:13.795000Z",
"file_hash": "0c159e81d0b82615835791186f47e59239dde042e5af16d09c9273511e2e96eb",
"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 an\nunknown subgroup H of a group G must be determined from a uniform superposition\non a left coset of H. These hidden subgroup problems are typically solved by\nFourier sampling. When G is nonabelian, two important variants of Fourier\nsampling have been identified: the weak standard method, where only\nrepresentation names are measured, and the strong standard method, where full\nmeasurement (i.e., the row and column of the representation, in a suitably\nchosen basis) occurs. It has remained open whether the strong standard method\nis indeed stronger. In this article, we settle this question in the\naffirmative. We show that hidden subgroups H of the q-hedral groups, i.e.,\nsemidirect products Z_q \\ltimes Z_p where q | (p-1), and in particular the\naffine groups A_p, can be information-theoretically reconstructed using the\nstrong standard method. Moreover, if |H| = p/ \\polylog(p), these subgroups can\nbe fully reconstructed with a polynomial amount of quantum and classical\ncomputation. We show that, for some q, neither the ``forgetful\u0027\u0027 abelian method\nnor measuring in a random basis succeeds, even information-theoretically. Thus,\nat least for some groups, it is crucial to use the full power of representation\ntheory: namely, to measure the high-dimensional representations in an adapted\nbasis that respects the group\u0027s subgroup structure. We apply our algorithm for\nthe hidden subgroup problem to new families of cryptographically motivated\nHidden Shift problems, generalizing work of van Dam, Hallgren and Ip on shifts\nof multiplicative characters.",
"arxiv_id": "quant-ph/0503095",
"authors": [
"Cristopher Moore",
"Daniel Rockmore",
"Alexander Russell",
"Leonard J. Schulman"
],
"categories": [
"quant-ph"
],
"title": "The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts",
"url": "https://arxiv.org/abs/quant-ph/0503095"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b862041d-7da8-49af-beb3-ad2cdf8ca416",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}