dorsal/arxiv
View SchemaThe hidden subgroup problem and permutation group theory
| Authors | Julia Kempe, Aner Shalev |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0406046 |
| URL | https://arxiv.org/abs/quant-ph/0406046 |
| Journal | Proc. 16th ACM-SIAM SODA, p. 1118-1125 (2005) |
Abstract
We employ concepts and tools from the theory of finite permutation groups in order to analyse the Hidden Subgroup Problem via Quantum Fourier Sampling (QFS) for the symmetric group. We show that under very general conditions both the weak and the random-strong form (strong form with random choices of basis) of QFS fail to provide any advantage over classical exhaustive search. In particular we give a complete characterisation of polynomial size subgroups, and of primitive subgroups, that can be distinguished from the identity subgroup with the above methods. Furthermore, assuming a plausible group theoretic conjecture for which we give supporting evidence, we show that weak and random-strong QFS for the symmetric group have no advantage whatsoever over classical search.
{
"annotation_id": "bf04f242-fcc5-468f-aeb4-064f06a236cf",
"date_created": "2026-03-02T18:02:06.650000Z",
"date_modified": "2026-03-02T18:02:06.650000Z",
"file_hash": "809b96c1c0c94012345af00a515740534c34ee5fdd4ad25d7fd28f44889e92c0",
"private": false,
"record": {
"abstract": "We employ concepts and tools from the theory of finite permutation groups in\norder to analyse the Hidden Subgroup Problem via Quantum Fourier Sampling (QFS)\nfor the symmetric group. We show that under very general conditions both the\nweak and the random-strong form (strong form with random choices of basis) of\nQFS fail to provide any advantage over classical exhaustive search. In\nparticular we give a complete characterisation of polynomial size subgroups,\nand of primitive subgroups, that can be distinguished from the identity\nsubgroup with the above methods. Furthermore, assuming a plausible group\ntheoretic conjecture for which we give supporting evidence, we show that weak\nand random-strong QFS for the symmetric group have no advantage whatsoever over\nclassical search.",
"arxiv_id": "quant-ph/0406046",
"authors": [
"Julia Kempe",
"Aner Shalev"
],
"categories": [
"quant-ph",
"cs.CC"
],
"journal_ref": "Proc. 16th ACM-SIAM SODA, p. 1118-1125 (2005)",
"title": "The hidden subgroup problem and permutation group theory",
"url": "https://arxiv.org/abs/quant-ph/0406046"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "85b863e1-1010-4e4d-8e20-9b4e5c175fd7",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}