{
  "annotation_id": "dac29163-eaee-4107-9c71-1669e45beda5",
  "date_created": "2026-03-02T18:02:20.224000Z",
  "date_modified": "2026-03-02T18:02:20.224000Z",
  "file_hash": "4bb00d77eccf804217ee8f2fe09a1807175424dfb06b30b2fa395c3cf9d7d3b8",
  "private": false,
  "record": {
    "abstract": "We present a negative result regarding the hidden subgroup problem on the\npowers $G^n$ of a fixed group $G$. Under a condition on the base group $G$, we\nprove that strong Fourier sampling cannot distinguish some subgroups of $G^n$.\nSince strong sampling is in fact the optimal measurement on a coset state, this\nshows that we have no hope of efficiently solving the hidden subgroup problem\nover these groups with separable measurements on coset states (that is, using\nany polynomial number of single-register coset state experiments). Base groups\nsatisfying our condition include all nonabelian simple groups. We apply our\nresults to show that there exist uniform families of nilpotent groups whose\nnormal series factors have constant size and yet are immune to strong Fourier\nsampling.",
    "arxiv_id": "quant-ph/0511054",
    "authors": [
      "Gorjan Alagic",
      "Cristopher Moore",
      "Alexander Russell"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Strong Fourier Sampling Fails over $G^n$",
    "url": "https://arxiv.org/abs/quant-ph/0511054"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "c31aac96-f64d-4e9d-a3fe-85f3d186a1bd",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}