{
  "annotation_id": "6db7c04e-5ba5-4ac9-be70-6a91fe36465a",
  "date_created": "2026-03-02T18:02:13.515000Z",
  "date_modified": "2026-03-02T18:02:13.515000Z",
  "file_hash": "0b89ff240b8387a11119a0f73b1217101b29d3435edc47b37fe607f8347826f6",
  "private": false,
  "record": {
    "abstract": "Part I of this paper showed that the hidden subgroup problem over the\nsymmetric group--including the special case relevant to Graph\nIsomorphism--cannot be efficiently solved by strong Fourier sampling, even if\none may perform an arbitrary POVM on the coset state. In this paper, we extend\nthese results to entangled measurements. Specifically, we show that the hidden\nsubgroup problem on the symmetric group cannot be solved by any POVM applied to\npairs of coset states. In particular, these hidden subgroups cannot be\ndetermined by any polynomial number of one- or two-register experiments on\ncoset states.",
    "arxiv_id": "quant-ph/0501066",
    "authors": [
      "Cristopher Moore",
      "Alexander Russell"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "The Symmetric Group Defies Strong Fourier Sampling: Part II",
    "url": "https://arxiv.org/abs/quant-ph/0501066"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "f78f0bcb-5a44-45da-9322-3a42983b3be7",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}