{
  "annotation_id": "eff3692f-92af-442d-86f1-a2b86afdcfe2",
  "date_created": "2026-03-02T18:02:20.633000Z",
  "date_modified": "2026-03-02T18:02:20.633000Z",
  "file_hash": "0888c1137daa9bfb686c97fb15465d1cdf0a6b07a13b3b179f296d5614f3fe0b",
  "private": false,
  "record": {
    "abstract": "We establish a general method for proving bounds on the information that can\nbe extracted via arbitrary entangled measurements on tensor products of hidden\nsubgroup coset states. When applied to the symmetric group, the method yields\nan Omega(n log n) lower bound on the number of coset states over which we must\nperform an entangled measurement in order to obtain non-negligible information\nabout a hidden involution. These results are tight to within a multiplicative\nconstant and apply, in particular, to the case relevant for the Graph\nIsomorphism problem.\n  Part of our proof was obtained after learning from Hallgren, Roetteler, and\nSen that they had obtained similar results.",
    "arxiv_id": "quant-ph/0511149",
    "authors": [
      "Cristopher Moore",
      "Alexander Russell"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Tight Results on Multiregister Fourier Sampling: Quantum Measurements   for Graph Isomorphism Require Entanglement",
    "url": "https://arxiv.org/abs/quant-ph/0511149"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "308feb69-7621-41ac-9b27-927d73e039a3",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}